bkorecic's blog

By bkorecic, history, 5 weeks ago, In English

Hello,

With some friends we are very confused because of this. We have these two different codes:

The weird thing is that they are the same code, but the ONLY difference is how we read the input to the global string "path".

On the AC code:

string sAux; // line 69
cin >> sAux;
 
path = sAux;

On the TLE code:

cin >> path; // line 69

The submission that gives TLE reads directly into the global variable, while the AC code reads into an intermediary local string and then assigns to the global variable.

We have absolutely no idea why or how this makes any difference.

Any ideas? Thanks!

 
 
 
 
  • Vote: I like it
  • +15
  • Vote: I do not like it

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

    But I think this situation is different, because in both cases "path" is a global variable. The only thing that might change is where "sAux" is stored, but it should not matter because it's only used once (when assigning to "path"), unless the compiler does some weird stuff with "path".

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

O.o

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

This is interesting. I tried changing a few things, and got the following results (none of these use sAux):

  • Using bool visited[7][7] passed
  • Using vector<vector<bool>> visited did not
  • Passing the string as a const parameter got TLE
  • Changing the string to a char array got TLE

Then again, the program is very close to the TL, so I'm almost sure it's a small optimization that's causing the issue. For the cases that they both pass, it takes about 10% longer for the bool[7][7]. Adding back sAux only improved the running time by 0.01s.

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

    Interesting experimentation. Maybe one would have to look into the assembly to find what sAux does.