NOCHANGE - Editorial

Do you know how to prove your solution?

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Alexey Zayakin
Tester: Radoslav Dimitrov
Editorialist: William Lin

DIFFICULTY:

Easy

PREREQUISITES:

Math, Observations

PROBLEM:

You are given N different coin types, the i-th worth D_i cents. Find any multiset of coins (or report that none exist) which 1. has a sum greater than P and 2. when we remove any coin in the multiset, the sum becomes smaller than P.

QUICK EXPLANATION:

First, we check that all D_i divide P. If some D_i doesn’t divide P, one multiset is \left\lceil \frac{P}{D_i} \right\rceil coins of type i. Next, we check that D_i divides D_{i+1} for each valid i. If this is not true for some i, a multiset exists using 1 coin of type D_{i+1} and \left\lceil \frac{P-D_{i+1}}{D_i} \right\rceil coins of type D_i. Otherwise, no multiset exists.

EXPLANATION:

The strategy to solving this problem is to work with many small cases until you can figure out which multisets can be formed.

For example, let’s try D=[3] and P=10. We can find that the only multiset which works it taking 4 coins.

After seeing this example and a few other examples, we should be able to notice something:

Observation 1. If there exists a D_i which doesn’t divide P, we can find a multiset.

Proof

Since D_i doesn’t divide P, there doesn’t exist a k such that k\cdot D_i = P. Instead, P is between multiples of D_i, so there exists a k such that k\cdot D_i < P < (k+1)\cdot D_i.

Notice that taking k+1 coins with value D_i gives us a multiset that we want: k+1 coins gives a sum greater than P, but taking only k coins gives a sum less than P.

It only remains to find the value of k+1. We will divide the inequality above by D_i to obtain k < \frac{P}{D_i} < k+1. Since \frac{P}{D_i} cannot be an integer, we realize that k=\left\lfloor \frac{P}{D_i} \right\rfloor and k+1=\left\lceil \frac{P}{D_i} \right\rceil.

From now on, we just need to solve the case in which all D_i divide P. Again, we will work with small cases.

For example, let’s try D=[3, 4] and P=12.

It’s impossible to use just one coin type, so we have to use both coin types. How about, let’s just include 1 coin of value 4 and try to fill the rest of the sum with coins of value 3?

It works in this case if we take 3 coins of value 3. We can work with other small cases, and this strategy of using 1 coin of the bigger value and filling the rest of the sum with coins of the smaller value seems to work. This leads to another observation:

Observation 2. If D_i and D_{i+1} both divide P and D_i doesn’t divide D_{i+1}, we can find a multiset.

Proof

Let’s use 1 coin of value D_{i+1}, so the sum that we have left is P-D_{i+1}.

First, notice that we only need to check if removing 1 coin of value D_i gives a sum less than P, since if removing D_i gives a sum less than P, then removing D_{i+1} will also give a sum less than P.

Next, notice that this is similar to the case in Observation 1: we have a sum S that we need to fill with 1 coin type and we need to make sure that after removing that coin, the sum of the multiset becomes less than S.

From observation 1, we know that we can use \left\lceil \frac{P-D_{i+1}}{D_i} \right\rceil coins of value D_i if D_i doesn’t divide P-D_{i+1}.

It turns out that, whenever D_i doesn’t divide D_{i+1}, D_i will not divide P-D_{i+1}.

Proof

If a and b are multiples of k, then a-b must also be a multiple of k.

Let’s suppose that P-D_{i+1} is a multiple of D_i. From the statement above, we know that P-(P-D_{i+1})=D_{i+1} must also be a multiple of D_i.

But this contradicts our assumption that D_i doesn’t divide D_{i+1}. Thus, P-D_{i+1} is not a multiple of D_i.

The only case left is when D_i divides D_{i+1} for all valid i.

We could try a few cases, or we could just submit a program which will say that no multiset exists if this case is satisfied, since there is no penalty for wrong submissions in Long Challenges. Whatever we do, we will find that a multiset never exists for this case!

Observation 3. If none of the conditions of Observation 1 or Observation 2 are satisfied, then no multiset exists.

Proof

Let’s first consider coin types which we are familiar with (our base-10 numeral system). Let D=[1, 10, 100, 1000] and P=2000. Consider the following questions:

If we have a multiset which sums to 2001, does that mean we must have a coin with value 1 in the multiset?

Answer

Yes, only a coin with value 1 can cause the units digit of the sum to be greater than 0. In this case, the multiset is not valid since we can remove the 1 so that the sum of the multiset becomes 2020.

If we have a multiset which sums to 2010, does that mean we must have a coin with value 10 in the multiset?

Answer

No, we can have 2010 coins of value 1.

If we have a multiset which sums to 2010, does that mean we must have a coin with value \le 10 in the multiset?

Answer

Yes, because if we only use the coins greater than 10, which are 100 and 1000, the tens digit in the sum should be 0.

Thus, there exists either a coin of value 1 or a coin of value 10. We can remove either one of them and still have a sum \ge 2000, so the multiset must be invalid.

We have 3 multisets, they sum to 2020, 2069, and 3000, respectively. Are any of them valid?

Answer

No.

In all of the cases here, what we are doing is that we are looking at the digits of S, the sum of our multiset, and finding the smallest digit greater than the corresponding digit in P.

For example, for 2020, the smallest digit which differs from P is the power 10. Then, we are guaranteed that the multiset contains a coin with value \le 10. We can remove one such coin to make the sum of our multiset smaller while still being \ge P.

What if we have a different D, and they are not powers of 10? Such as D=[2, 6, 60] and P=180?

We can do a similar thing that we did with the powers of 10. We can write P in our new base as 0\cdot 2 + 0\cdot 6 + 3\cdot 60.

Let’s say we have a multiset which sums to 186. We can write the sum in our new base as 0\cdot 2 + 1\cdot 6 + 3\cdot 60.

By our reasoning above, we realize that there must be a coin with value \le 6 in the multiset, so we can remove it and still have a sum \ge 180.

Thus, we have proved that no multisets exist for general D as well.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
 
using namespace std;
 
const int MX = 100000;
 
int d[MX + 1], c[MX + 1];
 
int main() {
	int T;
	ignore = scanf("%d", &T);
	while (T--) {
		int n, p;
		ignore = scanf("%d %d", &n, &p);
		for (int i = 0; i < n; i++) ignore = scanf("%d", d + i);
		
		bool found = false;
	
		d[n] = p;
		for (int i = n - 1; i >= 0; i--)
			if (d[i + 1] % d[i] != 0) {
				fill(c, c + n, 0);
				c[i + 1] = p / d[i + 1] - 1;
				c[i] = d[i + 1] / d[i] + 1;
				
				found = true;
				break;
			}
		
		if (found) {
			printf("YES");
			for (int i = 0; i < n; i++) printf(" %d", c[i]);
			printf("\n");
		}
		else printf("NO\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;
int a[MAXN], p;
 
void read() {
	cin >> n >> p;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
}
 
void solve() {
	for(int i = 0; i < n; i++) {
		if(p % a[i]) {
			cout << "YES ";
			for(int j = 0; j < i; j++) {
				cout << 0 << " ";
			}
			
			cout << p / a[i] + 1;
 
			for(int j = 0; j < n - i - 1; j++) {
				cout << " 0";
			}
 
			cout << endl;
			return;
		}
	}
 
	for(int i = 0; i < n - 1; i++) {
		if(a[i + 1] % a[i]) {
			cout << "YES ";
			for(int j = 0; j < i; j++) {
				cout << "0 ";
			}
 
			cout << a[i + 1] / a[i] + 1 << " " << p / a[i + 1] - 1;
			
			for(int j = i + 2; j < n; j++) {
				cout << " 0";
			}
			cout << endl;
			return;
		}
	}
 
	cout << "NO" << 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;

int n, p, d[1000];

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

	//make sure d[i] divides p
	for(int i=0; i<n; ++i) {
		if(p%d[i]<1)
			continue;
		cout << "YES";
		for(int j=0; j<n; ++j) {
			//if j=i, count is ceil(p/d[i])
			//otherwise, count is 0
			cout << " " << (j^i?0:p/d[i]+1);
		}
		cout << "\n";
		return;
	}

	//make sure d[i] divides d[i+1]
	for(int i=0; i+1<n; ++i) {
		if(d[i+1]%d[i]<1)
			continue;
		cout << "YES";
		for(int j=0; j<n; ++j) {
			//if j=i+1, count is 1
			//otherwise, if j=i, count is ceil((p-d[i+1])/d[i])
			//otherwise, count is 0
			int c=j==i+1;
			if(j==i)
				c=(p-d[i+1])/d[i]+1;
			cout << " " << c;
		}
		cout << "\n";
		return;
	}

	cout << "NO\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:

39 Likes

Now this is how editorials supposed to be written. Crisp and clear with example. @tmwilliamlin Thanks a lot for writing such a precise and well descriptive editorial.

14 Likes

Bro tell me one thing why we start from n-1 ( I solved it too ) but when we start from 0 then it will give wrong answer…can u plz give me a test case where the answer will be different.

Can you provide the test cases?
so that I can check for which examples my code is giving wrong answer.

@ssrivastava990
suppose we have to pay 12 Rs and denominations are
1,2,3,4,6

Yes 11 1 0 0 0

@ssrivastava990 but it violates the condition that if any coin is removed from the multiset, remaining sum should be strictly smaller than amount to be paid, like if i remove one coin of 1, amount will be 12.

1 Like

Yess… got it thanks broooo…

But is this only test case ( means give a test case where 1 is not present) and it fails

Yes there are more cases where denominations are like 18,6,2

try
1
2 10
2 5

Which one will be the output for following input
1
7 36
1 2 3 4 5 6 7
option…
a> 0 0 0 0 0 0 6
b> 0 1 0 0 0 0 5
Please explain…

There may be multiple output, as long as you don’t violate given conditions.Both options are correct.

@tmwilliamlin
I had a n^2 code basically which gave AC. The testcases were weak. I realized it later, but due to AC didn’t want to optimize it.
https://www.codechef.com/viewsolution/29365605

I think option B is optimum. In case B one will pay Rs 37 only (which is strictly greater than required fair) but in case of A one will Pay Rs 42 (and there is no upper limit it can be any 6,7,8,…and so on).
Since both option is correct for which option i should program ??

You should code for option A since it is efficient to find.

i guess this did the trick (O(n))
https://www.codechef.com/viewsolution/29466191

Ftlacv - Online C++ Compiler & Debugging Tool - Ideone.com hepl me with this where i am wrong

How in [3,4] for P=12 it’s impossible to use only one set? I can use 3*4 to get the required… and even if I remove one 3 … I can get < 12. Please help someone

The Problem Statement say that you should find if it is possible to pay more than P. So in this case you should pay at least 13.