aman_naughty's blog

INTERESTING TRIE PROBLEM HELP
By aman_naughty, history, 5 years ago, In English

problem link : LINK

submission link : code

I am adding words to the trie and while adding i also store at each node the lexicographically largest encrypted code encountered till now in it. As the encrypted code is unique for all the strings I maintain a hashmap with key=encrypted string and value = original string Then for any query my answer is simply the number of vowels in the original string found after searching the prefix in trie. Why is my code giving wrong answer. Can someone provide some test cases where this fails??

P.S. why are people downvoting this

  • Vote: I like it
  • -18
  • Vote: I do not like it

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

If multiple lines have the same 5-character code, you overwrite something in your map m. You print 1 instead of 6 for the following test:

2
baaaaaa ABCDE
x ABCDE
1
ba

If it still won't work, take someone's correct solution and compare the answers on random tests.

Also, I'm so sick of people downvoting blogs for no reason. Someone just asked a question, provided a problem link, described his solution. What else do you want?

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

    Thank you sir for replying so fast but in the problem statement it is mentioned that each string has a unique encrypted code and in your example this condition is violated I think or am I misunderstanding the meaning of unique here ??

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

This is very strange. Resubmitting your code gives me TLE instead of WA. Your constant factor is quite big. I changed checking vowels to using a function:

bool is_vowel(char ch) {
	return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}

... and it passed.

Btw. I think your complexity is O(Q·L) because for every query you might iterate over a long string to count vowels. Instead, you should store the number of vowels (so, the answer) in every node of the trie.

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

    But how come you changing the vowel checker made it pass??

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

      I changed the verdict from "Time Limit Exceeded" to "Accepted". Your code was too slow. Hashsets have a big constant factor.

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

        I thought my approach was correct and didn't knew that unordered_set have such time complexity. Also why did it show WA answer initially ??

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

          Unordered_set has O(1) complexity per operation, but the constant factor is quite big. It's a few times slower than operations on an array.

          The complexity is bad because of the algorithm, it isn't related to the unordered_set.

          I don't know why it showed WA. Either you have undefined behaviour (but I don't see a reason for that) or maybe it's Codechef's fault. Maybe you reached time limit, they killed your program, but the output was still checked? And that not-completed output was judged as WA. I don't know.

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

            Ok then what would be more optimal approach to do this question

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

              "Instead, you should store the number of vowels (so, the answer) in every node of the trie."

              Store the number of vowels instead of a string.

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

                If i store the number of vowels in a trie how would I match whether a query string exists in the trie as prefix or not??

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

                  The trie is still built using the strings. It's just that the nodes can store the number of vowels as an extra, or instead of the 5-character string.

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

I've been playing around a bit with this problem and I've noticed some things.

  1. This extremely advanced solution passes (it took a lot of effort to write those 12 lines), but this one fails. The only difference is that in the first one I use strip() on the query strings, removing whitespace before and after the string, which really shouldn't be necessary. So something is bad with the input.

  2. Just from my solution passing I can guarantee that the testcases are extremely weak.

  3. Strangely this solution by aman_naughty now gets TLE instead of wrong answer. The following is just my guess, but I think that it might be possible that they've changed the testcases. I know that during a monthly challenge on Codechef a while back I had the exact same reaction when suddenly my accepted solution didn't get accepted anymore when I resubmitted it, but the original solution stayed accepted. I asked around and got told that they've added additional testcases and that they would rejudge all solution later that week.

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

    Did some more tests to see if they've changed the testcases. Now I'm almost certain that's exactly what they've done.

    I tested resubmitting another users early submission. Previously he got WA but the code now gets accepted. I think that there might have been something off with the testcases in the beginning because it took 11-12 h until someone got an accepted solution.

    → Reply