In the period between Nov. 28, 00:00 (UTC) and Nov. 28, 02:30 (UTC) Codeforces and Polygon will be possibly unavailable because of maintenance. ×

its_aks_ulure's blog

By its_aks_ulure, history, 7 months ago, In English

I was preparing some problems for a college contest from the past few weeks and came up with this problem idea.

Given N words consisting of either lowercase English letters or a special character '#'. 
Find the expected number of nodes in the trie after a trie is constructed replacing all the special character('#') in the words uniformly randomly with any letter between 'a' to 'z'. 

I want to know if there exists any polynomial time solution for this problem.

Thanks

Read more »

 
 
 
 
  • Vote: I like it
  • +28
  • Vote: I do not like it