SHKSTR - Editorial

Is it necessary to store the entire vector of the indices of the strings at every node? Can’t we just keep the minimum index of the string at each node along that path and then the actual index of the string at it’s leaf node. Would be much more space efficient.

I used an entirely different approach, working in C#.

As each string is no more than 10 characters, each one of 26 lower case letters, each entire string can be encoded into a ‘long’, with 5 bits per letter. Comparisons like ‘CompareTo’ are then fast.

Define a class StringIndex, consisting of an encoded string and its index in the array.

Build a sorted list of StringIndex, sorted by the integer encoded string.

For each query, find its place in the sorted list by a binary search.

From there search forwards until an index within range, and set the common prefix with that string.

Then search backwards. Check whether the first one with an index in range has a longer common prefix. Search backwards until there is a shorter common prefix.

When no common prefix is found, set to the first string in the list with an index in range.

As the number being searched may be much less than the number of strings supplied, extract a series of shorter lists before starting any queries, and then choose the appropriate list to search for each query.

My submission may be found at CodeChef: Practical coding for everyone

It earned 100 points in 0.43 seconds.

1 Like

Nice explanation.

My code is not passing only the first test case .Can any one tell what is the first testcase?

Using same approach as editorialist,still getting wa.
eFFVqJ - Online C++0x Compiler & Debugging Tool - Ideone.com Here I am using unordered_map in trie to reduce unnecessary space but I have tried it directly also still getting wa. I am adding string no. to vector of strings at that position only if string having greater index than the last element in vector is lexicographically smaller than it

Even brute force is passing under 1s in pypy…

Can someone please explain the use of the member “leaf_id” in the “trie node” in editorialist’s solution
(I know it may be a lame question, but a beginner here)

Yes, it will consume less memory but in big O notation it will be same. Just wanted to explain through the example that it will still be same and such modified trie is helpful in general. Actually using it we can solve the problem for general range [l, r] instead of [1, r] but with additional O(\log{n}) factor.

1 Like

Similar optimisation as above comment.

use insert code option and then place your code

Please give link to your submission. Pasting code is tedious and takes lot of visible space.

There was an issue while linking the code. It is updated now.

Okay. The editorialists’ code was being displayed while clicking on testers’ solution. Thanks. Btw Any comments regarding my code ?

Read about tries xD

Yeah I got that part!

each string can have 10 letters…and there are 10^5 strings…
total characters possible are 10^6 at max… And (1<<20)== 2^20 is smallest multiple of 2 greater than 10^6

@l_returns why we looked for next multiple of 2… isn’t the trie a 26-nary tree instead of a binary tree. If we use the formula given in this m-ary tree - Wikipedia ,parameters should be h=10,k=26 to calculate total number of nodes in trie

He talks about that. Read the editorial and discussions above.

U r doing it wrong way… I had just calculated that answer before writing this comment of mine… It takes about 1.468*10^14 or something nodes to complete whole tree… But u need to realize that if we use nodes then we make them as much as we need… so at max we need 10^6 nodes…so why to waste other nodes… So setter must be using nodes which are needed… he won’t create whole tree when it’s not needed… and constrainsts prove we need 10^6 at max…
I didn’t knew the formula u said but I proved that formula using this example…

The test data for small test case for weak. Below is a counter test case for your solution:

2
a
a
1
1 b