CHNGIT - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

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. :slight_smile:

2 Likes

Can anyone tell me whats wrong in my code.Please !!!

#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t–)
{
int n,arr[100],ct=0;
cin>>n;

    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
       
    }
  int m,q=0;
  for(int i=1;i<n;i++)
  {  
      m=arr[i];
     for(int j=i+1;j<n;j++)
  {
      if(m==arr[j])
    
      q=arr[j];
  }
    
}
if(q==0)
{
    cout<<1<<endl;
}
else
{
for(int i=0;i<n;i++)
{
    if(arr[i]!=q)
    {
        arr[i]=q;
        ct++;
    }
}
  cout<<ct<<endl;
    
}

    
}
// your code goes here
return 0;

}

Please either format your code or link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

Okay…Sure.

Can you please check from All Submissions.I recently submitted it.

That’s some impressive laziness, there :slight_smile:

Link to the submission: https://www.codechef.com/viewsolution/28466556

Consider the testcase:

1
1
1
2 Likes

Got it…Thank you so much.
and it was’t laziness…I don’t know how to format the code :sweat_smile: so
Thanks though!!!

1 Like

There’s a link to a Tutorial that shows how to format it in my initial post :slight_smile:

Nevertheless, you’re welcome :slight_smile:

1 Like

i just took array of size 100(the limit of N as mentioned in the question). Keeping the rest of the things same.

      int n;
      cin>>n;
      int a[100];
      fill(a,a+100,0);
      int x;
      foi(n){
              cin>>x;
              a[x-1]+=1;
          }
          int ma=*max_element(a,a+100);
          cout<<n-ma<<endl;

it reduced space complexity.

Hey…can you tell me whats wrong now:frowning_face:
Link to the submission: https://www.codechef.com/viewsolution/28466896

It fails on the testcase:

1
7
4 4 3 3 2 3 2

(the answer should be 4).

hmm…got it finally!!!
should have been used map only.well Thanks again!!!:slightly_smiling_face:

1 Like

Here is my submission in c++ :

#include <bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--)
	{
	     int n;
	     cin>>n;
	     //int arr[n];
	     map<int,int >m;
	     for(int i=0;i<n;i++)
	     {
	          int a;
	          cin>>a;
	          m[a]++;
	     }
	     int max_recur_cnt=0;
	     
	     for(auto i : m)
	     {
	          max_recur_cnt = max(max_recur_cnt,i.second);
	     }
	     
	     cout<<(n-max_recur_cnt)<<endl;
	   
          
	}
	
	return 0;
}

I’m having trouble finding error in this code: https://www.codechef.com/viewsolution/28469142

Custom input is giving correct answer, but getting WA on submission. Can someone please provide test case for which this code is not producing correct output.

How is the code different form this: https://www.codechef.com/viewsolution/28468971

Consider the testcase:

1 
7
30 100 88 74 92 89 46

Edit:

Since a_i can be 100, you have an out-of-bounds access at the line:

a[num]++;

so the behaviour is Undefined.

Edit2:

1
10
100 100 100 100 100 100 100 100 100  2

also gives the wrong answer, even with your AC submission - weak testcases, there :slight_smile:

@vijju123 @kmaaszraa - can we get this testcase added to the Practice version? :slight_smile:

2 Likes

Actually the condition A_i \le N holds in all test cases. I didn’t want to fail any solutions because of this.

I don’t know if my logic is correct or not. Can anyone please help me out, my solution was accepted but after reading this editorial. I found my solution nowhere close to the discussion.

So this is what I did.
I found the frequency of element which has occured the most, say sequence is (1,4,6,1,3,6). So max frequency is 2 be it for 6 or 1 doesn’t matter.
Since we have to find the minimum number of moves so I substract the max frequency from size of sequnce. In above case the size is 6. so minimum number of swappings is 6-2=4

Let’s take One of the given testcase 9 8 1 8
so max frequency is 2 (we are not bothered to find which element has max frequemcy, we just need max frequency) so length is 4
Therefore 4-2=2

Can someone share there thoughts about this approach. It was accepted but still I’m confused if it’s right!

Some one help me with my solution. Sometime, it’s work, but it always runtime error
[https://www.codechef.com/viewsolution/28481127] is my solution(https://www.codechef.com/viewsolution/28481127)

I think so. But I have a problem, i don’t know how to fix that?

Here’s a random testcase your code fails on:

7
2 
4 1
1
2
2
25 27
1
9
8
32 13 87 33 33 64 37 2
10
3 4 45 16 19 38 32 58 18 28
1
3