Read about tries xD
Yeah I got that part!
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: https://www.codechef.com/viewsolution/18893009
How did the setter decide the upper-bound on the number of nodes of trie as (1<<20)?? Can anyone please explainā¦
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
@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.
@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 https://en.wikipedia.org/wiki/K-ary_tree ,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ā¦
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 https://www.codechef.com/viewsolution/18780484
It earned 100 points in 0.43 seconds.
1 Like
Nice explanation.
The test data for small test case for weak. Below is a counter test case for your solution:
2 a a 1 1 b
@arvindpunk, using map is fine and works in most cases. But beware of the additional O(\log{N}) factor it adds to your complexity and can give TLE in some problem. Learning and implementing tries is quite easy. I definitely recommend you to learn it as it is also the basis of harder string algorithms like aho-corasick, suffix tree etc. which use the same structure as its base. Also, tries are useful for xor-minimisation problems.
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.
https://ideone.com/eFFVqJ 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)