Bakry's blog

something weird cause TLE in szkopul
By Bakry, history, 6 years ago, In English

hello, there's something weird happened to me in szkopul website which caused TLE and after small changes to the code, it got AC..it happened to me in 2 problems.

1 — first problem : POI10-sums

I got 90 with this code and got TLE in test case 8 , but after that I got the full score using this code , the only difference between the two codes is that loop in dijkstra which in first code is :

for(int i = 0 ; i < n ; ++i)
{
    int now2 = now + arr[i] ;
    int cur2 = (cur + arr[i]) % arr[0] ;
    if(now2 > 1e9)
        continue ;
    if(now2 < vis[cur2] && now2 <= 1e9)
    {
        vis[cur2] = now2 ;
        q.push({now2 , cur2}) ;
    }
}

but in second code it's :

for(int i = 0 ; i < n ; ++i)
{
    int now2 = now + arr[i] ;
    int cur2 = (cur + arr[i]) % arr[0] ;
    //if(now2 > 1e9)
    //    continue ;
    if(now2 < vis[cur2] && now2 <= 1e9)
    {
        vis[cur2] = now2 ;
        q.push({now2 , cur2}) ;
    }
}

so the only difference is that I put this comment , there's no additional loop or nothing and the condition also was right.

2 — second problem : POI15-seals

I got 56 with this code and got TLE at test case 6, 7, 8, and 9, after that I made a small change and got 100 with this code, the only difference is that I made 

char arr[n][m] , arr2[a][b] ;

in the first code , and replaced it with

vector<string>arr(n) ;
vector<string>arr2(a);

in the second code, and I don't think that makes that great difference because it's the same time in taking input.

so I would like to know what makes first codes in this two problems get TLE and after very small differences it got the full score even that these small differences don't affect the time of the codes.

hope the blog wasn't long and hope to know the reason of TLE.

Thanks.

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

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

Compiler optimization and/or different complexities of different standard library functions are often the main reasons for making tangible differences in the execution-time and memory requirements in response to small changes in the code. Note that the TLE verdict may not tell you the amount of time by which the first code exceeded the time-limit thershold. Only 1 msec above the time-limit is sufficient to produce the TLE verdict.

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

    In the first problem: the difference between the AC code and the TLE code is more than 0.12 sec...and the difference between the two codes is the if condition, will just an if condition make that difference ?!

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

      The very-small difference in the high-level C++ source codes does not necessarily imply that the difference between the execution times of the complied object codes should be very-small as well. For example, if you define one of the arguments of some user-defined function in C++ as an object without using the reference operator '&' before the object name, then the C++ complier implicitly generates object code to create a new copy of the passed object, leaving the object in the function call unchanged. This very small change, only the '&' operator, can easily generate a TLE verdict if the size of the copied object is large, and the function call is repeated a large number of times inside a loop.

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

        yes, but if we looked in the above problem, only putting this if condition

        if(now2 > 1e9)
        continue ;

        in a comment make the code AC, I don't think it made a large difference.

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

          I agree with you. A plausible approach for more analysis is write a small peformance comparator for both functions, and compare the execution times for both functions with and without the condition statement. You should also write a small function to generate random test case with a 5000 items set and 10000 queries.

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

          Maybe the old GCC 4.8 compiler that szkopul uses doesn't catch on that this continue statement is not necessary and doesn't optimize it out well. But I'm not sure. Taking a look at the generated assembly code might hint something.

          → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Since 1e9 is a double, now2 is first converted into a double and then compared with 1e9. Change it to if(now2 > int(1e9)) so that you're comparing integers, which is much faster.

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

            A very tricky issue. Thanks for sharing.

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

            Thanks , when I made that in first code , I got AC , I didn't know that the conversion will take more than 120 ms.

            → Reply