931D: Peculiar apple-tree

Claim: if a level has an odd # of apples, it will contribute an apple in the end!!!

Proof: by induction on levels, when we move the apple to the level above, the cancel rule means the oddity is preserved. => at the root level, even means empty, odd means 1 => so all even cases lead to cancel at the root

937D: Sleepy Game

We need to find a path, s.t .

  1. even length

  2. the final node has no outgoing edges

So we assign a node into two cases: arriving at the node, with the oddity of the path traveled so far, and build a graph!!!

So we just do a DFS, and try find one such paths, and also keep track of existance of cycles, so that we can ensure that we can keep at least a draw

940D: Alena And The Heater

for each new digit we processed, we can see that

  1. 11110 case, up can push down ub of r

  2. 00001 case, we can inc ub of l

  3. 11111 case, we can increase lb of r

  4. 00000 case, we can dec up of l

  5. if the last 4 digits are not 0000 or 1111, we can not infer anything

In the end, we take ub of r and lb of l, see if they intersects

946D: Timetable

Official answer uses naive dp, although i doubt it will pass the run time check

950C: Zebras

Simple greedy solution would work

950D: A Leapfrog in the Array

Note that all shift happens between even indices, while start with an odd index

Let’s conside the moment where an odd inde is first “merged” with the band to the right

  1. we know for sure the length of the band to the right

  2. for the odd indices to the right, they haven’t moved yet

The key insight I missed is that, at each step, the move size reduced, and conversely, increased by itself!!!

Proof: in the jump, we go from p + (n - p/2) to p, i.e. the jump length is n - p/2,

so first jump length is 2 * n - from, to 2 * (from - n), the second jump length becomes 4 * n - 2 * from, we can see that the jump length doubles at each step!!!

So that for every even index, we calculate the jump length by reverce, until the jump length is 1 => that is the first “merge” we made, half that is the answer

948D: Perfect Security

Use trie to optimize the O(n^2) solution