Official

B - Pasta Editorial by en_translator


In the \(i\)-th day, if Takahashi has multiple candidates of noodles, then he can choose any of them.
This can be proved by the fact that, when his meal plan has been completed for the first \((i-1)\) days, he can carry the plan on the \(i\)-th day (eat a noodle of length \(B_i\)) if and only if the multiset of the lengths of remaining noodles contains \(B_i\), and the multiset is independent of which noodle with the same length he have eaten in the previous days.

By this fact, we can perform a naive simulation. Inspect the noodle for each day: if a noodle with the desired length (equal to \(B_i\)) remains, let him eat the noodle. If he could eat noodles for all the \(N\) days, then the answer is Yes; if there exists a day on which he cannot find a noodle to eat, then the answer is No. The time complexity is \(O(NM)\), which is fast enough.
When implementing, be careful not to eat the same noodle on multiple days, or conversely eat multiple noodles on the same day. Also, note that programs outputting No multiple times or outputting Yes after outputting No due to the mistakes in conditional branches etc. are considered wrong.

Sample code in C++ (simulation)

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

int main() {
	int n, m;
	int a[1000];
	int b;
	bool used[1000];
	bool found,success;

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		used[i] = false;
	}

	success = true;
	for (int i = 0; i < m; i++) {
		cin >> b;
		found = false;

		for (int j = 0; j < n; j++) {
			if ((a[j] == b)&&(!used[j])) {
				used[j] = true;
				found = true;
				break;
			}
		}

		if (!found)success = false;
	}
	if (success)cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Also, this problem can be solved in a total of \(O((N+M)\log N)\) time by managing how many noodles of each length are there with a data structure like std::map. While the knowledge is probably not required to solve \(200\)-point problem in ABC, you may of course solve the problem in this way.

Sample code in c++ (using std::map):

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

int main() {
	int n, m;
	map<int, int>mp;
	int x;

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> x;
		mp[x]++;
	}
	for (int i = 0; i < m; i++) {
		cin >> x;
		if (mp[x] == 0) {
			cout << "No" << endl;
			return 0;
		}
		mp[x]--;
	}
	cout << "Yes" << endl;
	return 0;
}

posted:
last update: