Using Tries to solve bundling problem

Revision en2, by from_dyu_import_geek, 2020-03-30 18:41:05

Google Kickstart 2020 had a problem called bundling. I need a little help understanding some code for this problem. Below is someone else's code to solve this problem. I have understood that he is using a 2D array as a Trie (prefix tree). Can anyone please explain, step by step what his dfs() function does exactly? And what exactly the "cnt[]" array keeps track of. Thank you.

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

int n, k, c[2000001][26], m, cnt[2000001];
ll ans;

void dfs(int u=0, int d=0) {
	for(int v=0; v<26; ++v)
		if(c[u][v])
			dfs(c[u][v], d+1), cnt[u]+=cnt[c[u][v]];
	while(cnt[u]>=k) {
		cnt[u]-=k;
		ans+=d;
	}
}

void solve() {
	cin >> n >> k;
	m=1;
	for(int i=0; i<n; ++i) {
		string s;
		cin >> s;
		int u=0;
		for(char d : s) {
			if(!c[u][d-'A'])
				c[u][d-'A']=m++;
			u=c[u][d-'A'];
		}
		++cnt[u];
	}
	ans=0;
	dfs();
	cout << ans << "\n";
	memset(c, 0, m*sizeof(c[0]));
	memset(cnt, 0, m*4);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t, i=1;
	cin >> t;
	while(t--) {
		cout << "Case #" << i << ": ";
		solve();
		++i;
	}
}
Tags #googlekickstart, #trie, #preffix

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English from_dyu_import_geek 2020-03-30 18:41:05 328 Tiny change: 'ank you.\n~~~~~\n#' -> 'ank you.\n\n~~~~~\n#' (published)
en1 English from_dyu_import_geek 2020-03-30 18:33:09 992 Initial revision (saved to drafts)