Help me in solving MAKEALLEQUAL problem

help
,
1

My issue

i want help for this test case
n = 8 , m = 3
A = [1 2 2 2 4 4 4 7]
Now according to me answer is
choose A5, A6, A7 (means choose all 4’s) => A = [1 2 2 2 7 7 7 7] —> 3 operations
choose A2, A3, A4 (means choose all 2’s) => A = [1 7 7 7 7 7 7 7] —> 5 operations
Choose remaining 1 => A = [7 7 7 7 7 7 7 7] —> 6 operations
So according to me total 14 operations needed
but the answer is 10 why???

My code

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

signed main(){
 ios_base::sync_with_stdio(false);
cin.tie(NULL);
 int t;cin>>t;
 while(t--){
  int n,m;cin>>n>>m;
vector<int> a(n);
 for(auto &i:a) cin>>i;
sort(a.begin(),a.end());
vector<int> inc(n);
 int total = 0;
 int c = 1;
int ans = 0;
 for(int i=n-2; i>=0; --i){
  
      if(i+m<=n-2) total -= inc[i+m];
      ans += a[n-1]-a[i]-total;
       inc[i] = a[n-1]-a[i]-total;
      total += a[n-1]-a[i]-total;
     //   cout<<total<<" "<<ans<<" "<<inc[i]<<" "<<i<<"\n";
     
 }
 cout<<ans<<"\n";
}
 return 0;
}

Problem Link: Make All Equal Practice Coding Problem - CodeChef

2

Here is the proof can be done in 10 operations.

[1,2,2,2,4,4,4,7]
operation 1: choose 1 2 2 => 2,3,3,2,4,4,4,7
operation 2: choose 2 3 2 => 3,4,3,3,4,4,4,7
operation 3: choose 3 3 3 => 4,4,4,4,4,4,4,7
operation 4: choose 4 4 4 => 5,5,5,4,4,4,4,7
operation 5: choose 4 4 4 => 5,5,5,5,5,5,4,7
operation 6: choose 5 5 4 => 6,6,5,5,5,5,5,7
operation 7: choose 5 5 5 => 6,6,6,6,6,5,5,7
operation 8: choose 6 5 5 => 7,6,6,6,6,6,6,7
operation 9: choose 6 6 6 => 7,7,7,7,6,6,6,7
operation 10: choose 6 6 6 => 7,7,7,7,7,7,7,7

Your logic is wrong, you should use summation of differences from maximum element not prefix differences.
You should return maximum of (difference between maximum and minimum element) and (ceiling value of summation/k).

Here is my detailed explaination with solution:
https://www.codechef.com/viewsolution/1035944654

1 Like