MazzForces's blog

Watto and Mechanism (Tries) Help required.
By MazzForces, history, 8 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

any help would be useful

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

The AC code looks like it checks many possibilities in the trie, changing at each possible index. How does that not get TLE?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hey thanx fam, your point seems completely valid to me.. :)

        → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The time complexity of the find operation is O(3 * lengthofstring). Now since sum of all string length is 6 * 105 , this shouldnt TLE.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There are 10^5 queries

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        The total length of lines in the input doesn't exceed 6·10^5.

        I thought they meant problem's input(not code's input). Now it makes sense :)

        → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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:

  1. The node in the tree which we are at.
  2. String left to be searched(you can pass just an index and make the string global).
  3. A boolean value "taken" which indicates if there is exactly one character different in our trie traversal uptil now.

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The exact same thing TLE's in Java. 1200 ms is quite a lot in C++ u know...

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Maybe that is because I used slower cin and cout. Same thing with scanf passes in 280 ms. See.

      → Reply