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
@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.