raja_n's blog

Help regarding hacks
By raja_n, history, 4 years ago, In English

https://codeforces.net/contest/1389/submission/88316090

In the above solution of Educational Codeforces Round 92 for problem A,there is a loop used inside testcase loop.

So,I tried to hack it with 10000 testcases of 500000001 1000000000. According to this test case ,there will be 10000*5*pow(10,8) operations but still I don't get successful tle hack.Even my ide got crashed at this input but still codeforces did not give a tle.

Can anyone help me by telling why is it so?

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

»
4 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

This is because of compiler optimization. The compiler its self detected that it doesn't have to enter all the loop to find the answer. It detects that it have to enter for some few operations and if it didn't find an answer, then it breaks out early. Or, the compiler detected a pattern which can get the answer nearly instantly. In both cases, those are compiler optimizations. I have added volatile keyword to the i in the for loop, and it took around 700ms in one of these huge testcases( volatile keyword prevents compiler optimizations).

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

    So, You mean if I am giving same testcase 10000 times then compiler will find a pattern for that pattern and will not give a TLE?

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

      Nope, the same testcase it won't find a pattern. The pattern or breaking early is in the loop its self.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
        for(i=i1;i<=i2;i++){
    if(i2-i2%i1>i1){
        cout<<i1<<" "<<i2-i2%i1<<endl;
        flag=1;
        break;
    }
}

        This is the loop which will run 5*pow(10,8) times if i1=500000001 and i2=1000000000, there is no answer for this test case,So IF condition will never be true and loop will never break itself.

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

          i2-i2%i1>i1 will always produce an answer in the first iteration if an answer exists. If there is no answer, it automatically breaks. No need to continue through the loop. That is what C++ compiler detects.

          See this submission here. I made the loop run only once and it got Accepted.

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

          The compiler (GCC 10.1.0, with -O3) managed to optimize it into:

            <bb 4> [local count: 114492992]:
  _20 = std::basic_istream<char>::operator>> (&cin, &i1);
  std::basic_istream<char>::operator>> (_20, &i2);
  i_22 = i1;
  i2.3_85 = i2;
  if (i_22 > i2.3_85)
    goto <bb 13>; [5.50%]
  else
    goto <bb 5>; [94.50%]

  <bb 5> [local count: 108195877]:
  _5 = i2.3_85 % i_22;
  _6 = i2.3_85 - _5;
  if (_6 > i_22)
    goto <bb 6>; [5.50%]
  else
    goto <bb 13>; [94.50%]

          The compiler deduced that the loop is useless and optimized it away.

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

            Can you please tell how you are getting this kind of output? This doesn't seem like Godbolt.

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

              It's the output from gcc -fdump-tree-optimize. For example, g++ -O2 -fdump-tree-optimize hw.cc will produce a hw.cc.234t.optimized file, which is in "GIMPLE" (GCC IR) and can be viewed with a text editor.

              If you're on Godbolt you can also view it:

              1. Press Add new... button.
              2. Select GCC Tree/RTL output.
              3. Select 234t.optimized in Select a pass... droplist.

              (The pass number 234t may vary in different GCC versions.)

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

          The loop variable (i) is never used so every iteration is exactly the same (and there are no side effects unless the if is true which can only occur once due to break). Therefore the compiler can prove it is safe to remove the loop and leave you with a single if statement.

          → Reply