Neru's Lost Connection (Editorial)

Solution

First, let us calculate the initial value of the connection:

Then we will not search for the new value directly. Instead, we will search for the maximum increase after two permutations.

Consider one segment of length $4$ starting at position $s$.

After permuting the elements on this segment, only the edges near this segment change:

If some edge does not exist because it goes outside the array, we simply do not take it into account.

Since the length of the segment is $4$, we can iterate over all its permutations. There are only 4! = 24 of them.

For each starting position $s$, we calculate delta_s — the maximum increase of the value if we permute only the segment [s,s+3].

Now we need to choose two segments.

There are two cases.

First case: there is at least one position between the segments.

If the first segment starts at $i$, the second one starts at $j$, and j-i \ge 5, then the edges affected by them do not intersect.

Therefore, the total increase is equal to:

To find the maximum quickly, we will maintain a prefix maximum for delta_i.

Second case: the segments are adjacent.

This is the case when j=i+4.

Then the segments do not intersect, but there is one common edge between them:

This edge depends on both permutations at the same time, so we cannot simply add delta_i + delta_j.

For this case, we store additional values separately.

For each segment, we will know:

• the best value of the left part if a certain element becomes the last element of the segment;

• the best value of the right part if a certain element becomes the first element of the segment.

Then, for two adjacent segments, we only need to iterate over which element is the last one in the first segment and which element is the first one in the second segment. There are only 4 \cdot 4 such options.

After that, the answer is equal to the initial value plus the maximum increase found.

Example

In the first example, we can choose the segments $p[\mathrm{1..4}]$ and $p[\mathrm{5..8}]$.

After permuting them, the array can become:

Then the value of the connection is equal to:

Complexity

For each segment of length $4$, we iterate over $24$ permutations.

For adjacent segments, we additionally iterate over 4 \cdot 4 options.

All these numbers are constants, so the total complexity of the solution is $O(n)$.