Max or Min#12799

Max or Min (Editorial)

[1]#1

Author:

Roman Bilyi

Developer:

Roman Bilyi

Editorialist:

Stanislav Bezkorovainyi

Before solving the problem for all from to , let's try to solve a problem for a fixed number .

It's obvious, that if there is no element of array that is equal to , then the answer is .

Otherwise, the answer always exists. Let's prove it.

At first, let's replace all the elements in the array by the following rule:

  • If a_i < k, then a_i := -1 (replace a_i with )

  • If a_i = k, then a_i := 0 (replace a_i with ).

  • If a_i > k, then a_i := 1 (replace a_i with )

Now, the problem is equivalent to the previous one, we just have to make elements of the array equal to .

Let's call zebra a subarray of the array that consists of altering numbers and . Examples of zebras are: , , [-1,1,-1], , [1,-1,1,-1,1,-1,1], [-1,1,-1,1,-1,1,-1,1,-1]. Note, that since the array is arranged in a circle, arrays like, for example, [1,-1,-1,-1] have zebra [-1,1,-1] that starts from the last element.

Since the elements are arranged in a circle, then cyclical shifts do not change it. Let's make necessary number of cyclical shifts to left, so that the first element of the array is equal to . Now we know for sure, that there are no zebras that come through index . It helps, because it ensures that finding all zebras in our cyclical string is now equivalent to finding all zebras in the string after the shifts. Why do we even need to find these zebras? We'll come to that later.

Let's define as a multiset of lengths of the longest sequential zebras. How we build it:

At first we stick the pointer at position . Then the following algorithm works until p \leq n:

  • If a_p = 0, then increase by . Repeat the algorithm.

  • Otherwise, let be the length of the longest possible zebra that starts from position . Add to and increase by . Repeat the algorithm.

For example, if was [k, -1, 1, -1, -1, 1, k, -1, -1], then Z(a) = \{3,2,1,1\} (the longest zebra that starts on position has length , the longest zebra that starts on position has length , the longest zebras that start on positions and have length ).

Let's define function cnt(a, c) that returns number of occurrences of in the array . Let's define as a function that takes the array as an argument and returns the following value:

f(a) = cnt(a,-1) + cnt(a,1) + \sum_{z \in Z(a)}\Bigl\lfloor \frac{z}{2}\Bigr\rfloor

In other words, equals to number of elements that are not equal to plus the sum of floored lengths of zebras divided by two.

Claim. The answer is equal to .

Those, who don't want to read lengthy proofs can skip to How to implement it? section. For those, who want to read the proof, here it is:

Proof.

  • Claim. f(a) = 0 if and only if all the elements of the array are equal to .

    Proof. If all the elements are equal to , then cnt(a,-1) = cnt(a,1) = 0 and there are definitely no zebras in the array, so f(a) = 0. It works in the other direction too: if f(a) = 0, then cnt(a,-1) + cnt(a,1) = 0, so there are no elements that are not equal to , i.e. all of the elements of the array are equal to .

    What it gives us? It means that our problem is equivalent to problem of reducing value of of our initial array to in as few operations as possible.

  • Claim. If we can transform our array into array in one operation, then f(b) \geq f(a)-1. In other words, we can not reduce the value of the function more than by one in an operation.

    Proof. At first, we should notice, that an operation that changes value of the element that is equal to only increases value of cnt(a,-1) + cnt(a,1), thus f(b) > f(a) if was obtained by changing value of an element in the array that is equal to .

    Now it is left to prove that changing value of an element that is equal to either or can not reduce the value of the function more than by one. I'll show you why changing an element that is equal to can not do this. The proof for is very similar.

    Let's suppose that a_i = 1 for some . Now let's look at all possible triples [a_{i-1}, a_i, a_{i+1}] (since the array is cyclical a_0 = a_n, a_{n+1} = a_1). There are possible triples:

    • [1,1,1]. We can not change a_i at all.

    • [-1,1,1]. We can make a_i equal to . Even though a_i might belong to a zebra, it is easy to proof that changing it to won't affect by more, than .

    • [1,1,-1]. The same as the previous one.

    • [-1,1,-1]. We can make a_i equal to . It doesn't change cnt(a,-1) + cnt(a,1), but it is obvious that a_i belongs to some zebra that starts on position p < i. By setting value of a_i as we "split" this zebra into two zebras which start at positions and i+1. Let's say that their lengths are len_1 and len_2 respectively. The length of the zebra before the split is len_1 + len_2 + 1 (it included a_i). Now, f(b) = f(a) - \big\lfloor \frac{len_1+len_2+1}{2}\bigr\rfloor + \bigl\lfloor \frac{len_1}{2}\bigr\rfloor + \bigl\lfloor \frac{len_2}{2}\bigr\rfloor. It is easy to prove, that \bigl\lfloor \frac{len_1+len_2+1}{2}\bigr\rfloor - \bigl\lfloor \frac{len_1}{2}\bigr\rfloor - \bigl\lfloor \frac{len_2}{2}\bigr\rfloor is either equal to or . In order to prove this, you should test how expanding flooring brackets will work for cases, when: len_1 is even and len_2 is even, len_1 is even and len_2 is odd, len_1 is odd and len_2 is even, and both len_1 and len_2 are odd.

    • [0,1,1]. We can make a_i equal to . It will only affect cnt(a,1), because of that f(b) = f(a)-1.

    • [1,1,0]. The same as the previous one.

    • [0,1,0]. We can make a_i equal to . f(b) = f(a) - 1 as well.

    • [-1,1,0]. We can make a_i equal to . It will not affect cnt(a,-1)+cnt(a,1). It is also obvious that a_i belongs to some zebra. Let's suppose that it's length is . f(b) = f(a) - \big\lfloor \frac{len}{2}\bigr\rfloor + \big\lfloor \frac{len-1}{2}\bigr\rfloor. It is obvious, that \big\lfloor \frac{len}{2}\bigr\rfloor - \big\lfloor \frac{len-1}{2}\bigr\rfloor is equal to either or .

    • [0,1,-1]. The same as the previous one.

    What it gives us? Now we know that is the lower bound of number of operations needed to make all the elements of the array equal to .

  • Claim. It is always possible to solve the problem in operations.

    Proof. We do it using the following algorithm:

    1. Look through all positions such that a_i = 0 and a_{i-1} \neq 0. If there are no such positions, then all the elements of the array are equal to and thus the algorithm should stop. If such position exists, then proceed to step 2.

    2. If [a_{i-2}, a_{i-1}, a_i] is equal to either [0, -1, 0], [0,1,0], [-1,-1,0] or [1,1,0], then we set value a_{i-1} as , which will obviously decrease the value of . After that, return to step 1. If the array is not equal to neither of the mentioned above, then don't do anything and go to step 3.

    3. Now we know, that [a_{i-2}, a_{i-1}, a_i] is equal to either [1,-1,0] or [-1,1,0]. It is obvious, that a_{i-2} belongs to some zebra of length greater than . By applying or operation respectively we can make a_{i-2} have same value as a_{i-1}.

      If the zebra's length is greater, then , then after making a_{i-1} and a_{i-2} equal, a_{i-3}, a_{i-2}, a_{i-1} will have same values, thus, the zebra will no longer contain elements a_{i-2} and a_{i-1}, so it's length will be decreased by , so it's length divided by two will be decreased by one. This is why will be decreased by .

      If the zebra's length is equal to , then, obviously, the zebra contains only elements a_{i-1} and a_{i-2}. If they are equal, then the zebra no longer exists at all. Thus, will be decreased by 1.

      After making a_{i-2} equal to a_{i-1}, return to step 1.

    What it gives us? Now we know, that is the lower bound of our answer and it is always achievable. Thus, is the answer.

How to implement it? It is obvious how to find in for a fixed . But we need to solve the problem for all from to .

Let's remember for each value from to on which positions they occur. And set all a_i := 1.

Let's define arrays , and value :

  • Let's say that an element on a position belongs to some zebra, then the value of p_i is the position from which the zebra starts. If a_i = 0, then p_i = i.

  • If there is a zebra that starts from position , then the value of len_i is equal to length of that zebra. If no zebra starts from position , then len_i = 0.

  • is equal to \sum_{z \in Z(a)}\bigl\lfloor \frac{z}{2}\bigr\rfloor, assuming that our array is not cyclical (i.e we do not count zebras that contain both positions and ).

Let's also define procedure upd(pos, val). upd(pos,val) changes value of a_{pos} to in a way that sustains all the arrays and and value valid.

Now, let's make all p_i := 1 and thus all len_i := 1, sumz := 0. Now, we iterate from to , solving the problem for every possible in the following way:

  • If the value has no occurences, then the answer for this is .

  • Otherwise, proceed:

    • Now, we should iterate over all positions , where occurred and call upd(i,0).

    • Now, answer ans_k for is equal to number of positions, where doesn't occur plus . But we need to make sure the zebra that contains both elements on positions and (if it exists) is counted too. If a_1 = 0 or a_n = 0 or a_n = a_1, then the zebra doesn't exist at all, so we don't need to modify ans_k. Otherwise, the zebra exists and we need to modify ans_k in the following way: ans_k := ans_k - \bigl\lfloor \frac{len_1}{2}\bigr\rfloor - \bigl\lfloor \frac{len_{p_n}}{2}\bigr\rfloor + \bigl\lfloor \frac{len_1 + len_{p_n}}{2}\bigr\rfloor. This modifying is equivalent to deleting zebras that start on positions and p_n (this is the zebra that contains ) and adding zebra of length len_1 + len_{p_n}.

    • Now, we should iterate over all positions , where occurred and call upd(i,-1).

    This algorithm will always work, because, since we iterate in ascending order, once position is assigned we will never have to change it's value again.

The only question is how to implement upd(pos,val). In order to simplify it's implementation, I will use the fact if val = 0, then a_{pos} previously was , and if val = -1, then a_{pos} previously was .

  • If val = 0, then do the following:

    • If p_{pos} + len_{p_{pos}} - 1 = pos (i.e the zebra, that contains position ends on it), then we should decrease by \bigl\lfloor \frac{len_{p_{pos}}}{2}\bigr\rfloor - \bigl\lfloor \frac{len_{p_{pos}-1}}{2}\bigr\rfloor and decrease len_{p_{pos}} by one.

    • Otherwise, the zebra doen't end on position , so transforming a_{pos} into will split it. Decrease by \bigl\lfloor \frac{len_{p_{pos}}}{2}\bigr\rfloor - \bigl\lfloor \frac{pos - p_{pos}}{2}\bigr\rfloor - \bigl\lfloor \frac{p_{pos} + len_{p_{pos}} - 1 - pos}{2}\bigr\rfloor (basicaly, we just split the zebra). Assign p_i := pos+1 for all from pos+1 to p_{pos} + len_{p_{pos}} - 1. So now, we set len_{pos+1} := p_{pos} + len_{p_{pos}} - 1 - pos,len_{p_{pos}} := pos - p_{pos}.

    • In the end, in both cases, set p_{pos} := pos, len_{pos} := 0, a_{pos} := 0.

  • If val = -1, then do the following:

    • At first, set a_{pos} := -1, len_{pos} := 1, p_{pos} := pos.

    • If pos < n and a_{pos+1} = 1, then there is a zebra that starts form position that contains zebra that starts from position pos+1 as a suffix. Increase by \bigl\lfloor \frac{len_{pos+1}+1}{2}\bigr\rfloor - \bigl\lfloor \frac{len_{pos+1}}{2}\bigr\rfloor. Set p_i := pos for all from pos + 1 to pos + len_{pos+1}. Set len_{pos} := len_{pos+1}+1, len_{pos+1} := 0.

    • If pos > 1 and a_{pos-1} = 1, then there is a zebra that starts from position p_{pos-1} that has zebra that starts from position as a suffix. Increase by \bigl\lfloor \frac{len_{p_{pos-1}} + len_{pos}}{2}\bigr\rfloor - \bigl\lfloor \frac{len_{p_{pos-1}}}{2}\bigr\rfloor - \bigl\lfloor \frac{len_{pos}}{2}\bigr\rfloor. Set p_i := p_{pos-1} for all from to pos + len_{pos} - 1. Set len_{p_{pos-1}} := len_{p_{pos-1}} + len_{pos}, len_{pos} := 0.

In order to assign some value on a segment in O(\log n) you can use Segment Tree (you can read more about this data structure here https://cp-algorithms.com/data\_structures/segment\_tree.html). Since upd(pos, val) is called exactly times for each , then the procedure is called times. Every call is done in O(\log n), thus, the final time complexity is O(n \log n).