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 