Updated. I did not remember even where the problem originally came from :(

The high-level idea is, we divide the main problem into two phases: In the first phase, we determine the value of some positions; in the second phase, we query the sum of remaining positions. Recover 0-1 sequence is used in the first phase to determine more values of positions so that the main problem can be solved within a bounded number of queries.

$$$ (x^i+1)^{\text{mod}}=x^{i \text{mod}}+1 $$$ and since $$$ \text{mod} $$$ is a prime when modulo $$$ n $$$ we have $$$ \prod_{i=0}^{n-1} (x^i+1)^{\text{mod}} = \prod_{i=0}^{n-1} (x^i+1) $$$, and we can reduce $$$ T $$$ by this formula.

We maintain a query sequence $$$ q_i $$$ (consisting of sets, indexed from 1) of length $$$ 2^i $$$ for recovering sequence of length $$$ f_i $$$. Initially, $$$ i = 0 $$$ and $$$ f_i = 1, q_i = \lbrace \lbrace 1\rbrace \rbrace $$$.

Each time, we recurrently obtain $$$ q_{i + 1} $$$ base on $$$ q_i $$$ and try to use $$$ 2^{i + 1} $$$ queries to recover a 0-1 sequence of length $$$ 2 f_i + 2^i - 1 $$$. During our process, we always assume the last term of $$$ q_i $$$ queries the sum of the sequence.

Then we can perform the following queries for $$$ j $$$-th set $$$ S \in q_i $$$ which is not a complete set: $$$ S \cup \lbrace x + f_i | x \in S\rbrace \cup \lbrace 2 f_i + j \rbrace $$$ and $$$ S \cup \lbrace x + f_i | 1 \le x \le f_i, x \not \in S\rbrace $$$. The remaining two queries are $$$ \lbrace x | f_i + 1 \le x \le 2 f_i \rbrace $$$ and $$$ \lbrace x | 1 \le x \le 2 f_i + 2^i - 1 \rbrace $$$, which is consistent with our assumption.

Then in each pair of queries, we get result $$$ a $$$ and $$$ b $$$. Suppose the number of ones in items indexed from $$$ f_i + 1 $$$ to $$$ 2 f_i $$$ is $$$ m $$$, then $$$ \lfloor (a + b - m) / 2 \rfloor $$$ indicate the sum over $$$ S $$$, and $$$ \lfloor (a - b + m) / 2 \rfloor $$$ indicate the sum over $$$ \lbrace x + f_i | x \in S\rbrace $$$, and $$$ (a + b + m) \bmod 2 $$$ indicate the value of $$$ 2 f_i + j $$$.

This enables us to use $$$ 2^n $$$ queries to recover a sequence of length $$$ n 2^n + 1 $$$ since $$$ f_n = n 2^n + 1 $$$.

Team China:

• WZYYN (Yuyang Zhou)

• lyx_cjz (Yuxiang Luo)

• 142857 (Mingrun Jiang)

• yasugongshang (Zhanpeng Wang)

The regulations slightly changes this year. The thesis defense used to be between the two days' contest in the past several years, but this year it took place after the two days' selection. As before, it do matters the result of selection.

Seems work, thanks!

After long struggle with Python3 and bugs, my 2018 sadly ends with

My solution rquires division over big integers. However I have no template for it, so I tried to implement it using C++ first, after some time I changed my mind. Because of unfamiliar with Python, I spent long time coding, thinking about many things about language rather than the problem(like is there any functions like std::unique()?). Oh it's really a terrible night for me.

Well I didn't mean stop writing problem, I think the problem is a good problem but it's harder for people only using C/C++, compared with those are familiar with Java or Python.

I don't know the meaning for such a boring problem with lots of cases to handle. It's too much harder on coding than thinking.

Is there any place for virtual participation? Seems a challenging set of problems.

Wish everyone enjoys the round and few bugs! And hope all the programs will be fast in practice :D

it has been clarified in the announcement :)

wish all the participants high rating! :)

Well I think it's a great method(though may be too hard for me because of my poor English:D)