Solution to a modification of CF1392F — Omkar and Landslide

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

In the original problem, the heights are strictly increasing, as a result, there can be at most one equal pair, leading to a simple solution.

However, what if the heights are non-decreasing, instead of strictly increasing? In this case, there can be more than one equal pair in the final heights. For example, $$$[1,1,2,2,3,3]$$$ will remain the same, in which there are three equal pairs. The fact that there can be more than one equal pairs makes it impossible for us to solve the problem based on the sum and length of the original heights. For example, $$$[4,4,5,5]$$$ and $$$[3,4,5,6]$$$ are all valid heights.

How can we solve this modification?

In the Official Tutorial, it has been proved that the sequence of operations does not matter. So we can assume that when we process the $$$k$$$-th element, the first $$$k-1$$$ elements are already a valid sequence (but might not be in their final form).

Let's consider the difference of a valid sequence. It can only have $$$0$$$ and $$$1$$$. For example, $$$[2,3,3,4]$$$ has difference $$$[1,0,1]$$$. How will the difference change when future slides happen?

We can do some experiments. Supposing there is an infinite hill at the end, we will have:

$$$[2,3,3,4]$$$ ==> $$$[2,3,4,4]$$$ ==> $$$[2,3,4,5]$$$ ==> $$$[3,3,4,5]$$$

And the difference array changes like this:

$$$[,1,0,1]$$$ ==> $$$[,1,1,0]$$$ ==> $$$[,1,1,1]$$$ ==> $$$[,0,1,1]$$$

We can see that the position of $$$0$$$ in the difference array keeps moving backward until it vanishes at the end. Then it will occur again at the front.

In the following, we will call a $$$0$$$ in the difference array a "slot". In the above example, there is only one slot, what about multiple slots?

Let's see another example.

$$$[2,2,3,3,4]$$$ ==> $$$[2,2,3,4,4]$$$ ==> $$$[2,2,3,4,5]$$$ ==> $$$[2,3,3,4,5]$$$ ==> $$$[2,3,4,4,5]$$$ ==> $$$[2,3,4,5,5]$$$ ==> $$$[2,3,4,5,6]$$$

Where the difference array goes like:

$$$[,0,1,0,1]$$$ ==> $$$[,0,1,1,0]$$$ ==> $$$[,0,1,1,1]$$$ ==> $$$[,1,0,1,1]$$$ ==> $$$[,1,1,0,1]$$$ ==> $$$[,1,1,1,0]$$$ ==> $$$[,1,1,1,1]$$$

Rev.	By	When	Δ	Comment
en3	lucifer1004	2020-08-19 13:00:39	15	Tiny change: 'moves one element backward ' -> 'moves one position backward '
en2	lucifer1004	2020-08-19 12:58:48	2857	Version 1.0 (published)
en1	lucifer1004	2020-08-19 12:49:05	2071	Initial revision (saved to drafts)

Rev.

Lang.

When

Comment

en3