Блог пользователя M.Mahdi

Автор M.Mahdi, 11 лет назад, По-английски

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++?

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

»
11 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

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

»
11 лет назад, # |
  Проголосовать: нравится +70 Проголосовать: не нравится

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.

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

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

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

      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.

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

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.net/contest/369/submission/5311155

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    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!