Contest Duration: - (local time) (100 minutes) Back to Home

## D - Happy Birthday! 2 Editorial by en_translator

In fact, after you search $$201$$ candidates of sequence $$B$$ (or $$C$$), you can always find the pair of sequences that satisfy the condition.

When $$X+1$$ pigeons are in $$X$$ birdcages, there are at least one birdcages which contains two or more pigeons

This is called the “pigeonhole principle.” In this problem, we can say that

If you classify $$201$$ sequences into $$200$$ groups by the remainder of the sum of its elements divided by $$200$$, there are at least one group which contains two or more sequences.

Since there are more than $$2^N-1$$ candidates of sequences, for the case where $$N \ge 8$$, we can see that an answer always exists.
Now, how can we search $$201$$ candidates of sequences?
For example, the following strategy is possible: take the first $$\min(N,8)$$ elements and enumerate all candidates of sequences with bitmasks. For $$N \le 8$$, it’s nothing more than an ordinary brute force, so it works fine. For $$N \ge 9$$, since there are $$255$$ candidates that can be obtained from $$8$$ elements, so they are sufficient to obtain $$1$$ pair of answers.

This bitwise brute force works in a constant time.

Sample code in C++:

#include<bits/stdc++.h>

using namespace std;

void output(vector<int> &a){
cout << a.size();
for(auto &nx : a){
cout << ' ' << nx;
}
cout << '\n';
}

int main(){
int n;
cin >> n;
vector<int> a(n);
for(auto &nx : a){cin >> nx;}
vector<vector<int>> bk(200,vector<int>(0));

int cnt=min(n,8);
for(int i=1;i<(1<<cnt);i++){
int sig=0;
vector<int> s;
for(int j=0;j<cnt;j++){
if(i&(1<<j)){
s.push_back(j+1);
sig+=a[j];sig%=200;
}
}
if(bk[sig].size()!=0){
cout << "Yes\n";
output(bk[sig]);
output(s);
return 0;
}
else{bk[sig]=s;}
}
cout << "No\n";
return 0;
}

Construct a case where $N=7$ and the answer is No. (Expanding this fold reveals one of the answer) For example, the answer for the following case is No.  7 1 2 4 8 16 32 64 

posted:
last update: