CFMM - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest, div. 1
Contest, div. 2

Author: Kerim Kochekov
Tester: Teja Vardhan Reddy
Editorialist: Oleksandr Kulkov

DIFFICULTY:
CAKEWALK
PREREQUISITES:
None
PROBLEM:
You have N strings S_1, \dots, S_N. Their letters are all mixed up. What is the maximum amount of words codechef that you may make up of these letters?
EXPLANATION:
To complete the word codechef you need two letters e, two letters c, one letter o, one letter h, one letter d and one letter f. Let’s denote number of letter x in the set as \#_x. Under such notion the answer can be written as ans=\min(\left\lfloor\#_e/2\right\rfloor,\left\lfloor\#_c/2\right\rfloor, \#_h, \#_f,\#_o,\#_d). Indeed, each of arguments here make an upper bound on number of possible words codechef and on the other hand you always may take all needed letters to get exactly ans codechef’s. Possible code:

int N;
cin >> N;
vector<string> S(N);
string s;
for(int i = 0; i < N; i++) {
	cin >> S[i];
	s += S[i];
}
int nc = count(begin(s), end(s), 'c');
int no = count(begin(s), end(s), 'o');
int nd = count(begin(s), end(s), 'd');
int ne = count(begin(s), end(s), 'e');
int nh = count(begin(s), end(s), 'h');
int nf = count(begin(s), end(s), 'f');
cout << min({ne / 2, nc / 2, nh, nf, no, nd}) << endl;

AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.

2 Likes
2 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> t;
	while(t--) {
		int n;
		cin >> n;
		string s[n];
		for(int i = 0; i < n; i++) {
			cin >> s[i];
		}
		int c = 0, o = 0, d = 0, e = 0, h = 0, f = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < s[i].size(); j++) {
				if(s[i][j] == 'c') {
					c++;
				} else if(s[i][j] == 'o') {
					o++;
				} else if(s[i][j] == 'd') {
					d++;
				} else if(s[i][j] == 'e') {
					e++;
				} else if(s[i][j] == 'h') {
					h++;
				} else if(s[i][j] == 'f') {
					f++;
				}
			}
		}
		c /= 2;
		e /= 2;
		cout << min(c, min(o, min(d, min(e, min(h, f))))) << endl;
	}
}

Although, I didn’t use any algorithm that the editorialist did, I did the same thing just much harder to do.

3 
#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        string str;
        for(int i = 0;i<n;i++){
            string s;
            cin>>s;
            str = str+s;
        }
        unordered_map<char,int> hash;
        n = str.size();
        for(int i = 0;i<n;i++){
            if(str[i] == 'c' || str[i] == 'o' || str[i] == 'd' || str[i] == 'e' || str[i] == 'h' || str[i] == 'f'){
                hash[str[i]]++;
            }
        }
        hash['c'] = hash['c']/2;
        hash['e'] = hash['e']/2;
        int min = 1000;
        string s = "codehf";
        for(int i = 0;i<s.size();i++){
            if(min>hash[s[i]])
                min = hash[s[i]];
        }
        cout<<min<<endl;
    }
    return 0;
}