The model solution for NERC Finals 2025–2026, Problem B is wrong.
The solution claims an optimal strategy: always use $$$\max(a)$$$ to attack $$$\max(b)$$$ (simulate with max-heaps).
Counterexample:
a = [3,3,4]b = [1,5,6].
If Alice follows the model strategy, she plays $$$4 \to 6$$$, so $$$b$$$ becomes $$$[1,2,5]$$$. Then Bob plays $$$5 \to 4$$$ and destroys Alice's $$$4$$$, leaving $$$a=[3,3]$$$, and Bob can force a win from there.
However, Alice has a winning move: play $$$4 \to 5$$$ first, turning $$$b$$$ into $$$[1,1,6]$$$. From this position Alice can force a win (verified by exhaustive game-tree search).
So always attack $$$\max(b)$$$ with $$$\max(a)$$$ is not optimal for this test.
The proof in the editorial contains the step:
Therefore, if we replace the element being attacked with $$$max(b)$$$ ... we can replace $$$b_j$$$ with $$$max(b)$$$ without worsening the situation.
This replacement is unjustified, and the counterexample above shows it is false.
I wonder if anyone noticed the author's solution was incorrect during the contest. gpt identified a contradiction when provided the problem statement and the solution.
In the mirror contest, I noticed that any proofs I make for this part doesn’t connect, but given the solve counts it does not make sense to spend 10+ minutes to help the authors debug their problems when it is a 2 minute AC.
Insane find! It is hard to 100% fair evaluate an impact of this error, but at least, it seems like (MAYBE IT IS POSSIBLE BUT NOT GUARANTEED)SpbSU Log'n'roll would have qualified to WF instead of SpbSU I See Personal Computer, if problem B didnt exist. https://nerc.itmo.ru/archive/2025/standings.html 11th and 12th places, 10min penalty diff overall, and about 40min diff on problem B. Waiting for official steatement.
At first glance, this seems to be true. But if task B did not exist at all, the "I See Personal Computer" team would not have spent approximately 30 minutes on it and would have saved a penalty of 150 minutes for the 5 subsequent tasks, while the "Log'n'roll" team would not have spent 14 minutes on it and would have saved 56 minutes for the subsequent 4 tasks. Therefore, it is not entirely accurate to focus solely on the difference in the penalty for task B.
Well you are assuming that they spent all that time solely on B which maybe is not true (and also three people can solve different tasks so yeah maybe someone was solving next task in that time). But yes I agree that situation is very unclear, and it is not guaranteed that Log'n'roll would have won without B, we simply dont know many important details. And it will indeed be unfair to I See Personal Computer if the decision is simple remove problem B. And also unfair to Log'n'roll if everything will be left as it its. There really is not any good solution at this point, so I wonder what jury will do.
I assume you got the "14 minutes spent on B" for Log'n'roll as a difference between AC on A and B. However, for your team the number would be 13 minutes then, as a difference between your AC on M and B. Considering their 1 wrong attempt they "have lost" 76 minutes, while your team only 65. Not saying this analysis is correct, the contest would've been much different much with one of the easier task removed but we should be honest here.
Yes, I agree with the error in the calculations. Indeed, the difference between the neighboring submission times for the "I See Personal Computer" team is 13 minutes. However, my main concern was that if we simply looked at the difference in the penalty for task B, the contest would have been completely different, especially considering that it is the second most difficult task. It seems that you share this concern to some extent.
If problem B did not exist at all we would have completely different scoreboard since team AltF4 would not spend 100 attempts on B and easily AK
1) Wow!! Superb, huge respect to you!
2) Just out of curiosity, did you find this counterexample manually, or by stress-testing, or by AI?
By AI)
I was reading the problems on my phone and tried to solve problems “ideologically” (just come up with the idea). I asked GPT to stress-test the greedy strategy, and it found this counterexample.
After that I tried to reason about it myself, but couldn’t come up with solution. Then I gave up and opened the editorial and noticed it claims exactly the greedy strategy that GPT had just broken.
As a person who participated in the NEF, something didn’t sit right with this greedy approach. We didn’t solve this problem due to some unfortunate team miscommunication (the editorial’s idea was proposed, but we moved on to other tasks, and I for some reason thought that we found a counter-example, so I didn’t bother with trying to write the code). Quite relieved to see that my gut feeling was right after all! Now I am curious about what they gonna do with this problem and results in particular.
By the way, what is the optimal strategy, then? Because now that the main solution has been proven incorrect, the problem seems much more complicated, since I don’t think there is a strategy comparable to the original in terms of simplicity. It was one of the easiest problems of the contest (the second most solved problem), so it will be a shame if the real solution is significantly harder than the intended one.
Just a heads up for anyone thinking this counter example isn't valid. After this blog got published, the problem statement of 2181B - Battle of Arrays was changed from
to
You can find the original problem statement by downloading the pdf under contest materials.
Huh, so that probably means this was the intended statement (I highly doubt that they are trying to cover up a messed-up model solution, because the problems should have been thoroughly reviewed by many renowned programmers). Though in this case, especially for the semifinals of ICPC, the problem sounds too obvious (why would I ever choose not the maximum element from my array if I can only hit the maximum of my opponent?). I know that this problem should be on the easier side, but, like, this straightforward? I wonder if that was really the original statement that for some reason got replaced with incorrect version.
Looking at the tutorial, I would say that it kinda implies the possibility of attacking not the maximum of the second array, so I may argue that this change is a hot fix rather that the statement as it was originally composed.
Most testers would just try greedy, get AC, and think they've solved the problem (just like what the contestants did). It is really the responisbility of the judges to catch errors like this one.
I think the fix of the problem statement is simply a quick bodge. The fix forces the player to pick $$$y$$$ greedily, which basically means the player is forced to play greedily, making greedy obviously optimal. It does not change the fact that the original problem was wrong.
The strangest thing is why they didn't have a brute force solution added in Polygon. And if they did have it added — then why there were no stress tests in the main testset. There are testcases enabled and test amount is unlikely a reason to not make one or two.
My opinion is that the task was fixed for the Codeforces archive usage. Maybe it really does not have a clear solution in the original form, so they stated that explicitly to keep it solvable and formally correct.
I don't believe the coverup theory. Hundreds of participants saw the problem live, and many of them took their printed statements home. Moreover, PDF version pinned in CF remains unmodified.
So, in my opinion the solution idea really was a misbelief by judges. Well, a lot of contestants believed into that idea as well (us included).
An agruably simpler counter example is
Alice playing the 11 into the 14 is winning for Alice, but playing the 11 into the 15 results in a loss.
To see this, note that after two moves, Alice array will always be
a = [10](assuming Bob plays optimally). And at that point, greedy is optimal for both players. So the only real choice is Alice's first turn.Great catch. Thanks. We've given you the credit for finding the issue in the update problem tutorial: https://nerc.itmo.ru/archive/2025/nef-2025-tutorial.pdf