Tag Archives: implementation

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 #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