rachitnaruzu's blog

why this solution to "Watto and Mechanism" problem is incorrect.
By rachitnaruzu, 9 years ago, In English

link to problem: Watto and Mechanism

I used C++ maps and mapped all n strings in map, initially, like this:

//map<string,bool> m;
m[str] = true;

then for each query string s of length L, produced 3*L modified_strings (meaning: at every position in original string, putting 'a','b','c' to produce 3*L modified _strings with only one character difference from s) and check whether any of them are in map, like this:

//let t be one of the modified string
if(m[modified_string]) flag = true;

if any one of them is present in map then print "YES" otherwise "NO". But this solution is giving Wrong answer on pretest 6. Here 10118407 is my code. And secondly, i was not able to get the idea of using polynomial hashing, can anyone please explain ?

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Map isn't magic, you can't insert so many strings, because of memory limits...

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

    Thank you for your reply but could you please explain what has to be done, i was not able to get the solution to this one ? How to accomplish the task of saving strings, because they have to be saved somehow, i guess.

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

      http://codeforces.com/contest/514/problem/C

      Given string s, determine if the memory of the mechanism contains string t that consists of the same number of characters as s and differs from s in exactly one position.

      Besides of the fact this solution probably TLEs on large testcases (you consider something like 3m checks in your map, each of them may need to compare very long strings), you make some checks for strings t which are equal to s.

      E.g.

      1 2
aaa
aab
aaa

      Correct:

      YES
NO

      Your output (I guess):

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

        Thanks a lot. You were right, silly of me. After handling the above test case, it passed me for pretest 6 (just checked that if modified_string is in map then it must not be same as s).

        10122988 is my new code.

        But as kpw29 said, i'm getting "Memory limit exceeded" on test 18 now.

        Now if i rethink, my approach is totally wrong i guess, could you please tell me what is the efficient approach to this one ?

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

          You should use polynomial hash (See the editorial) or a trie for a good solution

          On another note, you should not check the existence of a key in a map by mp[key] like in your code. When you write mp[key] it creates a new entry in the map with that key and returns the new value which is initialized to the default value of the type(bool in your case). AFAIK default value of a primitive type is undefined, but seeing that your code has passed 17 pretests, it must be initializing them to false.

          Your solution might pass a couple more cases (atleast avoid MLE, though it will TLE) if you check existence in the map using map.find

          My solution using a trei — 10057709

          My solution using 2x Hash — 9866391

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

            When operator[] inserts new element in map, it is value-initialized (which means zero-initialize for scalar types) not default-initialized. It is well defined to false for bool and 0 for integer types.

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

            Well as you said, on using map.find it got me through test 18 but then TLE on 19.

            However, i understood the trie and hashing version of it.

            Thanks.

            → Reply