Hey Guys, I've been trying for a long time to solve this question Watto and Mechinism using a Trie. I know this task can be accomplished using hashing too, but I need help with a Trie based solution so that I can understand Tries better.
Now, I Have written a solution in Java almost identical to another solution that has been written in C++. The C++ based soltuion gets an AC, whereas I keep getting TLE on test case 33. The AC code does not belong to me and I've used it only for learning purpose . I have completely been unable to understand what I have done different My Submission from this one . Please help me with this. What am I doing wrong or different from the AC solution here.??
any help would be useful
The AC code looks like it checks many possibilities in the trie, changing at each possible index. How does that not get TLE?
Exactly...And I find my java code to no different at all and it gets "TLE"...this amuses me to be frank...It makes me feel hashing is just a better option whenever I come across such a question..What do u feel?
I think there should've been a test case to break this kind of code. That's a problem setter's problem. I mean, submitting this in a contest is risky. It may be possible that the author was simply checking if this solution passes, and he himself doubted that it will. Java is 5x slower, so yeah, never use Java with such risky codes in a contest.
On second thoughts, I may not have analyzed the complexity correctly. eg: the branching may occur at all indices, but at each index, there can be max 2 possible brach-outs, and then no branching once this has been done. That's easily O( m*(length^2) ). Sum over all lengths is ~ 10^6, and in order for the code to reach maximum complexity, there must be O(length) strings at least, right? So, if all strings have same length(to reach maximum level), then 10^6=length^2. length of string ~ 10^3 on average. Even then, the maximum complexity is m*10^6. Ok, I can't seem to justify with complexity analysis, and if someone can, please do. Until then, I'll assume test suite is weak.
Hey thanx fam, your point seems completely valid to me.. :)
The time complexity of the find operation is O(3 * lengthofstring). Now since sum of all string length is 6 * 105 , this shouldnt TLE.
There are 10^5 queries
I guess the number of queries shall not make a difference here, as it it guaranteed that the length of all strings would not exceed 6*10^5. However, @arrogantidiot, the sample code in C++ gets AC in max 749 ms and my indetical code in Java gets TLE . Can you help regarding this?
I thought they meant problem's input(not code's input). Now it makes sense :)
Can someone provide me some resources for learning tries?
Its comparison with other string search algorithms like hashing,kmp,suffix array( i mean to say when to use it).
Using Tries: Topcoder
Following is the Trie based solution: First build the trie inserting all N strings into the structure. Fields of trie will be these: a boolean variable "is" indicating whether a word has ended here or not, and an array of references to structure(we need 3 references). For query, we will have a function which takes 3 parameters:
Now at each node of our trie, if the third boolean value "taken" is true, we have no choice but to "try" to go to the path of the string being queried. If there is no path we can return false else we will go into that path.
Now the other case, if the third boolean value "taken" is false, then we can try each of the 3 paths(if there is one). If we go to a path which is different from the string being queried, then we pass the third variable "taken" as true in the recursive call of this path because we have changed a character. Base case will be when the entire string has been queried and we are at a node where "is" is true and "taken" is also true.
AC Code
The exact same thing TLE's in Java. 1200 ms is quite a lot in C++ u know...
Maybe that is because I used slower cin and cout. Same thing with scanf passes in 280 ms. See.