Till the start of contest we have to expect that.

Tried to create such case during intermission but couldn't. Hoping problem setter was devilish enough to come up with one :)

And even more would fail if there is same for modulo 2^64

Looking at final standings — there are no such tests; however, still curious about existence of such test for given constants:)

Here's one such test:

0,0,2,0,1,0,3,0,0,0,
2,0,0,1,0,3,0,0,0,2,
0,0,1,0,0,0,3,3,0,0,
0,1,0,0,0,3,3,0,0,0,
1,0,0,0,0,4,0,0,2,0,
0,0,0,4,4,0,0,0,1,3,
0,0,0,0,0,3,0,0,0,0,
0,6,0,0,6,0,0,0,0,1,
3,0,0,0,0,0,3,0,0,0,
0,0,6,0,0,6,0,0,0,0

The answer is 152·2³² + 1.

Turns out there's a much simpler test, which is: (33 times 0), (2 times 33), (33 times 0).

There's exactly one way to put the 33's in different groups, and 32 ways to put them in the same group, each one yielding 2³³ ways to deal with the remaining zeros, so the answer will be 1 + 2³⁸.

Answering to ainu7's question below: there is a similar test of size 130 (and it can be even optimized to 128) that causes 2⁶⁴ modulo solutions to fail. While this construction is good, it's not clear whether this is the shortest test with such property.

450 hint: min cut

900 hint: look at matrix with 0, 1, 2 as rows (Bob's) and R, P, S as columns (Alice's) and what happens if 0 was Rock, 1 was Paper, but now 0 is Paper and 1 is Rock

450 is mincut (which is equal to maxflow, as you need only value of cut, not cut itself).

For every value X, add edge with capacity 0 from S to X, if X can be assigned to Bob, or edge with capacity INF, if it can't.

For every value X, add edge with capacity 0 frot X to T, if X can be assigned to Alice, or edge with capacity INF, if it can't.

For every pair of values X, Y, add edge between X and Y with capacity C, where C is penalty for assigning X and Y to different players.

Now you need to find mincut between S and T in given graph. You'll assign all vertices in same component with S to Alice, and all other vertices to Bob.

P.S. I can't understand why they gave this problem, it is pretty standard task, reduction to maxflow is well-known, and lot of users are using prewritten implementation of maxflow, therefore main part of solution can be done with copy-paste very fast.

You can see the editorial for div1 900 here. (spoiler alert!)

Please tell if something is unclear. :)

I use DP like this.

Let dp[i][j][k] be the minimum difficulty of the first i pitch, where pitch from i — j + 1 to i are given to Alice if k = 0, to Bob if k = 1.

Then with dp[i][j][k] we can update to dp[i + 1][j + 1][k] and dp[i + 1][1][1 — k].

The answer is min(dp[n][j][0], dp[n][j][1])