Tag Archives: greedy algorithm

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 #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 #273 (Div.2) C.Table Decorations

0
Posted on by

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

Logic:

Case 1:

If (number of maximum colored balloon)/2 is greater than or equal to sum of rest of the 2 colored balloons, then we can decorate each table with 2 balloons from maximum colored balloon and 1 balloon from either of the 2 other colored balloons.

Case 2:

If (number of maximum colored balloon)/2 is lesser than the sum of rest of the 2 colored balloons, then maximum number of tables that we can decorate would be (total number of balloons available)/3.

#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 main(){
ll arr[3];
REP(i,3){
cin>>arr[i];
}
sort(arr,arr+3);
if(arr[0]+arr[1]<=arr[2]/2){
cout<<arr[0]+arr[1];
}
else{
cout<<((arr[0]+arr[1]+arr[2])/3);
}
}
view raw TableDecorations.cpp hosted with ❤ by GitHub