SHKSTR - Editorial

Please add the links to the actual coded solutions of editorialist/author/tester. Right now, they just re-direct to this page itself.

I implemented a trie for this problem
but only for task #3 it is giving WA and for rest 5 test cases it is giving AC
can anybody help me out with what is wrong in my code
https://www.codechef.com/viewsolution/18767595

In case if you don’t want to use data structure,Sort N+q strings with keep track of indices of q strings and then for every query check strings above and below it in the sorted list upto a condition and find the lexicographically smallest with longest LCP. It works fine.

3 Likes

I used a hashtable to hash all the substrings and keep track of all the indices of the strings having the substring.
Sort all the substrings lexicographically.
Then when the queries come, iterate through the substrings of P from largest to smallest. For each substring, break once you get an index <= r.

Solution here.

1 Like

can anyone explain me traverse_down function of testers code please…thanks in advance

I used similar approach as the second one. Just instead of storing vector of indices I stored lowest index of string which the character is part of. Unfortunately My code is erring out in task 3. Can any body point the bug ?
Here’s the link.

Also nice editorial. Thanks. Just few small corrections though -

  1. The tester has actually used approach 2 in his/her code.

  2. The editorials’ code cannot be opened - Access denied in XML tree.

my code failed for test case 4 .I did it the same way by storing the lowest index of string.
please can anyone check what is wrong.
here is the link to my solution-
link text

I have used almost the same approach as the online one. Instead of a vector, i just stored the first occurence of the alphabet and another field which told me the index of the first word which ends there.
But, I am getting a TLE for it. Could you help me find why it is happening?
The link to my solution CodeChef: Practical coding for everyone

Why not use map<string, int> instead of implementing a trie? I understand the space requirement will be more, but it works for the above constraints (also works for most questions related to string queries). Is there any other reason why map<string, int> is not generally considered?

Should there be test cases which only pass for actual tries and not map<string, int>? That forces the user to learn/understand how to implement them. Just my thoughts on this.

Here’s my attempt at the offline solution but with map:
https://www.codechef.com/viewsolution/18808837

Can you please post the test cases file for this particular problem so that i can know where specifically my program / logic went wrong in the bruteforce method .

How is the leftmost node guaranteed to be lexographically smaller?

I used trie with storing the minimum index of the inserted string but I am also getting wrong answer for Test Case 4 My code link.

Rest of the test cases are correct and fast enough. I might be missing a corner case but still unable to find it though.

@arnaagyeya: You can compare your solution with mine. I find your code quite unreadable to find the actual mistake. I’m sure you can understand your mistake after looking at my code. I just read about trie and implemented it so it may have some bugs but the solution worked for this problem.

Link to my code: CodeChef: Practical coding for everyone

How did the setter decide the upper-bound on the number of nodes of trie as (1<<20)?? Can anyone please explain…

@decagon: Thanks for the answer. I could not get where I was wrong as mine is online implementation but your implementation was very efficient. A very nice offline approach for this problem.

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