C: Suppose you know that "a lot" of points are on one line (let's say, over half). Can you find a simple way of finding that line?

D2: The same observation as for D1 — we just need to find the final positions of the balls, because we know they will be in sorted order. Now suppose we already launched $$$k$$$ balls, and they have positions $$$a_1, \ldots, a_k$$$. A new ball comes in with energy $$$x$$$ — how does that affect the sequence? My hint is instead of looking at $$$a_i$$$, look at $$$b_i := a_i - i$$$ (assuming $$$a_i$$$ is sorted).

Zixiang Zhou (duality) solved d2 in interesting way, 2nd position on scoreboard, very short and simple, but I don't understand idea

For D2, I have an idea that is slightly different from the Official Solution.

Instead of keeping track of where the stones are, I keep track of where the spaces are.

Initially there are infinitely many spaces, from 0 to +inf. When a stone is thrown with energy E. The coordinate of the left most E + 1 + i spaces (i is the index of the stone, 0-based) will decrease by 1. For example, after a stone of energy 4 was thrown, the spaces are now at -1, 0, 1, 2, 3, 5, 6, 7, 8, .... If we again throw a new stone with energy 6, then the spaces are now at -2, -1, 0, 1, 2, 4, 5, 6, 8, 9, ....

Decreasing a prefix of the array can be time consuming, but we can transform this array into a new array that represent the difference between adjacent elements.

For example, -1, 0, 1, 2, 3, 5, 6, 7, 8, ... becomes -1, 1, 1, 1, 1, 2, 1, 1, 1, ...

and -2, -1, 0, 1, 2, 4, 5, 6, 8, 9, ... becomes -2, 1, 1, 1, 1, 2, 1, 1, 2, 1, ...

Decreaseing a prefix of the array becomes $$$O(1)$$$. Also, most of the entries have value 1, so we can only keep track of the positions where value isn't 1.

After we finish processing the spaces, we can easily reconstruct the position of these stones. See the following Python3 code for more details.

T = int(input())

for cas in range(1, T + 1):
    N, G = map(int, input().split())

    spaces = {}
    spaces[0] = 0
    for i in range(N):
        E = int(input())
        spaces[0] -= 1
        if E + i + 1 not in spaces:
            spaces[E + i + 1] = 2
        else:
            spaces[E + i + 1] += 1

    diff = sorted(spaces.items())

    stones = []
    pos = diff[0][1]
    for i in range(1, len(diff)):
        leftpos = pos + diff[i][0] - diff[i - 1][0]
        pos = leftpos + diff[i][1] - 1
        stones += list(range(leftpos, pos))

    stones = [(abs(stones[i] - G), N - i) for i in range(N)]
    dist, index = min(stones)
    print(f"Case #{cas}: {index} {dist}")

Here's a video where I explain my solutions, for anyone interested.

For C, I just followed a randomised approach. I chose 2 distinct points at random (600, 300, 100) times and then ran a checker to maximize my answer.

(600, 300, 100) I.e. I submitted 100 iters one first (was scared of the 6m TL) but then I had enough window to submit the 300 iters output, and then 600 iters output as well.

is C duplicate? Feels like I've seen it almost exactly before

My solution for D2 was somewhat different from the official solution. Each time you throw a ball with power $$$E_i$$$, it ends up at the $$$E_i^{th}$$$ empty position, and all the balls within this range will become shifted to the left. You can represent the number line as a binary array of length $$$N$$$, and maintain it as $$$\sqrt{N}$$$ blocks of size $$$\sqrt{N}$$$ each, with each block represented by a queue. When a ball completely passes over a block (remaining power $$$>$$$ num zeroes), you can shift the balls by popping the front of the queue, and pushing 0 to the back. If a ball stops in the middle of a block, you can manually calculate the resulting state in $$$O(\sqrt{N})$$$ time. Each query runs in $$$O(\sqrt{N})$$$ time, and the total time for all queries is $$$O(Q \sqrt{N})$$$ time, which is good enough to pass.

I solved C, I shuffled the array of given points then the if the answer is $$$n/2$$$ or more then the answer is quite easy as you can just output n. But if the answer is lesser than $$$n/2$$$ then the probability of a point not belonging in the line that minimices m is $$$<0.5$$$.

So i look for the first $$$40$$$ random points and save the best m they could achieve giving a prob of $$$0.5^{40}$$$ which is fairly small.