TCO19 Algorithm Rounds are not related to regional qualification! Round 1a, Round 1b and Members who got a bye are eligible for this!

Regionals have their separate qualification — This year performance in the period of Feb-April was used for qualifying members for the regionals :)

It take me several minutes to correct condition number_less_than_goal $$$< (n + 1) / 2$$$, number_greater_than_goal $$$\le n / 2$$$ :)

I found the second problem to be much easier than the first one

Just try all divisors of $$$n$$$. For each divisor $$$d$$$, call the same algorithm recursively on $$$n/d-1$$$. During steps other than the first, don't consider $$$d=1$$$.

In fact, this problem is OEIS A167439.

Let test N and N-1 separately, so we can assume that there's no 1 in sequence.

Take a look at $$$a_0$$$, each consequent number is divisible by $$$a_0$$$, so N is also divisible by $$$a_0$$$.

Now if we divide everything by $$$a_0$$$ we'll receive another sequence with sum of $$$\frac{N}{a_0}$$$ and first element 1. Let's drop that 1 and solve the problem for $$$\frac{N}{a_0} - 1$$$. Just build dp on top of that.

clist.by :>

I managed to find it on TCO website :) https://tco19.topcoder.com/algorithm/algorithm-rules

Outline (I'm on the phone now):

Obviously, optimal strategy is same for both players.

If d is max difference, you will never play more than 2d+1 because playing 1 is at least as good for all possible choices of the other player. (This is the main observation you needed.)

Then, write linear equations for the 2d+1 probabilities using "principle of indifference", there is a unique solution. (Some more proofs needed to argue correctness.)

Based on discussion with Egor.

Basic lemma from game theory: For all $$$p_k > 0$$$ we should have expected winning of exactly $$$0$$$ against pure strategy "say $$$k$$$".

$$$p_1$$$ is not zero, otherwise we can shift everything to the left. So, $$$\sum_{k=2}^{d+1} p_k \ge 1/2$$$. Now it is easy to see that for all $$$k > 2d+1$$$ $$$p_k=0$$$ (because we are certainly winning strictly more than 0 against this pure strategy). Now we can see than $$$p_k=p_{2d+2-k}$$$ (because everything is symmetric), and we have $$$d+1$$$ variables and $$$d+1$$$ linear equations.

Right. Also looks like getting positive score was enough to qualify to Round 3 from all prev rounds. So you weren't actually competing against other people, only against yourself :D

Upd. not really, only 200 people qualify to Round 3, I thought it was 250

That would be a clear violation of the rules!