Official

G - The baggage Editorial by en_translator


To come to the conclusion first, it is optimal to assign parcels in the following order. If no parcels remain after the last step, then the answer is Yes; otherwise, the answer is No. From now on, we will refer to (a person’s strength)\(-\)(the sum of weights of parcels that they has) at some point as the remaining strength.

  • Step \(1\): A person with strength \(5\) picks up a parcel of weight \(5\). (Repeat this step until there are no more person with strength \(5\) or a parcel of weight \(5\). The same rule applies for the later steps.)
  • Step \(2\): A person with strength \(4\) picks up a parcel of weight \(4\).
  • Step \(3\): A person with strength \(5\) picks up a parcel of weight \(4\).
  • Step \(4\): A person with strength \(3\) picks up a parcel of weight \(3\).
  • Step \(5\): A person with strength \(5\) picks up a parcel of weight \(3\).
  • Step \(6\): A person with strength \(4\) picks up a parcel of weight \(3\).
  • Step \(7\): A person with the remaining strength at least \(2\) picks up a parcel of weight \(2\).
  • Step \(8\): A person with the remaining strength at least \(1\) picks up a parcel of weight \(1\).

It is obvious that if no parcels remain after the last step then the answer is Yes. We will now prove that if any parcel remains then the answer is No. Actually we will actually proof by contraposition; we will prove that if there exists an assignment that satisfies the condition, and a parcel of each weight does not remain.

First, parcels of weights \(5\), \(4\), or \(3\) are trivial. Since nobody can carry more than one parcel with weight at least \(3\), if a desired assignment exists, then the following holds:

\[ A_5\leq B_5, \quad A_4+A_5\leq B_4+B_5, \quad A_3+A_4+A_5\leq B_3+B_4+B_5. \]

Considering the situation after Step \(1\), \(3\), or \(6\) has ended, we can see that if the inequality above holds, then after such an assignment, a parcel of weight \(5\), \(4\), or \(3\) does not remain.

Next, we consider the parcels of weight \(2\). Take an assignment satisfying the conditions. Assume that the first 6 steps has ended, taking into account that who are carrying parcels of weights \(5\), \(4\), and \(3\) has a certain “remaining strength” with appropriate value subtracted Then, the following inequality always hold:

\[ A_2\leq \frac{1}{2}\times\left( (\text{the sum of remaining strengths})-(\text{the number of people with odd remaining strength}) \right), \]

\((\text{the sum of remaining strengths})\) is independent of assignments of parcels with weights more than \(3\), and \((\text{the number of people with odd remaining strength})\)
\(B_1+B_3+B_5-(\text{the number of people with strength }5\text{ who are carrying a parcel of weight }5)-(\text{the number of people with strength }3\text{ who are carrying a parcel of weight }3)-(\text{the number of people with strength }5\text{ who are carrying a parcel of weight }3)+(\text{the number of people with strength }3\text{ who are carrying a parcel of weight }4)\)
\(=B_1+B_3+B_5-A_3-A_5+2\times (\text{the number of people with strength }3\text{ who are carrying a parcel of weight }4). \)
It is appropriate if the value above for the assignment obtained through the algorithm above is less than that for the any assignment satisfying the condition. Thus, what we have to show is that “the number of people with strength \(4\) who are carrying a parcel of weight 3” of the assignment after the first six steps described above has finished is the minimum possible such value of the assignment of parcels with weights at least \(3\). This minimum value can be written as \(\max(0,A_3-B_3-(B_5-A_5-\max(A_4-B_4,0)))\), which can be derived stepwise. It is obvious that the assignment above achieves this value.

Finally, we consider the parcels of weight \(1\).

By the existence of an assignment satisfying the condition,

\[ A_1+2A_2+3A_3+4A_4+5A_5 \leq B_1+2B_2+3B_3+4B_4+5B_5 \]

holds. Then, it is obvious that no parcel of weight \(1\) remains after Step \(8\).

Therefore, the assignment algorithm has been justified. The simulation can be done in an \(O(1)\) time for each step by manipulating the number of people with each remaining strength and the number of parcels of each weight. Hence the judge can be done in an \(O(1)\) time for each test case, and the problem has been solved.

Sample code in C++:

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

#define N 200010
#define MOD (ll)998244353
#define ll long long
#define rep(i, n) for(int i = 0; i < n; ++i)

ll a[6];
ll b[6];

void pack(ll x, ll y) {
	ll c = min(a[x], b[y]);
	a[x] -= c;
	b[y] -= c;
	b[y - x] += c;
	return;
}

int main(void) {
	ll t;
	bool ans;
	cin >> t;
	rep(tt, t) {
		rep(i, 5)cin >> a[i + 1];
		rep(i, 5)cin >> b[i + 1];
		a[0] = 0;
		b[0] = 0;

		pack(5, 5);
		pack(4, 4);
		pack(4, 5);
		pack(3, 3);
		pack(3, 5);
		pack(3, 4);
		rep(i, 4)pack(2, 5 - i);
		rep(i, 5)pack(1, 5 - i);

		ans = true;
		rep(i, 5)if (a[i + 1] > 0)ans = false;
		if (ans)cout << "Yes" << endl;
		else cout << "No" << endl;
	}

	return 0;
}

posted:
last update: