How to solve it?

#1

please help with the approach

#2

Hello @chemant077,

In this problem, you are given n clues in the form of n strings.
You have to find a code with the help of the given clues based on the length of longest common prefix of (ai, aj).
It will too large to dry run this approach the example you have given.

Solution:
This is question of Trie.
what we do is for all nodes of the trie , we calculate number of strings in the substree and then just apply combinatorics.
you can see my code:

Hope, this would help.

#3

void dfs(node *root,int dep){ int ans=0; for(int i=0;i<26;i++){ if(root->next[i]!=NULL){ dfs(root->next[i],dep+1); root->cnt+=root->next[i]->cnt; ans-=NC2(root->next[i]->cnt); } } ans+=NC2(root->cnt); // db(ans,dep); anss[dep]+=ans;

#4

CAN YOU please explain why you did the ans-=nc2(root->next[i].cnt)

#5

Hello @chemant077,

what we do is for all nodes of the trie , we calculate number of strings in the substree and then just apply combinatorics such -
NC2(total nodes in the subtree of current nodes)-summation of NC2(children in each nodes)

#6

your code in not printing anything

#7

bro am really not getting your logic

#8

To find the code of the treasure box they need to find the sum of total number of combination (i, j) [the combination are unordered] such that - length of longest common prefix of (ai, aj) = M. They need to do this for all k that lies in [0, max(length(ai))]. can you please explain this line

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.