Hidden Sequence
Time limit1sMemory limit512 MB
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 , and to find this sequence you are allowed to ask questions of the following type: "is a subsequence of the hidden sequence?"
A binary sequence , with values , is a subsequence of the code , with values , if and only if can be obtained by deleting some of the values of . Formally, is a subsequence of if and only if there exist indices such that for every .
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.