Restore Cycles#12783

Restore Cycles (Editorial)

Problem author:	Maryan Shyika
Prepared by:	Maryan Shyika
Tutorial:	Maryan Shyika

Idea

The final score of a person is equal to the maximum value $a_{j}$ a_j among all positions they visit during $x$ days.

First, let us check whether a solution can exist. If for at least one person starting at position $s$ we have

a_{s} > c,

a_s>c,

then already on the first day their score becomes greater than the required value $c$ . In this case, the answer is $- 1$ .

Now group people by their value $c$ . For each such group, divide the people into two types:

Good — people for whom $a_{s} = c$ a_s=c. Such a position already provides the required maximum.
Bad — people for whom $a_{s} < c$ a_s<c. In order for their final score to become equal to $c$ , they have to visit a position with value $a_{i} = c$ a_i=c.

Consider one group with the same value $c$ . We use every position from Good as an anchor of a separate cycle. We can add at most $x - 1$ x-1 positions from Bad to this cycle.

Thus, the length of every such cycle does not exceed $x$ , so every person in it will visit the anchor with value $c$ during $x$ days. At the same time, all other positions containing people in this cycle have values not greater than $c$ , so the final maximum will be exactly $c$ .

If some elements from Bad remain after using all positions from Good, we need to create additional cycles for them. As an anchor for such a cycle, we use a free position without a person for which

a_{i} = c .

a_i=c.

Again, we add at most $x - 1$ x-1 positions from Bad to each such anchor.

If there are not enough free positions with value $c$ , it is impossible to construct a valid permutation, so we output $- 1$ .

Also, if $x = 1$ x=1 and there is at least one position from Bad, the answer is immediately $- 1$ , since such a person cannot reach another position.

After processing all groups, every constructed set of positions

v_{1}, v_{2}, \dots, v_{t}

v_1,v_2,\ldots,v_t

is closed into a cycle:

p_{v_{1}} = v_{2}, p_{v_{2}} = v_{3}, \dots, p_{v_{t}} = v_{1} .

p_{v_1}=v_2,\quad p_{v_2}=v_3,\quad \ldots,\quad p_{v_t}=v_1.

All positions that were not used in any cycle are made fixed points:

p_{i} = i .

p_i=i.

Thus, we obtain a valid permutation for which the final score of every person is equal to the required value $c$ .

The overall time complexity is $O (n lo g n)$ O(n\log n) due to the use of std::map.

The memory complexity is $O (n)$ .

a_{j}

a_{s} > c,

a_{s} = c

a_{s} < c

a_{i} = c

x - 1

a_{i} = c .

x - 1

x = 1

v_{1}, v_{2}, \dots, v_{t}

p_{v_{1}} = v_{2}, p_{v_{2}} = v_{3}, \dots, p_{v_{t}} = v_{1} .

p_{i} = i .

O (n lo g n)