aranjuda's blog

The curious case of 376D
By aranjuda, 11 years ago, In English

After going through the tutorial and seeing that an O(m*n) algorithm would pass and there was something to do with a "right" array, I coded up a solution that TLEd and then optimized it over XYZ attempts to this:

http://mirror.codeforces.com/contest/376/submission/5630035

which still TLEs. A friend optimized it to traverse in column major: http://mirror.codeforces.com/contest/376/submission/5631054

which passes. But, when I do the same:

http://mirror.codeforces.com/contest/376/submission/5631820

TLE! Any explanations?

Edit: Solved... (change char[] to string)

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

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

When you have two similar solutions, one of which passes and one doesn't, try to find differences.
In this case, try to replace "string" with "char[]" and get AC

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

    Yup, just changed it, thanks :) [Edit: I had somehow not seen the string/char[] difference :| ]

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

You are reading 25 megabytes of data with cin. Try using scanf or gets to read the data.

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

    I used sync_with_stdio(0); though.

    It passed once I changed it to a char array. I guess the overhead with string arrays is too high.

    → Reply