Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: shauryabhalla0
Tester & Editorialist: iceknight1093






An array is said to be good if no two of its adjacent elements are equal, and it has at most local maximum and one local minimum.

You’re given an array A. In one move, you can:

  • Choose indices i and j, and set A_i to A_j for a cost of 0.
  • Choose index i, and set A_i to any integer for a cost of K.

Find the minimum number of moves to obtain an array that can be rearranged into a good array.


Suppose A is a good array. Let’s make some observations about it.

Let \text{mx} denote the maximum element of A, and \text{mn} denote the minimum.
Notice that if either \text{mx} or \text{mn} appear in the middle of A, they’ll be a local maximum/minimum (because adjacent elements can’t be equal).
This immediately limits us to at most three occurrences of each one: the endpoints of the array, and one in the middle.

Further, between any two occurrences of \text{mx} there will be a local minimum (do you see why?); and a similar constraint holds for two occurrences of \text{mn}.
This tells us that there can’t be \geq 3 occurrences of \text{mx} in the array; since then we’d have two local minimums and that isn’t allowed.

So, each of \text{mx} and \text{mn} can occur at most twice in the array; taking up upto 4 positions.
Also, two of these four positions are the endpoints of the array.
What about the other elements?

A bit of thinking should tell you that any element that isn’t \text{mn} or \text{mx} can occur at most 3 times.


The above observations drastically limit the number of distinct elements present in the array.
Upto four elements are minimums/maximums; and every other distinct element can occur at most thrice.

So, if there are x distinct elements (that aren’t the maximum/minimum), we have the inequality 4 + 3x \geq N, or x \geq \left\lceil \frac{N-4}{3} \right\rceil.
In total, this means A must have at least 2 + \left\lceil \frac{N-4}{3} \right\rceil distinct elements.

Now, let’s relate this to the operations we have.

  • The first operation allows us to set A_i to some other A_j.
    This cannot increase the number of distinct elements present, but it can reduce the frequency of one element and increase the frequency of another.
  • The second operation allows us to set A_i to any integer.
    This allows us to add a new distinct element to the array.

Recall from above that we have a lower bound on the number of distinct elements required.
So, we must perform the second operation till that lower bound is reached.
If we do this y times, the cost incurred is K\cdot y.
Finding y is easy: count the number of distinct elements in A, then see how many more are needed to reach 2 + \left\lceil \frac{N-4}{3} \right\rceil.

Once the lower bound on distinct elements is reached, it can be proved that the first operation is enough to rearrange frequencies so that we hit the required bounds (i.e, minimum and maximum appear at most twice, everything else at most thrice).
The cost here is 0 since the first operation is free.

This solves the problem!

Note that the solution above relies on the fact that N \geq 4, since we subtracted 4 from N.
For N \leq 3, the answers can be special-cased:

  • For N = 1 the answer is always 0
  • For N = 2 and N = 3, the answer is K if all the elements of A are equal, and 0 otherwise.


\mathcal{O}(N) per test case.


Author's code (C++)

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;

#define int long long   
#define all(x) x.begin(), x.end()

// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
typedef unsigned long long ull;
typedef long double lld;

const int N=1e7+2, M=1e5+10, mod=1e9+7, inf = 4e18, moda = 998244353;
const lld pi = 3.141592653589793;

void solve(){
    int n, k;
    vector<int> a(n);
    for(int i=0; i<n; i++) cin>>a[i];

    if(n == 1){

        if(a[0] == a[n-1]){

    int min_count = ceil((lld)(n-4)/3)+2;
    int curr_count = unique(all(a))-a.begin();
    cout<<k*max(0ll, min_count-curr_count)<<'\n';

signed main(){

    cin.tie(0);  cout.tie(0);

    // freopen("","r",stdin);
    // freopen("zoutput.out","w",stdout);

    int tt;

    // for(int i=1; i<=tt; i++){
    //     cout<<"Case #"<<i<<": ";
    //     solve();
    // }


    // solve();
Editorialist's code (Python)
for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    if n == 1: print(0)
    elif n <= 3: print(k if min(a) == max(a) else 0)
        distinct = len(set(a))
        ans = 0
        while distinct < 2 + (n - 2)//3:
            ans += k
            distinct += 1

Can you please refer some more problems like this , where we have to find bounds on our answer and then try to prove that the claimed bound is the best and then also give some strategy to attain that bound. Any site’s question would be fine. I need to up skill myself in such greedy techniques. Thanks in advance

@iceknight1093 see this test case n = 10, k = 2, A = [1,2, 3, 3, 3, 3, 3, 3, 3, 4]. Here number of distinct element is 4 = 2 + ceil((n - 4)/3), i.e., y = 0. So the cost will be 0. But notice mx = 4, mn = 1 but element 3 has occurred 7 times. But we know that every element has to occur at most 3 times. So the cost can not be 0 but according to your algorithm the cost is 0. Please correct me if I am wrong.

Please reread the problem. There is another type of operation which costs nothing.

Yes yes. Actually I misread the cost 0 operation to be swapping but it was A[j] = A[i] but not the other way around. That’s why the misconception has occurred. Thank you so much for resolving the doubt.

I think the proof is missing for this claim. On clicking the given “Proof” section nothing appears in it.