Sorry for such a title. But I believe this topic will interest a lot of people. (When writing this post, I am informed that this stage would be unrated. Nevertheless, I decide to post this. After all, I paid a lot of effort in it.)

This passage is about the Problem J — Hand Cricket on this stage. My team believe that EVERY "passed" submission in this problem is wrong and we can offer a hacking case for these submissions (and probably for the standard solution).

If you haven't seen the problem description, here it is:

Hacking Case

If you just wonder what is our hacking case, here it is:

3
100 100 1
1
1 3 0

If you try some passed submissions on this case, they all give $$$371894957$$$ as their answer, which is $$$\frac{100}{51}\bmod 998244353$$$ . The strategy chosen by these submissions are actually $$$(p_1,p_2,p_3)=(\frac{1}{102},\frac{1}{102},\frac{100}{102}), (q_1,q_2,q_3)=(\frac{1}{102},\frac{1}{102},\frac{100}{102})$$$ .

However, there's clearly a better solution: For Alice, she can choose $$$(p_1,p_2,p_3)=(\frac{1}{2},\frac{1}{2},0)$$$ . In that way, no matter what strategy Bob chooses, Alice is guaranteed to gain at least $$$50$$$ points, which is far larger than the answer mentioned above. Actually, the equilibrium here is $$$(p_1,p_2,p_3)=(\frac{1}{2},\frac{1}{2},0),(q_1,q_2,q_3)=(\frac{1}{2},\frac{1}{2},0)$$$ , rather than the answer provided by the "correct answer".

What happened?

We ignore the $$$K_i$$$ in the problem statement and let it be $$$0$$$, and we try to answer just a single query.

In that way, we just need to figure out what is the best strategies of Alice and Bob when the subarray is fixed.

Let's say the elements of this subarray are $$$[v_1,v_2,\dots,v_k]$$$ , and Alice chooses his strategy as $$$(p_1,p_2,\dots,p_k)$$$ , Bob chooses his strategy as $$$(q_1,q_2,\dots,q_k)$$$ .

Alice tries to solve this optimization problem: $$$\max_{(p_1,p_2,\dots,p_k)}\sum\limits_{i=1}^k v_ip_i(1-q_i)$$$

Bob tries to solve this optimization problem: $$$\min_{(q_1,q_2,\dots,q_k)}\sum\limits_{i=1}^k v_ip_i(1-q_i)$$$

Both equations are linear, so it seems quite easy.

For Alice, if she knew about $$$(q_1,q_2,\dots,q_k)$$$, she could find the maximum value of $$$v_i(1-q_i)$$$ and distribute her probability on those $$$i'$$$-s such that $$$v_{i'}(1-q_{i'})$$$ reaches this maximum. (Statement 1)

Same for Bob. If he knew about $$$(p_1,p_2,\dots,p_k)$$$, she could find the minimum value of $$$v_ip_i$$$ and distribute his probability on those $$$i'$$$-s such that $$$v_{i'}p_{i'}$$$ reaches this minimum. (Statement 2)

So far, so good, right? But we don't actually know which $$$i'$$$-s to consider . (And the hypothesis made by a lot of teams is that probability should be distributed in each $$$i=1,2,\dots,k$$$, which is just not true.)

Let's say in the final equilibrium, we distribute the probability over a subset $$$i_1,i_2,\dots,i_t\ (t\geq 1)$$$ . Then we can say: $$$p_{i_1}\gt 0, p_{i_2}\gt 0, \dots, p_{i_t}\gt 0$$$ .

Then, from what we have discussed (Statement 1), $$$v_{i_1}(1-q_{i_1}),v_{i_2}(1-q_{i_2}),\dots, v_{i_2}(1-q_{i_2})$$$ all reach maximum, and are therefore the same. So $$$v_{i_1}(1-q_{i_1})=v_{i_2}(1-q_{i_2})=\dots=v_{i_t}(1-q_{i_t})$$$ .

And, for other $$$i$$$ not in $$${i_1,i_2,\dots,i_t}$$$ , Bob has no reason to give probability on any of them, because Alice will never choose them, so $$$q_{i_1}+q_{i_2}+\dots+q_{i_t}=1$$$ , that is, $$$(1-q_{i_1})+(1-q_{i_2})+\dots+(1-q_{i_t})=t-1$$$ .

From these equations, we can get that $$$1-q_{i_k}=(t-1)\frac{\frac{1}{v_k}}{\sum\limits_{j=1}^t\frac{1}{v_j}}\gt 0\ (1\leq k\leq t)$$$ .

Therefore, from what we have discussed (Statement 2), $$$v_{i_1}p_{i_1},v_{i_2}p_{i_2},\dots,v_{i_t}p_{i_t}$$$ reach maximum. So we have $$$v_{i_1}p_{i_1}=v_{i_2}p_{i_2}=\dots=v_{i_t}p_{i_t}$$$ . And we have $$$p_{i_1}+p_{i_2}+\dots+p_{i_t}=1$$$ 。

From these equations, we can get that $$$p_{i_k}=\frac{\frac{1}{v_k}}{\sum\limits_{j=1}^t\frac{1}{v_j}}\ (1\leq k\leq t)$$$ .

And we use these results to get the expectation of the final gain for Alice:

$$$\sum\limits_{k=1}^t \left(v_{i_k}\times\frac{\frac{1}{v_k}}{\sum\limits_{j=1}^t\frac{1}{v_j}}\times(t-1)\frac{\frac{1}{v_k}}{\sum\limits_{j=1}^t\frac{1}{v_j}}\right)=\frac{t-1}{\sum\limits_{j=1}^t\frac{1}{v_j}}$$$ .

So, we should choose the largest $$$t$$$ $$$v_j$$$-s to maximize this value. However, $$$t$$$ is yet to be determined, and it doesn't seem to have an easy way to find the best $$$t$$$ . And comparisons between results of different $$$t$$$-s without precision loss are seemingly quite difficult for me.

Some comments

There is one way to make this problem solvable: Reduce the problem to one query and return a real value for each query, not something about modulo. Then, we can iterate over the number of numbers to choose and we add those small numbers.

Our team spent quite long hours trying to get a glympse of this problem's solution, only to find the answers of others are just wrong. It is quite upset for us.

But there are more things about this problem. Here, instinct tells us that we don't have much reason to ignore some options. But logic tells something different. So careful analysis can be the key.

So, maybe, Anti-Instinct is yet another AI we should never ignore.