CEXM - Editorial

editorial
1

PROBLEM LINK:

Contest

Author:Bhavya Dhingra
Tester: Siddhant Shrivastava
Editorialist: Bhavya Mittal, Abhishek Ghosh

DIFFICULTY:

EASY

PREREQUISITES:

Greedy

PROBLEM:

N words are given, which have to be divided into groups of K size. We need to find the maximum number of such groups that can be created, out of the words given in each test case. The condition that has to be satisfied, is that any 2 words in a valid group should not have the same first letter.

BRIEF EXPLANATION:

We are given N distinct strings, in which we have to find the maximum number of sets that we can make of size K, such that words in any set should not have the same first letter. This is achieved by creating a frequency array for all the letters, and continually (reverse)sorting it in each iteration as we extract the number of valid groups from it. We stop the process when we have less than K non-zero elements in it.

EXPLANATION:

A frequency array of size 26 (for each letter of the English Alphabet) is initialized with the value 0. This will store the number of occurrences of the first letter for each word, as we iterate over all the words.

Example:

0^{th} index will store the number of occurrences of A.

1^{st} index will store the number of occurrences of B, and so on.

For finding the maximum number of groups, we need to start with the letter having maximum frequency. The frequency array is sorted in descending order and each iteration involves decrement of first K elements by 1 each, and we end up with a valid group. This is followed by sorting the array in descending order again such that the first K elements are non-zero. The process is continued till the element at index (K-1) becomes 0, as at least K elements are required to form a valid group.

As the size of the array is small, so, sorting the array in each iteration won’t compromise the complexity of the problem much, and our solution gets accepted, without encountering TLE.

Considering the sample test case 1:

Our array would initially look something like this. (Only first 5 elements)

FIGURE 1

Group 1 with words having first letter as {A,B,C}

FIGURE 2

Group 2 with words having first letter as {A,B,D}

FIGURE 3

Group 3 with words having first letter as {A,B,E}

FIGURE 4

Now, the number of non-zero elements = 0 < k, so no more unique groups can be obtained.

SOLUTION

Setter's Solution 
#include <iostream> 
#include <string> 
#include <set> 
#include <map> 
#include <stack> 
#include <queue> 
#include <vector> 
#include <utility> 
#include <iomanip> 
#include <sstream> 
#include <bitset> 
#include <cstdlib> 
#include <iterator> 
#include <algorithm> 
#include <cstdio> 
#include <cctype> 
#include <cmath> 
#include <math.h> 
#include <ctime> 
#include <cstring> 
#include <unordered_set> 
#include <unordered_map> 
using namespace std;

#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007

int n,k;

void solve()
{
    cin>>n>>k;
    int freq[26] = {0};
    rep(n)
    {
        string s;
        cin>>s;
        freq[s[0]-'A']++;
    }

     int ans = 0;
    while(true)
    {
        sort(freq,freq+26,greater<int>());
        if(freq[k-1]==0)
            break;
        ans++;
         for(int i = 0;i<k;i++)
        {
            freq[i]--;
        }
    }

    cout<<ans;
}

int32_t main()
{    
    sync;
    int t = 1;
    while(t--)
    {
        solve();
        cout<<"\n";
    }
    return 0;
}
2 Likes