Don't doublepost.

For odd d, you can color diagonals. For even d, this pattern works:

RRGGGGGGGGYYBBBBBBBBRRGGGGGGGGYYBBBBBBBB
RRRGGGGGGYYYYBBBBBBRRRRGGGGGGYYYYBBBBBBR
RRRRGGGGYYYYYYBBBBRRRRRRGGGGYYYYYYBBBBRR
RRRRRGGYYYYYYYYBBRRRRRRRRGGYYYYYYYYBBRRR
RRRRRRYYYYYYYYYYRRRRRRRRRRYYYYYYYYYYRRRR
RRRRRBBYYYYYYYYGGRRRRRRRRBBYYYYYYYYGGRRR
RRRRBBBBYYYYYYGGGGRRRRRRBBBBYYYYYYGGGGRR
RRRBBBBBBYYYYGGGGGGRRRRBBBBBBYYYYGGGGGGR
RRBBBBBBBBYYGGGGGGGGRRBBBBBBBBYYGGGGGGGG
GBBBBBBBBBBGGGGGGGGGGBBBBBBBBBBGGGGGGGGG
YYBBBBBBBBRRGGGGGGGGYYBBBBBBBBRRGGGGGGGG
YYYBBBBBBRRRRGGGGGGYYYYBBBBBBRRRRGGGGGGY
YYYYBBBBRRRRRRGGGGYYYYYYBBBBRRRRRRGGGGYY
YYYYYBBRRRRRRRRGGYYYYYYYYBBRRRRRRRRGGYYY
YYYYYYRRRRRRRRRRYYYYYYYYYYRRRRRRRRRRYYYY

I'm lucky I got my internet connection to work 2 minutes before the contest ended...

When D is odd, do checkerboard pattern with just two colours.

When D is even, tile the plane using a diamond of size D - 1 × D.

After squeezing leftmost 3 and 4 using 2 moves each you are left with sequence 5 9 2 6 5 3 and 6 moves. Then you make

[1 (x5)]    [1 (x9)]    [1 (x2)] [1 (x6)] [1 (x5)] [1 (x3)]
[1 (x3), 2] [2, 1 (x7)] [1 (x2)] [1 (x6)] [1 (x5)] [1 (x3)]
[1 (x3), 2] [2, 1 (x7)] [1 (x2)] [1, 1, 2, 2] [2, 1 (x3)] [1 (x3)]
[2, 3] [3, 2 (x3)] [2] [2, 4] [3, 2] [2, 1] (squeezed all except last one)
[5] [5, 4] [2] [2, 4] [3, 2] [2, 1]
[5] [9] [2] [2, 4] [3, 2] [2, 1]
[5] [9] [2] [6] [5] [3]

I hope the format is understandable

It's enough to give a problemset on colorings to 7th grade pupils in a mathcamp once

I started with something like

AABBAABBAABB
AABBAABBAABB
CCDDCCDDCCDD
CCDDCCDDCCDD
AABBAABBAABB
AABBAABBAABB

using rather standard idea "let's split everything into blocks so that distance within one block is not large enough and distance between blocks is too large", and then it took me an hour to understand that all I need to make first distance smaller than second is to rotate everything by 45 degrees.

One reason: If d = 2k, then the points (0,k), (0,-k), (k,0), and (-k,0) are pairwise distance d from each other, so they should all be different colors.

You can use a trick which is similar to 763B - Тимофей и прямоугольники

The main idea is to combine two boards. The first board should have every two cells with |x+y|-|x'+y'|=d different in color. The second board should have every two cells with |x-y|-|x'-y'|=d different in color. Then you can combine the two boards with 2 different colors to one board with 4 different colors. The code is very simple.

my submission

I thought about it in greedy way. I process groups from left to right and for every prefix I want to know the answer for prefix and for that best answer I also want to know greatest number of operations that can affect next slime (<=> operations that included last slime). One can see that these can easily be computed by some caseology and that it is not possible that if we allow ourselves one more operation on prefix then number of operations that we can use for suffix will grow by more than 1, what we need for correctness.

Let b_i = ceil(log a_i).

1. Notice that if b₁ > b₂ > ... > b_n then answer is b₁.

2. Think about greedy. Result may look smth like this.

I can explain my solution. You'd better try somewhere else, for example, several comments above, here is nice and short code, while my solution does nothing greedily and seems to be formally proved, but seems more complicated to me than others' solutions (however, I'll use sentences like "it's clear that ..." and "there is clearly no sense to ...", so the text below isn't completely formal).

First, consider the initial slimes. They can be divided into groups (i-th of them having a_i consecutive slimes) so that no two slimes from different groups will never be combined. We watch the numbers of slimes in these groups, we start from (a₁, ..., a_n) and end with (1, 1, ..., 1) (to clarify I remind that there are always n numbers).

Each operation consists of choosing a subsegment [l, r], dividing each a_i with l < i < r by two (thus we require them to be even before this) and turning each into an arbitrary number from .

Next we notice that each operation doesn't change popcounts of internal elements of the corresponding subsegment. This means that each a_i which is initially not a power of two should be the left-/rightmost element of a subsegment at least once.

Assume that all a_i-s are powers of two. Consider (b_i)_i = 1ⁿ instead where . Each operation now is decreasing by one on a subsegment. It's not hard to prove that the answer to the problem is

Indeed, one can imagine something like a Young tableau of b (except b isn't sorted) and then erase common edges of the i-th and the (i + 1)-st columns thus obtaining a division into horizontal rectangles representing the required subsegments.

Now let's see that each a_i which is not a power of two has and the upper (if we imagine it with positive gravity) unit square of a Young tableau is cursed (that means, it should keep one of its edges present and not erased).

One can wonder why the uppermost unit square. Well, if or if min(b_i - 1, b_i + 1) < b_i then such an edge will exist anyway, for example, the uppermost one. Otherwise we add 1 to the answer anyway no matter which square is cursed, so let this be the uppermost.

However, if two adjacent columns have the same height and each of them contains a cursed square then we can keep one edge for both of them and thus increase the answer by 1 instead of 2, so we should handle such partition of cursed columns into pairs.

Here is my code. One can see that actually there is no need to divide the initial array to 1-free regions manually, get(a) should return the answer as well.