_nathan_drake_'s blog

By _nathan_drake_, history, 4 years ago, In English

Can someone tell me why did I have TLE in one approach but got ac with a huge time margin for the second approach. https://www.codechef.com/viewsolution/29264170 https://www.codechef.com/viewsolution/29262311

For the first approach I stored all the strings in a unordered set. Then , for each string s1 in the set I checked it with other strings . If a string matches prefix of s1 , then I recur for the string s1 — prefix . Base case will be when the current string s1 matched totally with a prefix. Then I return 1, else 0.

For the second approach I stored all the strings in a unordered set. Then , for each string s1 in the set , I checked if there exists a string that matches a particular length prefix. If yes, then I recur for the string s1 — prefix .

Why is the time limit difference . Am I missing something.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By _nathan_drake_, history, 6 years ago, In English

Can anyone provide a better editorial for this question . https://www.codechef.com/LTIME01/problems/GRTRIP

I have been trying to understand it for a week now, but I fail to understand how shortest path tree is being constructed and how it is compared with the dfs done by chef in his own algorithm.

Please help

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it