First notice that it's basically a NIM game plus you have some heaps that are either A's or B's, let's denote |A| and |B| as the number of stones in heaps that are owned by only A and B respectively. If |A| > |B| A can always win, if |A| < |B| B can always win (these are easy to see), otherwise if |A| = |B| it's a standard NIM game.

Here's my solution for 4th:

If we try to parse the statement, it means counting the number of s, 1 ≤ s ≤ M such that and . Using the definition of ceiling function, such s needs to satisfy:

(k - 1)oe + 1 ≤ s ≤ k × oe

k(of - 1) + 1 ≤ s ≤ k × of.

Note that for each k it's trivial to compute the number of satisfying s, and each such k gives a disjoint range of values. However, trying all possible k is not possible (there could be up to 10⁹ of them) so we need to be more clever.

There are three cases to consider here:

1. If oe < of, then k(of - 1) + 1 ≥ k × oe + 1 > k × oe hence there are no solutions.

2. If oe > of, then k × of < (k - 1)oe + 1 iff oe - 1 < k(oe - of), so we only need to try for k up to (oe - 1) / (oe - of) ≤ oe. Furthermore, when oe is large () we only need to try at most values of k since afterward m < (k - 1)oe + 1, so in total we need to try values of k.

3. If oe = of, we can collapse the two inequalities into max ((k - 1)oe + 1, k(oe - 1) + 1) ≤ s ≤ k × oe or k × oe - min(k, oe) + 1 ≤ s ≤ k × oe. With that there are naturally two smaller cases: k ≤ oe where you just need to sum over all possible ranges (and using the above argument there are at most ranges), and k > oe where all possible values for s work.

Total time complexity is per test case.

My solution is in . Here n = oe.

Let f(x) = ceil(x / ceil(x / n)). The question is how many x from [1..M] satisfies f(x) = V.

When n is big, then observe that on each of the intervals [1, n], [n + 1, 2n], ... function f is increasing. So bin-search in each of the intervals. Time: .

When n is small, then write x = an + r and iterate over r. When r = 0 then f(x) = n. When r > 0 then we have f(x) = ceil(x / (a + 1)) and f(x) = V is giving you lower and upper bound on a.

You are right. This is such a shame. Sincere apologies from my side. Each of setter, tester, and editorialist in the panel missed it. Lesson learned, don't use directions like north, south, east, west, rather left, right, top and down would be better. The problem will be rejudged and your score will be reset to 5. Congrats on solving all the problems :)

It just means test cases are weak, i generated one such test case with 63 nodes complete binary tree having 19 markers numbered 0, 2 markets numbered 1 and 42 markers numbered 2.

Code for generating the above test case.

At least top 3 solutions (including mine) are failing on this test case.