vedhant

Google Kickstart - Bundling

Mar 22nd, 2020
601
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define pb push_back
  4. #define all(x) (x).begin(), (x).end()
  5.  
  6. using namespace std;
  7.  
  8. struct node {
  9.     node * child[26];
  10.     // no of words having prefix formed till this node
  11.     ll prefixes;
  12.     // no of words ending at this node
  13.     ll count;
  14. };
  15.  
  16. node * newNode() {
  17.     node * temp = new node();
  18.     for(int i=0; i<26; ++i)
  19.         temp->child[i] = NULL;
  20.     temp->prefixes = temp->count = 0;
  21.     return temp;
  22. }
  23.  
  24. // insert string s into the trie
  25. void insert(node * root, string s) {
  26.     node * curr = root;
  27.     ll n = s.length();
  28.     curr->prefixes ++;
  29.     for(ll i=0; i<n; ++i) {
  30.         if(curr->child[s[i]-'A'] == NULL) {
  31.             node * temp = newNode();
  32.             curr->child[s[i]-'A'] = temp;
  33.         }
  34.         curr = curr->child[s[i]-'A'];
  35.         // curr will be a prefix of s
  36.         curr->prefixes ++;
  37.     }
  38.     // string ends at curr
  39.     curr->count++;
  40. }
  41.  
  42. ll dfs(node * u, ll k, ll depth) {
  43.     // if cannot group into sets of k words
  44.     if(u->prefixes < k)
  45.         return 0;
  46.     ll ans = 0;
  47.     // here = no of strings ending at this node
  48.     ll here = u->count;
  49.     for(int i=0; i<26; ++i) {
  50.         // v is child node
  51.         node * v = u->child[i];
  52.         if(v == NULL)
  53.             continue;
  54.         // add child ans
  55.         ans += dfs(v, k, depth + 1);
  56.         // add child residues to 'here'
  57.         here += (v->prefixes % k);
  58.     }
  59.     // finally, ans = child_ans + sum of scores of groups formed by strings counted by 'here'
  60.     ans += depth * (here / k);
  61.     return ans;
  62. }
  63.  
  64. int main() {
  65.     ios_base::sync_with_stdio(false);
  66.     cin.tie(NULL);
  67.     int t;
  68.     cin>>t;
  69.     for(int tc=1; tc<=t; ++tc) {
  70.         ll n, k;
  71.         cin>>n>>k;
  72.         node * trie = newNode();
  73.         for(ll i=0; i<n; ++i) {
  74.             string s;
  75.             cin>>s;
  76.             insert(trie, s);
  77.         }
  78.         ll ans = dfs(trie, k, 0);
  79.         cout<<"Case #"<<tc<<": "<<ans<<endl;
  80.     }    
  81. }
RAW Paste Data Copied