## Editorial for IOI '16 P5 - Unscrambling a Messy Bug

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

**Subtask 1** allows you to check all possible elements, so it can be solved by various solutions. For example, you can add random elements in your set, check all elements, try all transpositions and check that it will give you the same result.

**Subtask 2** may be solved by a simple solution, using at most `add_element`

operations and at most `check_element`

operations.

- Let's add elements into the set, element will have first bits set to one.

```
add_element("10000000")
add_element("11000000")
add_element("11100000")
add_element("11110000")
add_element("11111000")
add_element("11111100")
add_element("11111110")
add_element("11111111")
```

- Now we will get positions of bits one by one. First, let's find the position of bit . This can be done using at most queries:

```
check_element("10000000") returned false
check_element("01000000") returned false
check_element("00100000") returned false
check_element("00010000") returned false
check_element("00001000") returned false
check_element("00000100") returned true
```

- Now we know the position of bit and want to find the position of bit . This can be done using at most queries:

```
check_element("10000100") returned false
check_element("01000100") returned false
check_element("00100100") returned false
check_element("00010100") returned true
```

- And so on, we can find position of bit using queries, so the total number of queries in the worst case is .

**Subtask 3** can be solved by several optimizations of the previous algorithm. The simplest one is to shuffle the order of bytes. This will give us the average number of queries , which was enough to pass the tests.

**Subtasks 4 and 5** require an solution, in **subtask 4** you can make at most operations of each type, in **subtask 5** you can make only operations.

**Subtask 5** may be solved using *divide and conquer* technique. Let's try to split all bits into two halves using requests, and solve the problem for each half independently. In this solution, we will make at most operations of each type.

- To split a group of bits into two halves, we will add into set elements, element will have bit set to one, all other set to zero:

```
add_element("10000000")
add_element("01000000")
add_element("00100000")
add_element("00010000")
```

- After this, we will check elements with a single bit set to one. For example:

```
check_element("10000000") returned false
check_element("01000000") returned true
check_element("00100000") returned false
check_element("00010000") returned false
check_element("00001000") returned true
check_element("00000100") returned true
check_element("00000010") returned false
check_element("00000001") returned true
```

Now we know which bits correspond to the first bits. In this example, we know that bits , , , and correspond to bits –. So now we will solve the same problem for them only, and after that solve the problem for other bits.

In order to solve the problem for some subset of bits, we need to make sure that the elements we use in different subproblems are distinct. We can achieve this by setting all bits that are not in our subset to ones. For example, when we want to split bits – into halves, we will make the following operations.

```
add_element("10001111")
add_element("01001111")
check_element("11110010")
check_element("10111010")
check_element("10110110")
check_element("10110011")
```

## Comments