Spoj( ONEZERO ) – Ones and zeros

2
Posted on by

Problem link: http://www.spoj.com/problems/ONEZERO/

Suppose the number that you want is X. X mod N = 0.

So you need to store only N states i.e. 0 to n-1. Start with 1.

Implement bfs approach. If the current state modulo is Y, append 0 to it i.e calculate Y*10 + 0 and find its modulo which will lead you to a new modulo state.

Similary append 1 to Y. i.e calculate Y*10 + 1 and find its modulo.

Example: if Y=11 append 0 to it to get 110 and append 1 to Y to get 111.

Have a parent array which will store the previous modulo state from which the current modulo state is reached. This parent array also acts as checkpoint to check if a modulo state is already visited or not.

Have a value array to store the value (1 or 0) that is appended to the parent modulo state to get the current modulo state.

Once the modulo state 0 is reached stop bfs and backtrack using parent array and value array to get the number (i.e smallest multiple of the number n consisting only of digits 1 and 0 beginning with 1).

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#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 mod 1000003
int parent[20005];
typedef long long int ll;
queue<int>q;
int temp,currentState;
int value[20005];
void solve(int n){
q.push(1);
parent[1]=0;
while(!q.empty()){
currentState=q.front();
q.pop();
if(currentState==0){
stack<int> s;
while(parent[currentState]){
s.push(value[currentState]);
currentState=parent[currentState];
}
s.push(1);
while(!s.empty()){
printf("%d",s.top());
s.pop();
}
printf("\n");
break;
}
temp=(currentState*10)%n;
if(parent[temp]==-1){
q.push(temp);
parent[temp]=currentState;
value[temp]=0;
}
temp=currentState*10+1;
temp%=n;
if(parent[temp]==-1){
q.push(temp);
parent[temp]=currentState;
value[temp]=1;
}
}
}
int main(){
int t,n;
scanf("%d",&t);
while(t--){
while(!q.empty()){
q.pop();
}
REP(i,20000)
parent[i]=-1;
scanf("%d",&n);
solve(n);
}
}
view raw ONEZERO.cpp hosted with ❤ by GitHub

Spoj (QUE1) Queue (Rookie)

1
Posted on by

problem link – http://www.spoj.com/problems/QUE1/

Vector of pairs is used to store the height and count of taller person standing before.

This problem can be solved by sorting the vector based on height.

Assign the final position for each person i in the answer array by moving them C empty positions from the index 0 where

C = count of taller person who are standing before person i

Detailed explanation is in the comments of the code below.

#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 10000005
typedef long long int ll;
int ans[1005];
int main(){
int t,n;
vector<pair<int,int> >arr;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
arr.resize(n);
memset(ans,0,sizeof ans);
//height
REP(i,n){
scanf("%d",&arr[i].first);
}
//count of ppl whose height is greater than the person at position i
REP(i,n){
scanf("%d",&arr[i].second);
}
//sort the vector of pairs based on the height
sort(arr.begin(),arr.end());
int greaterCount=0;
REP(i,n){
//greaterCount = count of ppl whose height is greater than the person at position i
greaterCount=arr[i].second;
REP(j,n){
//if there is no person whose height is greater than the height of current person (positioned at i) is found
//and if position j in ans array is not filled yet,then assign that person to position j
if(greaterCount==0&&ans[j]==0){
ans[j]=arr[i].first;
break;
}
//decrement the greaterCount eachtime when an unfilled answer position is found
//this implicitly means: decrement the greaterCount eachtime when a person with height greater than the current person i is found
if(ans[j]==0)
greaterCount--;
}
}
REP(i,n){
printf("%d ",ans[i]);
}
printf("\n");
}
}
view raw QUE1.cpp hosted with ❤ by GitHub

Solving K-Palindrome problem using Edit distance algorithm

0
Posted on by

A k-palindrome is a string which transforms into a palindrome on removing at most k characters.

Given a string S, and an interger K, print “YES” if S is a k-palindrome; otherwise print “NO”.
Constraints:
S has at most 20,000 characters.
0<=k<=30

Sample Test Case#1:
Input – abxa 1
Output – YES
Sample Test Case#2:
Input – abdxa 1
Output – No

Solution:

This can be solved using Edit distance dynamic programming algorithm. Edit distance DP algorithm can be used to find the minimum operations required to convert a source string  to destination string. The operations can be either addition or deletion of characters.

The K-palindrome problem can be solved using Edit distance algorithm by checking if the minimum operation required to convert the input string to its reverse.

Let editDistance(source,destination) be the function which takes source string and destination string and returns the minimum operations required to convert the source string to destination string.

A string S is K-palindrome if editDistance(S,reverse(S))<=2*K

This is because we can transform the given string S into its reverse by deleting  K letters and then inserting K letters.

This will be more clear with an example.

Let S=madtam and K=1.

To convert it into reverse of S, i.e matdam first we have to remove the character at index 3 ( 0 based index) in S.

Now the intermediate string is madam . Then we have to insert the character t at index 2 in the intermediate string to get “matdam” which is the reverse of string s.

If you look carefully you will know that the intermediate string “madam” is the palindrome that is obtained by removing k=1 characters.

Codeforces #224 (Div. 2) C. Arithmetic Progression

0
Posted on by

Problem link – http://codeforces.com/problemset/problem/382/C

#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 10000005
typedef long long int ll;
int main(){
int n;
int arr[100005];
vector<int> ans;
scanf("%d",&n);
REP(i,n){
scanf("%d",&arr[i]);
}
sort(arr,arr+n);
if(n==1){
cout<<"-1";
return 0;
}
if(n==2){
int diff=arr[1]-arr[0];
if(diff==0){
cout<<"1"<<endl<<arr[0];
return 0;
}
if(diff!=0&&diff%2==0){
ans.pb(arr[0]+diff/2);
}
ans.pb(arr[0]-diff);
ans.pb(arr[1]+diff);
}
else{
map<int,int> m;
FOR(i,1,n){
m[arr[i]-arr[i-1]]++;
}
int ms=m.size();
map<int,int>::iterator it;
if(ms==1){
it=m.begin();
if(it->first==0){
cout<<"1"<<endl<<arr[0];
return 0;
}
ans.pb(arr[0]-it->first);
ans.pb(arr[n-1]+it->first);
}
else if(ms==2){
vector<pair<int,int> >p;
int minCountValue,maxCountValue;
for(it=m.begin();it!=m.end();it++){
p.pb(mp(it->first,it->second));
}
if(p[0].second==1||p[1].second==1){
if(p[0].second==p[1].second){
if(p[0].first<p[1].first){
minCountValue=p[1].first;
maxCountValue=p[0].first;
}
}
else if(p[0].second<p[1].second){
minCountValue=p[0].first;
maxCountValue=p[1].first;
}
else{
minCountValue=p[1].first;
maxCountValue=p[0].first;
}
if(maxCountValue*2==minCountValue){
FOR(i,1,n){
if(arr[i]-arr[i-1]==minCountValue){
ans.pb(arr[i-1]+maxCountValue);
}
}
}
else{
cout<<"0";
return 0;
}
}
else{
cout<<"0";
return 0;
}
}
}
int ansSize=ans.size();
cout<<ansSize<<endl;
sort(ans.begin(),ans.end());
REP(i,ansSize){
cout<<ans[i]<<" ";
}
}
view raw Arithmetic Progression.cpp hosted with ❤ by GitHub

Codeforces Beta Round #84 (Div. 1) A. Lucky Sum of Digits

0
Posted on by

Problem link: http://codeforces.com/problemset/problem/109/A

A minimum number must contain less number of digits as possible. So to find the minimum number whose digit sum is equal to given n, we have to look into the case 1 and if it fails we have to move to case 2.If case 2 also fails then such minimum lucky  number cannot be formed.

Case 1:if the number can be formed using digits 7 alone.

Case 2: if the number can be formed with combination of digits 4 and 7 such that the number is minimum as possible

#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 10000005
typedef long long int ll;
int main(){
int n;
cin>>n;
if(n<4){
cout<<"-1";
return 0;
}
int numSeven=n/7;
int rem=n%7;
int numFour=rem/4;
int toBecomeFour=rem%4;
if(toBecomeFour!=0){
if(numSeven>=toBecomeFour){
numFour+=((7*toBecomeFour)+toBecomeFour)/4;
numSeven-=toBecomeFour;
}
else{
cout<<"-1";
return 0;
}
}
REP(i,numFour)
cout<<"4";
REP(i,numSeven)
cout<<"7";
}
view raw Lucky Sum of Digits.cpp hosted with ❤ by GitHub

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

Codeforces #211 (Div. 2) C.Fixing Typos

0
Posted on by

problem link: http://codeforces.com/problemset/problem/363/CA simple greedy approach will give you the solution.

A simple greedy approach will give you the solution.

Special care has to be taken for testcases like aabbccddeeff, aaaabbc

Code is self explanatory.

#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 10000005
typedef long long int ll;
//count in seperate vector and character in seperate vector
//count1[i] denotes the count of character[i]
vector<int>count1;
vector<char>character;
int main(){
string str;
cin>>str;
REP(i,str.size()){
char candidate=str[i];
int c=1;
for(int j=i+1;j<str.size();j++){
if(candidate==str[j])
c++;
else
break;
}
i+=(c-1);
count1.pb(c);
character.pb(candidate);
}
REP(i,count1.size()){
if(count1[i]>=3)
count1[i]=2;
}
REP(i,count1.size()-1){
if(count1[i]==2&&count1[i+1]==2){
count1[i+1]=1;
}
}
REP(i,count1.size()){
REP(j,count1[i]){
cout<<character[i];
}
}
}
view raw FixingTypos.cpp hosted with ❤ by GitHub

Codeforces #277 (Div. 2) C. Palindrome Transformation

0
Posted on by

Problem link -http://codeforces.com/contest/486/problem/C

Logic:

Check the number of characters that need to be changed inorder to make the given string palindrome.let the count be stored in variable ‘diff’.

It is optimal and sufficient to make changes to characters in any one of half of the string.

Lets choose the first half.

Case 1:

p is in first half of the string.

ans=diff+minimum number of steps required to move to all character positions that needs to be changed from position p

Case 2:

p is in 2nd half of the string.

Now reverse the string and make p=n-p+1

ans=diff+minimum number of steps required to move to all character positions that needs to be changed from position p

Thats all !

#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 10000005
typedef long long int ll;
int main(){
int n,p;
string str;
scanf("%d%d",&n,&p);
p--;
cin>>str;
int firstr;
firstr=n/2-1;
int diff=0;
//maxi - index of the rightmost character that needs to be changed in the first half of the string
//mini - index of the leftmost character that needs to be changed in the first half of the string
int mini=99999,maxi=-1;
if(p>firstr){
reverse(str.begin(),str.end());
p=n-1-p;
}
REP(i,firstr+1){
if(str[i]!=str[n-1-i]){
diff+=min((abs(str[i]-str[n-1-i])),abs(('z'-max(str[i],str[n-1-i]))+min(str[i],str[n-1-i])-'a'+1));
mini=min(mini,i);
maxi=max(maxi,i);
}
}
if(maxi>p&&mini<p){
if(abs(p-maxi)<abs(p-mini)){
diff+=abs(p-maxi)*2;
diff+=abs(p-mini);
}
else{
diff+=abs(p-mini)*2;
diff+=abs(p-maxi);
}
}
else if(maxi>p)
diff+=abs(p-maxi);
else if(mini<p)
diff+=abs(p-mini);
cout<<diff;
}
view raw Palindrome Transformation.cpp hosted with ❤ by GitHub

Codeforces #252 (Div.2) C. Valera and Tubes

0
Posted on by

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

The logic is very simple. Test cases might be misleading. Each tube has to be of length>=2.

So first find the points in zig zag path of the table.(i.e move from left to right and then go the next row and move from right to left and vice versa)

Let the first k-1 tubes be of length 2. Assign 2 points from the path for each tube.

Kth tube(last tube) will have the remaining cells in the zig zag path.

#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
typedef long long int ll;
int arr[305][305];
int visited[305];
int n,m,k;
int withinBoundary(int x,int y){
if(x>=0&&x<n&&y>=0&&y<m)
return 1;
else
return 0;
}
int main(){
cin>>n>>m>>k;
vector<pair<int,int> >q;
int dir=1;
int x=0,y=0;
q.pb(mp(0,0));
while(true){
y+=dir;
if(y==m){
dir*=-1;
y=m-1;
x++;
}
if(y==-1){
dir*=-1;
y=0;
x++;
}
if(x==n)
break;
q.pb(mp(x,y));
}
int j=0;
REP(i,k-1){
cout<<"2 ";
cout<<q[j].first+1<<" "<<q[j].second+1<<" "<<q[j+1].first+1<<" "<<q[j+1].second+1<<endl;
j+=2;
}
cout<<(n*m)-(2*(k-1))<<" ";
while(j<q.size()){
cout<<q[j].first+1<<" "<<q[j].second+1<<" ";
j++;
}
return 0;
}
view raw Valera and Tubes.cpp hosted with ❤ by GitHub