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: