Tag Archives: datastructure

Codeforces #264 (Div. 2) C. Gargari and Bishops

0
Posted on by

Problem link: http://codeforces.com/problemset/problem/463/C

To find 2 positions such that bishops in these positions cannot attach each other, we have to select 2 coordinates such that sum of x,y(row,column) in one coordinate is even and odd in other one.

Find the sum of primary and secondary diagonal and calculate the max amount of money for each position. After that iterate through each position and find the maximum money,position in even sum index set and odd sum index set.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
#define REP(i,n) for(int i=0; i<n; i++)
#define FOR(i,st,end) for(int i=st;i<end;i++)
#define db(x) cout << (#x) << " = " << x << endl;
#define mp make_pair
#define pb push_back
#define MAX 100005
typedef long long int ll;
ll secondary[4001];
ll primary[4001];
pair<int,int> evenIndex;
pair<int,int> oddIndex;
ll value[2];
int arr[2001][2001];
//value 0 denotes even
//value 1 denotes odd
int main(){
memset(value,-1,sizeof value);
int n;
cin>>n;
REP(i,n){
REP(j,n){
scanf("%d",&arr[i][j]);
secondary[i+j]+=arr[i][j];
primary[i-j+n-1]+=arr[i][j];
}
}
ll candidate;
REP(i,n){
REP(j,n){
candidate=secondary[i+j]+primary[i-j+n-1]-arr[i][j];
if((i+j)&1){
if(candidate>value[1]){
value[1]=candidate;
oddIndex.first=i;
oddIndex.second=j;
}
}
else{
if(candidate>value[0]){
value[0]=candidate;
evenIndex.first=i;
evenIndex.second=j;
}
}
}
}
cout<<value[0]+value[1]<<endl;
if(value[0]>value[1]){
cout<<evenIndex.first+1<<" "<<evenIndex.second+1<<" ";
cout<<oddIndex.first+1<<" "<<oddIndex.second+1<<endl;
}
else{
cout<<oddIndex.first+1<<" "<<oddIndex.second+1<<" ";
cout<<evenIndex.first+1<<" "<<evenIndex.second+1<<endl;
}
}
view raw Gargari and Bishops.cpp hosted with ❤ by GitHub

Codeforces #296 (Div. 2) B. Error Correct System

2
Posted on by

problem link – http://codeforces.com/contest/527/problem/B

This problem can be solved correctly if one knows to use the correct datastructure which will give a optimized solution.

here we use a 2D array called sameIndex

This 2D array is used to store mismatched characters from String S and String T respectively which are in the same index
if sameIndex[0][1]=1 then it means ‘a’ from String S and ‘b’ from String T are in same index
if sameIndex[1][0]=1 then it means ‘b’ from S and ‘a’ from T are in same index

There are 3 cases to look into

Case 1: perfect swapping pair is found and hamming distance is decremented by 2

Case 2: a swapping fair is found and hamming distance is decremented by 1

Case 3: hamming distance remains the same

These cases are explained in the code comments

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
#define REP(i,n) for(int i=0; i<n; i++)
#define FOR(i,st,end) for(int i=st;i<end;i++)
#define db(x) cout << (#x) << " = " << x << endl;
#define mp make_pair
#define pb push_back
#define MAX 100005
typedef long long int ll;
int main(){
int n;
string str1,str2;
cin>>n;
cin>>str1>>str2;
//This 2D array is used to store mismatched characters from String S and String T respectively which are in the same index
//if sameIndex[0][1]=1 then it means 'a' from String S and 'b' from String T are in same index
//if sameIndex[1][0]=1 then it means 'b' from S and 'a' from T are in same index
int sameIndex[26][26]={0};
//The below array is used to store the indexes of the mismatched characters in string T
//NOTE: String S and T are represented by str1 and str2 in the code and comments from now on
int match[26];
int ham=0;
int f=0;
pair<int,int> ans;
memset(match,-1,sizeof match);
REP(i,n){
sameIndex[str1[i]-'a'][str2[i]-'a']=1;
if(str1[i]!=str2[i]){
match[str2[i]-'a']=i;
ham++;
}
}
REP(i,n){
if(str1[i]!=str2[i]){
//Case 1
//If characters str1[i] and str2[i] are different
//check if character str2[i] in string str1 and str1[i] in string str2 are present in same index
//if present then the 2 characters can be swapped and thus hamming distance will be decremented by 2
if(sameIndex[str2[i]-'a'][str1[i]-'a']){
ham-=2;
f=1;
REP(j,n){
if(str1[j]==str2[i]&&str2[j]==str1[i]){
ans.first=i+1;
ans.second=j+1;
break;
}
}
break;
}
}
}
if(!f){
REP(i,n){
//Case 2
//check if mismatched character belonging to str1 is present in mismatched character set of str2
//if present then we can swap str1[i] with the index where str1[i] is present in str2
if(str1[i]!=str2[i]){
if(match[str1[i]-'a']!=-1){
f=1;
ans.first=i+1;
ans.second=match[str1[i]-'a']+1;
ham--;
break;
}
}
}
}
cout<<ham<<endl;
if(f){
cout<<ans.first<<" "<<ans.second<<endl;
}
else{
cout<<"-1 -1";
}
}
view raw Error Correct System.cpp hosted with ❤ by GitHub

Given an array of length N containing integers between 1 and N, determine if it contains any duplicates in O(n) time complexity and O(1) space complexity

0
Posted on by

Since we cannot use extra space, take advantage of the fact that the array has elements only from 1 to n
and there are n elements in the array(index ranges from 0 to n-1)
So if 1 occurs make value at 0th index negative
if 2 occurs make the value at 1st index negative
if n occurs make the value at n-1th index negative
So if the same number occurs again then the value at that number index will be found negative already and
voila !Thus we found a way finding repeating number.
Algorithm
traverse the list for i= 0 to n-1 elements
{
check for sign of A[abs(A[i])] ;
if positive then
make it negative by A[abs(A[i])]=-A[abs(A[i])];
else // i.e., A[abs(A[i])] is negative
this element (ith element of list) is a repetition
}

Insert in a circular sorted linklist

0
Posted on by
#include<iostream>
using namespace std;
struct node
{
int data;
struct node *next;
};
struct node* createNewNode(int data){
struct node* nn=new struct node();
nn->data=data;
nn->next=NULL;
return nn;
}
struct node* sortedInsert(node *head,int data){
struct node* newNode=createNewNode(data);
struct node* current=head;
if(current==NULL){//if the circular LL is empty
newNode->next=newNode;
head=newNode;
}
else if(current->data>=newNode->data){// if newNode has to be inserted before the head
while(current->next!=head){
current=current->next;
}
current->next=newNode;
newNode->next=head;
head=newNode;
}
else{//if the newNode has to be inserted somewhere inbetween the list
while(current->next!=head&&current->next->data<newNode->data)
current=current->next;
newNode->next=current->next;
current->next=newNode;
}
return head;
}
void printList(struct node *start)
{
struct node *temp;
if(start != NULL)
{
temp = start;
cout<<endl;
do {
cout<<temp->data<<" ";
temp = temp->next;
} while(temp != start);
}
}
int main()
{
struct node *head = NULL;
for(int i = 6; i>0; i--)
{
head=sortedInsert(head,i);
}
printList(head);
return 0;
}
view raw circularSortedLL.cpp hosted with ❤ by GitHub

Move the spaces to the starting of the string in a c style string. In place within one iteration.

0
Posted on by

Start two pointers i & j from the end of the string.

a. Keep copying the character from ith location to the jth location and decrement both i & j
b. When i encounters a space, decrement i, but not j
c Repeat steps a & b until i falls of the beginning of the string.
d. Keep setting ‘space’ character at jth location and decrement j unitl j falls of the beginning of the string

source:careercup.com

You are given an array of n integers which can contain integers from 1 to n only . Some elements can be repeated multiple times and some other elements can be absent from the array . Write a running code on paper which takes O(1) space apart from the input array and O(n) time to print which elements are not present in the array and the count of every element which is there in the array along with the element number .

0
Posted on by

Time complexity : O(n)

Space complexity: O(1)

We implement count sort technique to get the frequency of the elements 1 to n

[gist https://gist.github.com/vishnujayvel/5998457]