TWSTR - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

This problem can be solved by using a trie. Try inserting a string into the trie, at every node while inserting store 2 extra variables one for the priority and the other for the index of the string with the priority. If while inserting the priority of the string to be inserted is greater than the priority at that node replace the priority at that node with the greater priority and the index of the string to the current string.

Answering queries is pretty straight forward. Traverse the trie with the query and if the query is present print the string whose index is present at the last node of the query traversal, else print “NO”.

Note: Please look at the setter solution for a better understanding of the explanation.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2 Likes
2

Hi,I followed the editorial and my trie implementation experienced timeout.Let me know if I can do more optimizations.Below is my Code


[1]  


  [1]: https://www.codechef.com/viewsolution/15477613