Possible Royal Favorites
National Olympiad — National round (2024 season)
Submission name: king.cpp
Problem summary
For each month you know the families in which babies were born and whether the king held a ball. He holds a ball exactly when at least one baby belongs to a favorite family. Among families that appear in the records, list those for which there is no evidence that they are not favorites.
Input
N months; each month gives K, a ball flag B, then K family IDs.
Output
The number of possible favorite families and their IDs in increasing order on the next line. If none exist, print only 0.
Constraints
1 ≤ N,K,family ID ≤ 100000; B is 0 or 1; total babies ≤ 10^6.
Worked example
An independently prepared example for this explanation.
Input
3 5 1 1 1 3 4 5 2 0 1 3 1 1 5
Output
2 4 5
Solution analysis
- A month without a ball proves that every family with a birth that month is not a favorite. A month with a ball guarantees that at least one of its families is a favorite, but does not rule out any of them individually.
- Track whether each family has appeared and whether it has appeared in a no-ball month. At the end, keep exactly the seen, unexcluded IDs.
- In the sample, families 1 and 3 are excluded by month two. Families 4 and 5 remain possible. Family 2 is not reported because it never appears in the evidence.
Why it works
Any family excluded by a no-ball month cannot be a favorite under the rule. For a seen family not excluded, no negative record forbids it; declaring it an additional favorite preserves every no-ball month and cannot invalidate a ball month. Thus precisely the retained families are possible.
Watch out. The output includes possible favorites, not only proven favorites. Repeated babies from the same family must not create repeated IDs.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<bool> seen(100001, false), excluded(100001, false);
for (int month = 0; month < n; month++) {
int babies, ball;
cin >> babies >> ball;
for (int i = 0; i < babies; i++) {
int family;
cin >> family;
seen[family] = true;
// No ball rules out every family with a birth in this month.
if (ball == 0) {
excluded[family] = true;
}
}
}
vector<int> answer;
for (int family = 1; family <= 100000; family++) {
if (seen[family] && !excluded[family]) {
answer.push_back(family);
}
}
cout << answer.size() << '\n';
if (!answer.empty()) {
for (int i = 0; i < static_cast<int>(answer.size()); i++) {
if (i > 0) {
cout << ' ';
}
cout << answer[i];
}
cout << '\n';
}
}