PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: shauryabhalla0
Tester & Editorialist: iceknight1093
DIFFICULTY:
2754
PREREQUISITES:
None
PROBLEM:
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.
EXPLANATION:
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.
Proof
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.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
// #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;
cin>>n>>k;
vector<int> a(n);
for(int i=0; i<n; i++) cin>>a[i];
sort(all(a));
if(n == 1){
cout<<0<<'\n';
return;
}
if(n<4){
if(a[0] == a[n-1]){
cout<<k<<'\n';
return;
}
cout<<0<<'\n';
return;
}
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(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout<<setprecision(15)<<fixed;
// freopen("zinput.in","r",stdin);
// freopen("zoutput.out","w",stdout);
int tt;
cin>>tt;
// for(int i=1; i<=tt; i++){
// cout<<"Case #"<<i<<": ";
// solve();
// }
while(tt--){
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)
else:
distinct = len(set(a))
ans = 0
while distinct < 2 + (n - 2)//3:
ans += k
distinct += 1
print(ans)