Блог пользователя raja_n

Help regarding hacks
Автор raja_n, история, 4 года назад, По-английски

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?

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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).

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится 
        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.

        → Ответить
        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          → Ответить
        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          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.

          → Ответить
          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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.)

              → Ответить
        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          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.

          → Ответить