PROBLEM LINK:
Setter: Kasra Mazaheri
Tester: Arshia Soltani
Editorialist: Kasra Mazaheri
DIFFICULTY:
Cakewalk
PREREQUISITES:
Observation
PROBLEM:
Given an array A of length N, you’d like to make all the elements of the array equal using as few operations as possible. In one operation you may take any element and change it’s value to one of it’s neighboring elements (if existing).
QUICK EXPLANATION
- For each element of the array, we will use at most one operation on it.
- All the elements of the array that are left unchanged (no operation is used on them), should be equal.
- As a conclusion of the above observations, we should make all the elements equal to the number that has the most occurrences in order to minimize the number of operations.
EXPLANATION
Let’s assume that in the optimal solution, all the elements will become X. Since we can only change an element’s value to the value of another element of the array, there should be such i that initially A_i = X. Now in order to make all the elements equal to X, we can do the following operations :
- Change the value of A_{i-1} to A_i = X
- Change the value of A_{i-2} to A_{i-1} = X
\ldots - Change the value of A_1 to A_2 = X
And then :
- Change the value of A_{i+1} to A_i = X
- Change the value of A_{i+2} to A_{i+1} = X
\ldots - Change the value of A_N to A_{N-1} = X
It’s easy to see that this way all the elements will become X and we will only use one operation for each element (other than i itself). We can see that if an element is already equal to X, we don’t need to use any operations on it. Thus we only have to change the elements that are not equal to X.
Define Count(X) to be the number of elements of the array A that are equal to X. From the above observations we can see that we need N - Count(X) operations to make all the elements equal to X. Since we want to minimize this value, we should choose such X that the value of Count(X) is maximized.
TIME COMPLEXITY
The time complexity is O(N) or O(N \cdot log(N)) per test case, depending on the implementation.
SOLUTIONS:
Setter's Solution
// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
int main()
{
int q;
scanf("%d", &q);
for (; q; q --)
{
int n, a, Mx = 0;
scanf("%d", &n);
map < int , int > MP;
for (int i = 0; i < n; i ++)
scanf("%d", &a), MP[a] ++;
for (auto X : MP)
Mx = max(Mx, X.second);
printf("%d\n", n - Mx);
}
return 0;
}
Tester's Solution
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
long long gcd(long long a, long long b) {return b == 0 ? a : gcd(b, a % b);}
#define ll int
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=1e2+500;
ll c[maxn];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll q;
cin>>q;
while(q--){
ll n;
cin>>n;
for(ll i=0;i<n;i++){
ll a;
cin>>a;
c[a]++;
}
ll mx=0;
for(ll i=0;i<=100;i++){
mx=max(mx,c[i]);
}
cout<<n-mx<<endl;
for(ll i=0;i<=100;i++){
c[i]=0;
}
}
}
Feel free to share your approach. As usual, suggestions are warmly welcomed.