errorgorn's blog

By errorgorn, 2 years ago, In English

Here is a simple problem. Count the number of array $$$A$$$ of non-negative integers size $$$N$$$ such that $$$\sum\limits_{i=1}^{N} A_i \cdot i=K$$$. Where $$$N,K \leq 5000$$$. Find the answer modulo $$$1000000007$$$.

I unfortunately cannot share the link to a submissions page as it is on a private local judge.

Update: I have asked judge devs of the local judge, the compile command is g++ -O2 -o {compiledName} {sourceName} -m64 -static -std=gnu++14 -lm -s -w -Wall -Wshadow -fmax-errors=512

But anyways, here is the problem.

AC code
WA code

For the testcase $$$N=K=2500$$$ (which is the partition number for $$$2500$$$) the answer should be $$$729287017$$$, but the WA code gives $$$735199643$$$ (testing on atcoder custom invocation with C++ (GCC 9.2.1) ). This makes zero sense because the only thing different between these two codes is just the commented assert.

After further investigating, I managed to figure out that the problem was something to do with #pragma GCC optimize("O3").

Below is another set of AC and WA codes where the only difference is #pragma GCC optimize("O3").

AC code
WA code

I was super confused when I found out about this so I told kostia244. He told me that perhaps it is overflow. And indeed, after changing int memo[5005] to long long memo[5005], it is AC.

AC code with long long

So now we are both scratching our heads at this weird behaviour. Does anyone have an idea why this happens? Should we include macros in our codes by default now?

Sorry for tagging but ToxicPie9 nor

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

»
2 years ago, # |
  Vote: I like it +34 Vote: I do not like it

I don't want to sound like someone who calls every UB a compiler bug, but I don't see anything illegal in your code. Also I can reproduce this locally with g++-8 and g++-9, but it works correctly with g++-10 or g++-11, so maybe they actually fixed something?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    I too have strong reasons to believe it's a compiler bug (and I suspect it is related to optimizations that are triggered due to the array's memory layout). For instance, replacing the array with a vector of size $$$\max(n, k) + 1$$$ (or even 5005) is fine. Replacing it by a local array of size 5005 is also buggy.

»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

To me this looks like a compiler bug in the O3 optimizer in GCC 9. I could only reproduce it with GCC 9, but not 10 or 11.

»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

I further reduced the testcase using C-Vise and submitted a report to GCC bugzilla: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103615

AtCoder uses GCC 9.2, but there were two bugfix releases from the 9.x branch since then: changes from 9.2 to 9.3 and changes from 9.3 to 9.4. Let's say, if GCC developers backport the necessary bugfix to GCC 9.5, how likely are AtCoder and the other online judges to upgrade their old 9.x compilers?