CASH - Editorial

Do you know how to prove your solution?

PROBLEM LINK:

Practice
Div-2 Contest

Author: Sahil Chimnani
Tester: Radoslav Dimitrov
Editorialist: William Lin

DIFFICULTY:

Cakewalk

PREREQUISITES:

Greedy, Math

PROBLEM:

Given an array A of length N and an integer K, we need to make all elements of A divisible by K. We can split the array into a prefix and a suffix, move any coins from the prefix to the suffix, and remove any coins from the prefix. Find the minimum number of coins we need to remove.

QUICK EXPLANATION:

The answer is the remainder of the sum of the array divided by k.

EXPLANATION:

Let S be the sum of A. First, we will calculate a theoretical bound for the answer.

Observation 1. We need to remove at least S \mod K coins.

Proof

Note that minimizing the number of coins removed is equivalent to maximizing the number of coins left in the array. How can we bound the maximum possible number of coins left in the array?

After we modify A, we know that each element of A is divisible by K, so the number of coins left must also be divisible by K.

This means that the maximum possible number of coins left must be less than or equal to the greatest multiple of K less than or equal to S.

S minus that greatest multiple is precisely the remainder of S divided by K, which is the minimum number of coins we need to remove.

Now, we have a lower bound for the answer. Does it happen to be the answer?

We could try some small cases, or just submit a program which outputs this lower bound, since Long Challenges don’t have penalties for wrong submissions. In any case, we realize that it is the answer!

Observation 2. There exists a way to remove exactly S \mod K coins.

Proof

Let T=S-\left( S \mod K \right). We want to make sure that we keep at least T coins in the array.

If A_N \ge T, then we can choose the prefix to be the entire array. We will remove coins so that A_N becomes T and all other elements are 0.

Otherwise, A_N < T. We will choose the prefix of N-1 elements, which excludes only A_N. We will move enough coins from the prefix so that A_N becomes T. Note that we will always have enough coins in the prefix to do so since T \le S. Any other coins left in the prefix should be removed.

To conclude, we simply find S and output S \mod K as the answer.

HIDDEN TRAPS

  • The maximum possible value of S can be up to N \cdot 10^9 = 10^{14}, which exceeds the range of 32-bit integers (like int in C++ and Java). Make sure to use 64-bit integers (like long long in C++ & and long in Java)!

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define w(v) cout << #v<<" is : "<<v<<"\n"
using namespace std;



int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	cin >> t;
	while(t--){
		ll n,k;
		cin >> n >> k;
		ll ans = 0;
		for(int i = 0;i < n; i++){
			ll temp;
			cin >> temp;
			ans += temp;
		}
		ans = ans % k;
		cout << ans << "\n";
	}

	return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define endl '\n'
 
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
 
using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
 
int n, k;
int a[MAXN];
 
void read() {
	cin >> n >> k;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] += a[i - 1];
		a[i] %= k;
	}
}
 
void solve() {
	int ans = k;
	for(int i = 0; i <= n; i++) {
		int sec = ((n - i) * 1ll * k - (a[n] - a[i] + k) % k + k) % k;
		chkmin(ans, (k + a[i] - sec) % k);
	}
 
	cout << ans << endl;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	int T;
	cin >> T;
 
	while(T--) {
		read();
		solve();
	}
 
	return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=1e5;
int n, k, a[mxN];

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

	//find the sum of the array
	ll sum=0;
	for(int i=0; i<n; ++i)
		sum+=a[i];
	
	//answer is the remainder of sum divided by k
	cout << sum%k << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	while(t--)
		solve();
}

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

20 Likes

wow the solution is so simple… how did i not think of that

1 Like

You correctly pointed out the hidden trap. Thank You.

2 Likes

I was trying to simulate every step. That was the trap.

3 Likes

Glad that the “hidden traps” section was actually helpful!

7 Likes

Really nice editorials @tmwilliamlin !
Love the short introductions that serve to grab someone’s attention and the detailed editorial that follows smoothly and concisely with examples.
My only suggestion is could you recommend a few similar problems in the post and include links to learn stuff related to the problem, preferably some resource you’d used to learn the topic and found useful?

3 Likes

@tmwilliamlin

Can you please tell me where am I going wrong in this approach? I’m not able to pass all test cases.

#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--){
	    long int n,k;
	    cin>>n>>k;
	    long int a[n];
	    long int i,l,h,s=0,x;
	    for(i=0;i<n;i++) cin>>a[i];
	     l=0;
	     h=n-1;
	    long int sum=0;
	    while(l<=h){
	        x=a[l]%k;
	        sum+=x;
	        while(a[h]%k==0 && l<h) h--;
	          if(l<h){
	              x=a[h]%k;
	          while(k-x<=sum && l<h){
	          x=k-x;
	          sum-=x;
	          h--;
	          }}
	        l++;
	    }
	    cout<<sum<<endl;
	}
	return 0;
}

Yea, I would link similar problems if I actually find any… I don’t recall any problems like this one, though.

1 Like

Can u provide the editorial for RAISINS problem feb challenge div2

I don’t understand what your code is doing. Can you at least give some explanation about your approach, and some proof of why you think it works?

So I am maintaining two indexes, one for the start i.e l and one for the end i.e. h. For every starting index, I take its mod and keep on adding to a variable s(since adding all elements and then taking a mod is essentially similar to taking mod at every individual step). For the last pointer i.e. h I subtract k-a[i]%k from the sum which will be equivalent to subtracting the remainder from the sum(sum-(k-a[i]%k = sum-k+a[i]%k) . It is repeated until l==h and the remainder left is equal to sum.

It seems like an unproven greedy solution, so I wouldn’t be surprised if it doesn’t work.

Test case

1
3 3
2 5 5

Is there a proper mathematical proof for this problem?

That’s literally the main part of this editorial!

4 Likes

There is basic maths that was applied here: the example case wrote 13 in end to confuse you we can also get correct answer if we take out only 6 from the bag which is the remainder left when it is divided by 7.

1 Like

I can only see that you are asking to observe that solution is sum of array divided by k. I was thinking of a more of a proof than observation.

heres my non greedy solution
https://www.codechef.com/viewsolution/29366296

Do I not prove in my editorial that the solution is correct?

Did you know that if you click on the word “proof”, the proof appears?

1 Like

No I didn’t. This was my first contest on codechef. Found it now. Thanks man