Under construction

Still being built. Things may change

Hidden Sequence

Time limit1sMemory limit512 MB

Summary
Recover a hidden binary string of length N by asking whether chosen binary strings are its subsequences, keeping the longest query as short as possible.
Level

Medium7 of 10

Topics
String, Greedy, Divide and conquer
Solved
No attempts yet

Problem

You did it! You have finally made it to the X spot of the treasure map, but to open the treasure chest, you first need to break the code. The label attached to the chest states the rules: the code is a binary sequence of length NN, and to find this sequence you are allowed to ask questions of the following type: "is SS a subsequence of the hidden sequence?"

A binary sequence SS, with values S1,S2,…,SKS_1, S_2, \ldots, S_K, is a subsequence of the code CC, with values C1,C2,…,CNC_1, C_2, \ldots, C_N, if and only if SS can be obtained by deleting some of the values of CC. Formally, SS is a subsequence of CC if and only if there exist KK indices 1≤i1<i2<⋯<iK≤N1 \le i_1 < i_2 < \cdots < i_K \le N such that Cij=SjC_{i_j} = S_j for every 1≤j≤K1 \le j \le K.

You get a part of the treasure if you crack the code. The shorter the longest query you asked, the more of the treasure you get. In this game, the treasure is worth 100 points.

Examples1

  1. Example 1

    Input
    1
    
    Expected output
    ? 0
    ! 1