Codeforces Round #541 Editorial

Let's classify marked squares to two groups. First group will consist of cells that are neighboring by corner to ship. There are exactly $$$5$$$ such corners. Second group will consist of cells that are neighboring by side to ship. Number of such squares is equal to length of perimeter of a ship.

Thus answer is equal to $$$2 \cdot (w_1 + h1 + h2) + 4$$$.

Since some scores are already fixed, we only have "liberty" in between of them.

One can easily see, that basically we need to solve the problem between each neighboring pair and then sum all the answers (it may turn out, that for a fixed score, it will be accounted twice, in the "left" pair and in the "right", but it's easy to subtract it back).

How to solve the problem between score $$$(a, b)$$$ and $$$(c, d)$$$? We want to put in the middle as much pairs $$$(x, x)$$$ as possible. So we have $$$a \le x \le c$$$ and $$$b \le x \le d$$$, hence $$$\max(a, b) \le x \le \min(c, d)$$$, it's easy to count the number of such $$$x$$$'s and you can also see, that there is a goal sequence which achieves all such $$$(x, x)$$$'s together.

The solution is greedy one.

Suppose we have reordered $$$a_i$$$, so that $$$a_i \le a_{i + 1}$$$.

Then I claim that the answer can be built as follows:

First write all elements with even indices and then all elements with odd indices in reversed order.

For example, if $$$n = 5$$$: we get $$$a_1, a_3, a_5 \mid a_4, a_2$$$ and if $$$n = 6$$$: $$$a_1, a_3, a_5 \mid a_6, a_4, a_2$$$.

One can "check on many tests" that it works in practice, but here goes the proof:

Note, that the solution provides answer which is at most $$$\max a_{i + 2} - a_{i}$$$.

Let's show that for every $$$i$$$, answer must be at least $$$a_{i + 2} - a_{i}$$$. To do this, draw all $$$a_i$$$'s as a graph. Then the solution to the problem is some Hamiltonian cycle.

Let's suppose that $$$a_{i + 2} - a_{i}$$$ is prohibited to us (and all jumps containing this one).

Red denotes the forbidden jumps. One can easily see, that $$$a_{i+1}$$$ is a cut point, and no hamiltonian cycle is possible. This concludes our proof!

This task has different possible solutions.

One of them is as follows — make a DSU for all $$$n+m$$$ dishes (Disjoint Set Union data structure, https://en.wikipedia.org/wiki/Disjoint-set_data_structure), and unite all dishes that should be evaluated with the same number according to the table (unite dishes $$$i$$$ and $$$n+j$$$ if $$$a_{ij}$$$ equals "=".

Then create graph. We will iterate over all $$$i$$$, $$$j$$$ and add a directed edge in some direction between the sets, corresponding to the $$$i$$$ and $$$j$$$, if one of them is better, then the other.

In case the graph has a self-loop or cycle, it's easy to see that the answer is impossible. Otherwise assign numbers, where the vertex gets the least number greater than the vertex it goes to. This is the answer.

Let's notice, that the string multiplication is associative, that is $$$(a \cdot b) \cdot c = a \cdot (b \cdot c)$$$. So instead of left "$$$(a \cdot b) \cdot c$$$" given in statement, let's use "$$$a \cdot (b \cdot c)$$$"

That is, we have $$$s_n$$$, then go to $$$s_{n-1} \cdot s_n$$$, then $$$s_{n - 2} \cdot (s_{n-1} \cdot s_n)$$$ and so on.

One can also solve the problem without observing the associativity property and going with $$$s_1 \to s_1 \cdot s_2 \to (s_1 \cdot s_2) \cdot s_3$$$ and so on. However there is one caveat. Since the string grows very fast, "an answer" will grow as well.

And while you are promised that the answer is at most $$$10^9$$$, observe the following situtation: $$$s_1, s_2, ..., s_{100}$$$ are "aaaaaaaaaaaaaaaaaaaa", which makes an answer quite large, but if you add a $$$s_{101}$$$ equal to "c" it collides to a mere $$$1$$$, so it requires some careful handling, basically store for every value $$$x$$$ you want value $$$\min(x, 10^9)$$$. Going in another direction has an advantage, that if some value is large it will stay large for life, so since answer is $$$10^9$$$ no overflows will happen.

Now back to the suggested solution.

Let's proceed as $$$s_n \to s_{n-1} \cdot s_n \to s_{n - 2} \cdot (s_{n-1} \cdot s_n)$$$ and so on.

Note, that it's enough to store not whole the current string $$$s_{i} \cdot \ldots \cdot s_n$$$, but just some basic information about. Let's simply store:

• The length of the largest substring of a single character
• Whether the string consists of the single character or not
• The left and the right character of it
• The length of the prefix, which consists of a single character and the same for the suffix.

It's easy to see that if you know such values for some string $$$s_{i} \cdot \ldots \cdot s_n$$$, you can also compute it for $$$s_{i - 1} \cdot s_{i} \cdot \ldots \cdot s_n$$$ (here, the brackets are assumed as in $$$a \cdot (b \cdot c)$$$).

In this problem we are given a disjoint set union process with $$$n - 1$$$ steps, merging $$$n$$$ initial 1-element sets into one $$$n$$$-element set. We have to put elements into a linear array of cells, so that the cells to be joined at each step of the process were immediate neighbours (i.e. not separated by other cells).

This problem can be solved in $$$O(n\log n)$$$ or in $$$O(n\alpha(n))$$$ (where $$$\alpha(n)$$$ is the inverse Ackermann function) via standard disjoint-set data structure, additionally storing lists of elements in each set.

The simplest solution is based on a set-size version of rank heuristic:

• storing mapping from item to id (representative) of its current set, and the inverse mapping from set to the list of its elements
• when we have to merge two sets $$$A$$$ and $$$B$$$, we make the smaller set part of the larger set and update mappings, assigning new set ids for elements in $$$O(min(|A|, |B|))$$$ and concatenating the lists (can be done in $$$O(1)$$$ or in $$$O(min(|A|, |B|))$$$)

This gives us $$$O(n\log n)$$$: element can not change its set more than $$$log n$$$ times, because the change leads to (at least) doubling of the element's set size.

In order to get $$$O(n\alpha(n))$$$, we have to use the disjoint set structure with both path compression and rank heuristics, plus concatenation of lists should be done in $$$O(1)$$$.

This problem can be solved using dynamic programming technique.

Let $$$dp_i$$$ be minimum cost to fall first $$$i$$$ dominoes. If $$$i$$$-th domino was dropped to the right $$$dp_i = min(dp_j + c_i)$$$ over such $$$j$$$ that dropped $$$i$$$-th domino will fall all dominoes from $$$j + 1$$$ to $$$i$$$. Otherwise, some other domino was dropped to the right and fell domino $$$i$$$. Then $$$dp_i = min(dp_{j - 1} + c_j)$$$ other such $$$j$$$, that $$$j$$$-th domino dropped to the right will fall $$$i$$$-th domino. Such solution works in $$$O(m^2)$$$.

We need to speed up this solution. We need to find possible $$$j$$$ for each $$$i$$$ faster. At first let's notice, that possible $$$j$$$'s forms subsegments, so we need just find most right $$$j$$$. This can be done using stack technique like finding nearest element greater than current.

Another part of the solution, we need to optimize is taking range minimum query of $$$dp$$$'s. That can be easily done using segment tree technique or fenwick tree technique, however it requires $$$O(log m)$$$ time per query which is too slow. To make it faster we can use stack technique again! Let's maintain stack of increasing values of $$$dp_i$$$ (or $$$dp_i + c_i$$$, depending on case). Because segments on which we are taking minimum are nested or non-intersecting we can always drop all values after the optimum for each query. Using amortized analysis technique, we can see that such solution works in $$$O(m)$$$.