All Tracks Data Structures Advanced Data Structures Trie (Keyword Tree) Problem

XTerminus Wars: Final Episode - This is the way
No tags

A long time ago in a galaxy far, far away...

It's over. It's all over.

They fought. Fought till the very end. 
The protectors of the force fought their ultimate battle against BITMonster and brought balance to the force and now that they have nothing to do, so they enjoy letter writing in different languages for Senator Dumit Drivastav.  

Dumit likes annoying people. When he came to know that the letters submitted to him contained some words which are not even a part of the required language, he had a wicked smile on his face. The next time, when our protectors submitted the letters to him, he came up with a silly way of writing letters.

Now here's something you should know...

Each Language has a set of words (Let's call it dictionary), and they are arranged on the basis of the weight allocated to them. Now the same word may have different meanings so it can reappear.

So now, Dumit asked them to rewrite the letter in the following manner.

Suppose there exist N-words in the language then for each word, he gives them a range L and R (1<=L<=R<=N) and they need to write any word of their choice which lies in the range L and R.  

The job was easy for them.

Later that night, at the dinner table one of the protectors said, " What could have been the minimum number of steps to correct each word of the letter, given that in each step we either get to add a new character at the end of the word or delete the last character of the word?"

Again they solved it. But can you?

Every word in the dictionary will be a combination of some lower case English alphabets.

Note: Every word has same length.



  • First-line contains N, the number of words in the language.
  • The next N lines will have words arranged in the order of weights.
  • Next Q, the number of words in the letter.
  • the next Q lines will have L, R and the word written by the protectors in the letter.



2 <= N <= 10000

1 <= Q <= 100000

1 <= L <= R <= N


The sum of the length of N-words used in the language won't exceed 50000.


For each word, output the minimum number of steps required to get the correct word that matches the words lying between L and R.


PROBLEM SETTER: Saurabh Kishore Tiwari

2 2 o
4 4 gh
2 5 fpyy
Time Limit: 1.5 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


Initializing Code Editor...
View All Notifications