M.Mahdi's blog

Suspicious submission
By M.Mahdi, 11 years ago, In English

Hello!
In round #216, I tried to hack this code. As you see, there is a line written this:

int tp = (sa - sk) % (n - k);


If n = k, then the code must get RE because of division by zero. But the code has been accepted!
Can someone explain this behavior of C++?

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

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

How the code passes 19 th test case 1 1 1 1 1 1

in my pc it gets RTE!!! its very mysterious.

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

I have looked through assembly code generated by the compiler and I think I've found the reason. If the first loop in the code is never executed(e.m k == n), it jumps over all the block of code until the loop from 1 to k. So the division does not happen at all. It works only with -O2(or similar) optimization options. Without it this solution gets RE on test 1 1 1 1 1 1.

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

    Why does it jump to there? Maybe there is an important operation in the part between!

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

      For this particular code, when n == k, all the values that might be computed in this skipped block are completely disregarded by further actions. So, it jumps, because there's nothing important actually.

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

Amazing!!!!! Why Above code didn't get RTE ?? Testcase 11 was sufficient for getting RTE !!! Almost same solution Get RTE on test 11 due to division by 0. http://codeforces.me/contest/369/submission/5311155

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

    what i don't get about that code is the line //if(n>k). if this line hadn't been commented out, i think the solution would have been accepted.

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

I don't know, it fails on my compiler too.

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

yo.

an usual for cycle

for(init; condition; increment)
{
    body;
}

an usual assembly for this is:

init;
if(!condition)
    jmp end;
label again:
body;
increment;
if(condition)
    jmp again:
label end:

so basically the conditional check is implemented 2 times (depending on compiler flags). (the compiler cound have used a jmp check: after the init, to jump right to the end, to the conditional, and jump back if it needs to start the cycle.) if there is 2 copies of the conditionals, the first means do we need to start the cycle. in this case initialization of variable tp might be delayed until this point, because tp is only used inside this cycle.

later it will be overwritten, previous value does not matter. compilers are too smart i guess :)

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

when it comes to here:for(int i=k+1; i<=n; i++) because k+1>n so the pc will ignore the body and jump to next. so it won't get RE.... BTW I find that if n and k are double, it won't get RE either.

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

    but the line int tp = (sa-sk) % (n-k); does not lie inside the body of the for loop, so the code should get RE!

    → Reply