You can find the editorial and my solutions here: https://github.com/cgy4ever/CF228

389A - Лиса и игра с числами

First we know that: in the optimal solution, all number will be equal: otherwise we can pick a and b (a < b) then do b = b — a, it will make the answer better.

Then we need an observation: after each operation, the GCD (Greatest common divisor) of all number will remain same. It can be proved by this lemma: if g is a divisor of all number of x[], then after the operation, g is still the divisor of these numbers, and vice versa.

So in the end, all number will become the GCD of x[].

Another solution that can pass is: While there exist x[i] > x[j], then do x[i] -= x[j]. We can select arbitrary i and j if there exist more than 1 choice.

389B - Лиса и крест

Let's define the first # of a shape is the cell contain # that have the lexicographical smallest coordinate. Then the first # of a cross is the top one.

Then let x be the first # of the given board. (If the board is empty, then we can draw it with zero crosses.) x must be covered by a cross, and x must be the first # of the cross. (You can try 4 other positions, it will cause a lexicographical smaller # in the board than x)

So we try to cover this x use one cross, if it leads some part of the cross covers a '.', then there will be no solution. If not, we just reduce the number of # in the board by 4, we can do this again and again.

389C - Лиса и коробки / 388A - Лиса и коробки

We need some observation:

1. There exists an optimal solution such that: in any pile, the box on the higher position will have a smaller strength.

2. Let k be the minimal number of piles, then there exists an optimal solution such that: The height of all piles is n/k or n/k+1 (if n%k=0, then all of them have the height n/k).

We can prove them by exchange argument: from an optimal solution, swap the boxes in it to make above property holds, and we can ensure it will remain valid while swapping.

Then for a given k, we can check whether there exist a solution: the i-th (indexed from 0) smallest strength needs to be at least i/k.

So we can do binary search (or just enumerate, since n is only 100) on k.

389D - Лиса и минимальный путь / 388B - Лиса и минимальный путь

First we need to know how to calculate the number of different shortest paths from vertex 1 to vertex 2: it can be done by dp: dp[1] = 1, dp[v] = sum{dp[t] | dist(1,t) = dist(1,v) — 1}, then dp[2] is our answer.

We need to do dp layer by layer. (first we consider vertexes have distance 1 to node 1, then vertexes have distance 2 to node 1 and so on.) So we can construct the graph layer by layer, and link edges to control the dp value of it.

My solution is construct the answer by binary express: If k is 19, then we need some vertexes in previous layer such that the dp value is 16, 2 and 1. So we just need a way to construct layer with dp value equals to 2^k.

In the first layer, it contains one node: 1, it has the dp value 1. In the next layer, we can construct 2 nodes, with dp value equals to 1. (We use [1 1] to denote it). And the next layer is [1 1 2], then [1 1 2 4], [1 1 2 4 8] and so on. So we need about 30 layers such that gets all 2^k where k < 30. It uses about 500 nodes.

389E - Лиса и игра в карты / 388C - Лиса и игра в карты

First let's consider the case which all piles have even size. In this case, we can prove: in the optimal play, Ciel will gets all top most half cards of each pile, and Jiro gets the remain cards.

We can prove by these facts: Ciel have a strategy to ensure she can get this outcome and Jiro also have a strategy to ensure this outcome. (For Jiro this strategy is easy: just pick the card from pile that Ciel have just picked. For Ciel it's a little bit harder.)

Why we can conclude they are both the optimal strategy? Ciel just can't win more, because if she played with Jiro with above strategy, Jiro will get the bottom half of each pile.

Then we come back with cases that contain odd size piles. The result is: for odd size pile, Ciel will get the top (s-1)/2 cards and Jiro will get the bottom (s-1)/2 cards. Then what about the middle one? Let's denote S is all such middle cards. Then we define a reduced game: In each turn, they pick one card from S. The optimal play for this game is easy: Ciel gets the max one, and Jiro gets the 2nd largest one, and Ciel gets the 3rd largest one and so on.

We can prove Ciel have a strategy to get: all top half parts + cards she will get in the optimal play in the reduced game. And Jiro also have a strategy to get: all bottom half parts + cards he will get in the optimal play in the reduced game. And these strategy are optimal.

388D - Лиса и идеальные наборы

A perfect set correspond to a linear space, so we can use base to represent it. We do the Gauss–Jordan elimination of vectors in that set, and can get an unique base. (Note that we need to to the all process of Gauss–Jordan elimination, including the elimination after it reached upper triangular)

And we can construct the bases bit by bit from higher bit to lower, for a bit:

1. We can add a vector to the base such that the bit is the highest bit of that vector. And at this time, all other vector will have 0 in this bit.

2. Otherwise we need to assign this bit of each vector already in the base. If now we have k vector, then we have 2^k choices.

And when we do this, we need to know what's the maximal vector in this space. It's not hard:

1. If we add a vector, then in the maximal vector, this bit will be 1.

2. Otherwise, if we don't have any vector in base yet, then this bit will be 0. Otherwise there will be 2^(k-1) choices results in this bit of maximal vector will be 0, and 2^(k-1) choices results in 1.

So we can solve this task by DP bit by bit.

388E - Лиса и метеоритный дождь

All tasks beside this are very easy to code. And this one focus on implementation.

We can represent the orbit of each meteor by a line in 3D space. (we use an axis to represent the time, and two axis to represent the position on the plane.)

Then the problem becomes: we have some lines in 3D space (they are not complete coincide), find a largest clique such that each pair of lines touch at some point.

We need this observation: If there are 3 lines in the optimal clique, and these 3 lines are not share a common point, then all line in this clique will on a plane.

By using this observation, we only need to consider 2 cases:

1. All lines in the clique have a common point.

2. All lines in the clique are on the same plane.

Both are easy tasks in theory, but it needs some coding.

There are two ways:

1. Use integer anywhere. Note that the coordinates of intersection can be rational number, but can't be irrational, so we could do this. We can use some way to encode the plane, direction.

2. Use floating number. To count same number of points, we can sort (x, y, z) by using the following compare function: if (abs(A.x — B.x) > eps){return A.x < B.x} otherwise { if(abs(A.y-B.y)>eps){return A.y < B.y} otherwise return A.z < B.z}.