Google Kickstart 2020 Problem 4

general
1

Would anybody like to discuss the solution to problem 4 of this year’s Google Kickstart?

2

Trie.

3

I had thought of doing it that way but then I just sorted the strings in reverse order and picked up the strings one by one putting them into same groups for up to length k. But I got Wrong answer in it. Do you know as to why this failed.

4

Take this counter K = 2

abc adc add aed

3 Likes
5

Got it. Thanks a lot. I am getting a wrong answer on this one.

6

Will u please describe yur approach ??
@aniket_sanghi @priyansh19077

7

Use trie data structure and make a structure for 26 characters. After that insert string one by one and kept one count at each level which will denote number of strings with same prefix upto this length. After adding all the strings,iterate through all the levels and add count/k at each level.
Hope this will clear ur doubt

2 Likes
8

My approach is wrong. I just sorted all the strings in decreasing order lexicographic
ally. Then I just picked up the strings one by one and put them into groups. However, this was not correct so I would not suggest you to give any attention to it.

9

Ok, So I used something different so I’ll discuss that here.

I made a 2D array H, where H[i][j] is the hash of the prefix of ith string up to j characters.

Now I started from the MaxLength and checked the hash values for all the prefixes of that length, stored them in a map. Then I iterated the map and decreased the value of any key which was greater than K. I also stored the string’s index in a different set to check quickly if it’s already grouped or not.

I hoped that it will TLE for big cases, but on close inspection, it seems to work in O(No. of Chars).
And here’s my code for reference: Bundling

3 Likes
10

#include
#include

using namespace std;
int check (string s1,string s2)
{int temp=0;
for(int i=0;i<s1.size();i++)
{
if(s1[i]==s2[i])
{
temp++;
}else{
break;
}
}
return temp;
}

int main()
{
int t;
cin>>t;
for(int l=0;l<t;l++)
{
int n,k;
cin>>n>>k;
string s[n];
for(int i=0;i<n;i++)
{
cin>>s[i];
// cout<<s[i]<<" ";
}
sort(&s[0],&s[n]);

  int score=0,i=0;
  while((n-i-1)>0)
  {
      int count=0;
      for(int j=i;j<i+k-1;j++)
      {
         int temp =check(s[j],s[j+1]);
       
         if(j==i)
         {
             count=temp;
             continue;
         }
          else
          if(count>temp)
          {
              count=temp;
          }
    }
    score=score+count;
    i=i+k;
  }
  cout<<"Case #"<<l+1<<": "<<score<<endl;

}
}

11

I used a trie for solving this problem.
You can see my Video Solution here : Google Kickstart 2020 round A - Bundling | TRIE - YouTube

3 Likes
12

Refer JAN20 ENGLISH, almost similar approach

1 Like
13

I did it using trie, the basic idea was to process in a way to get max possible number of group whose contribution per group is max possible, then going for next smaller value means going in decreasing order of contribution possible by a group , suppose if the maximum length string is S and it’s occurrence is M then you can make M/k groups which will contribute (M/k)*s.size() into the answer, now the remaining M%k strings plus other strings of size < s.size() can be considered for contribution(max common prefix) of (S.size()-1). you can implement a quadratic solution using hasmaps at each iteration to get the count M or you can efficiently implement it using Trie,in trie just insert the words and maintain count for each prefix, in the end you should run a kind of dfs to get the answer in the bottom-up manner.
the solution i submitted:

2 Likes