[Yandex Cup 2024 Qual F] Zeroth Rome 题解

前言

English version of this editorial is provided after the sample code.

题意简述

本题为交互题，你需要猜 t 个 [0,2024] 间的非负整数 x_1,x_2,\ldots,x_t，可以询问最多 15 次，每次询问形如“给定一个大小为 N(1\le N\le 2025) 的集合 S 满足 S 的每个元素都是 [0,2024] 间的非负整数，交互库回答每个 x_i 是否在该集合内”。

注意，你的询问需要一次性全部给出，之后交互库再进行回答。但是，对于每个 x_i，交互库会在最多一个询问上给出错误的回复，而你需要准确地找出每个 x_i。

题目解法

如果交互库不会给出错误的回复，那么解决问题是简单的：考虑二进制拆位，对于每一位，询问值域中所有该位为 1 的数构成的集合，如果目标数存在于该集合内，代表目标数的该位为 1，否则为 0。可以在 \lceil\log_2V\rceil 次询问内完成。

如果交互库会在最多一个询问上给出错误的回复呢？考虑给 [0,2024] 间每个整数一个独特的“编号”：设整数 i 的编号为 a_i，如果 \forall i\ne j,\mathrm{popcount}(a_i\oplus a_j)\ge 3（其中 \mathrm{popcount} 表示一个整数二进制下 1 的个数，\oplus 表示按位异或），那么使用上面的询问方法询问这些编号，一定会得出正确的答案。具体确定答案的方法为，假设询问中得到了一个数 x，那么只要找到唯一一个 a_i 满足 \mathrm{popcount}(a_i\oplus x)\le 1 的 a_i，i 即为答案——可以证明这种编号构造方法能唯一确定答案。

现在的问题即为构造一组这样的 a_i。我们发现可以从 0 开始给每个数分配编号，将所有不合法的编号插入一个 std::set，之后找之中没出现过的最小非负整数，将其作为编号分配给下一个整数。用上面的方法进行暴力枚举，发现存在一组构造使得 a_i\le 32330，可以在 15 次询问内找到答案。

示例代码（C++17）

#include<bits/stdc++.h>
using namespace std;
const int N=2024;
int main(){
  ios::sync_with_stdio(false);
  vector<int> a; set<int> s;
  for(int i=0,x=0;i<=N;i++){
    a.emplace_back(x),s.emplace(x);
    for(int j=0;j<15;j++)
      for(int k=0;k<15;k++)
        s.emplace(x^(1<<j)^(j==k?0:(1<<k)));
    while(s.find(x)!=s.end())x++;
  }
  cerr<<a.back()<<endl;
  for(int i=0;i<=N;i++)
    for(int j=i+1;j<=N;j++)
      assert(__builtin_popcount(a[i]^a[j])>=3);
  int t; cin>>t;
  vector<vector<int> > v(15);
  cout<<"15\n";
  for(int i=0;i<15;i++){
    for(int j=0;j<=N;j++)
      if(a[j]>>i&1)
        v[i].emplace_back(j);
    for(int j:v[i])cout<<j<<' ';
    cout<<endl;
  }
  while(t--){
    int c=0,r=-1;
    for(int i=0;i<15;i++){
      int x; cin>>x;
      if(x)c|=1<<i;
    }
    for(int i=0;i<=N;i++)
      if(__builtin_popcount(a[i]^c)<=1)r=i;
    cout<<r<<endl;
  }
  return 0;
}

English Version

Translated by ChatGPT

Problem

This is an interactive problem, where you need to guess t non-negative integers x_1, x_2, \ldots, x_t within the range [0, 2024]. You can ask at most 15 queries, and each query takes the form: "Given a set S of size N(1\le N\le 2025), where every element of S is a non-negative integer within [0, 2024], does the interactor return whether each x_i is in this set or not?"

Note that you must provide all the queries at once, after which the interactor will respond. However, for each x_i , the system will give incorrect feedback for at most one query, and your goal is to accurately identify each x_i .

Solution

If the interactor never gave incorrect feedback, the solution would be straightforward: Consider the binary representation of each number. For each bit position, query a set consisting of all numbers in the range whose value in that bit position is 1. If the target number belongs to that set, then the corresponding bit is 1; otherwise, it is 0. This could be done in \lceil \log_2 V \rceil queries.

However, with the interactor potentially giving an incorrect response for up to one query, we need to take a different approach. We assign a unique "code" to each integer in the range [0, 2024]. Let the code for integer i be a_i , and ensure that for all i \neq j , we have \mathrm{popcount}(a_i \oplus a_j) \geq 3 , where \mathrm{popcount} denotes the number of 1s in the binary representation of an integer, and \oplus represents the bitwise XOR operation. By querying these codes in the method described earlier, we can guarantee a correct result.

To determine the answer, suppose we obtain a result x from the queries. We need to find the unique a_i such that \mathrm{popcount}(a_i \oplus x) \leq 1 , which will give us the correct i . This method ensures that we can uniquely identify the correct answer.

The problem now becomes constructing such a set of a_i . We can assign codes starting from 0, and for each code, insert invalid codes into a std::set. Then, for each subsequent number, assign the smallest non-negative integer that has not yet been used as a code. Using brute force exploration, we find that there exists a set of codes such that a_i \leq 32330 , which allows us to find the answer within 15 queries.