Please read the new rule regarding the restriction on the use of AI tools. ×

hxano's blog

By hxano, history, 4 weeks ago, In English

I was solving 1839D - Ball Sorting which was a standard DP problem, when I submitted and got WA on test 1. This was so strange to me since I just pasted the input into my own IDE and the outputs were identical. But sure enough, the moment I submitted the same exact solution, the output was different. I had to spam multiple submissions onto Codeforces to see what went wrong.

WA soluion vs AC solution

280230092 280230005

The only difference between these two pieces of code were ++n; a[n]=n; and a[++n]=n;. At first I thought, shouldn't these have the exact same effect? That's what my compiler told me!

After another WA on test 1-to-debug submission, I realised that it is possible that Codeforces' compiler had put the original value of $$$n$$$ into some temporary memory first, and only then update $$$n$$$ and put the temporary value back into the array.

I have used this kind of assignment a[++n]=n so many times, I'm surprised that only now I'm discovering this! Which is so dangerous because imagine the devastation this could have caused me in offline contests where you only get one chance.

Is it bad practice to put any thing but a single variable into the index of an array? I hope to learn more from all of you.

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

»
4 weeks ago, # |
  Vote: I like it -55 Vote: I do not like it

I think ++n increases the value first, while n++ increases the value later. That's the difference.

»
4 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

I believe this is UB. You can read more about it in the link below. It uses a similar case a[i] = i++; as an example of UB.

https://en.m.wikipedia.org/wiki/Sequence_point

»
4 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

In a[++n] = n, first right hand expression is calculated then left hand is calculated, so let's say n was equal to 5 earlier, this expression iss then equivalent to

a[6] = 5 and sets n to 6;

instead if you use the expression

a[n] = ++n;

which sets n to 6 first, which is equivalent to a[6] = 6 if n was 5 initially.

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

    Is the standard that RHS is evaluated before LHS? I thought it was undefined. Do you have a reference?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      https://en.wikipedia.org/wiki/Operators_in_C_and_C%2B%2B

      Under precedence order, you can see that associativity for assignment operator is from right to left.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +17 Vote: I do not like it

        This is not what associativity means. Associativity is about whether a = b = c is treated as a = (b = c) or (a = b) = c. The fact that the associativity is right-to-left does not by itself imply anything about the order in which a, b and c are evaluated.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      https://en.cppreference.com/w/cpp/language/eval_order

      19) In every simple assignment expression E1 = E2 and every compound assignment expression E1 @= E2, every value computation and side effect of E2 is sequenced before every value computation and side effect of E1. (since C++17)

      It is standard since C++17, but undefined behavior in C++14 and earlier versions.

»
4 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

As per my research and knowledge, this happens primarily because, the programming languages handle these operations internally is different. For example, the same statements may work for other languages like Java.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It's possible that Codeforces is compiling with a different compiler or different version than you are using locally. I'm not entirely sure, but I don't think that such behavior is strictly defined. Also, compilers perform a lot of optimization. Any of these factors could cause what you are seeing here.