Editorial for IOI '16 P5 - Unscrambling a Messy Bug

Remember to use this editorial 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 $2^n$ $2^{n}$ possible elements, so it can be solved by various solutions. For example, you can add $2^{n-1}$ $2^{n - 1}$ random elements in your set, check all elements, try all $\frac{n(n-1)}{2}$ $\frac{n (n - 1)}{2}$ transpositions and check that it will give you the same result.

Subtask 2 may be solved by a simple solution, using at most $n$ $n$ add_element operations and at most $\frac{n(n-1)}{2}$ $\frac{n (n - 1)}{2}$ check_element operations.

Let's add $n$ $n$ elements into the set, $i^\text{th}$ $i^{th}$ element will have first $i$ $i$ bits set to one.

Copy

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 $0$ $0$ . This can be done using at most $n-1$ $n - 1$ queries:

Copy

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 $0$ $0$ and want to find the position of bit $1$ $1$ . This can be done using at most $n-2$ $n - 2$ queries:

Copy

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 $i^\text{th}$ $i^{th}$ bit using $n-i-1$ $n - i - 1$ queries, so the total number of queries in the worst case is $\frac{n(n-1)}{2} = 496$ $\frac{n (n - 1)}{2} = 496$ .

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 $\frac{n(n-1)}{4} = 248$ $\frac{n (n - 1)}{4} = 248$ , which was enough to pass the tests.

Subtasks 4 and 5 require an $\mathcal O(n \log n)$ $O (n \log n)$ solution, in subtask 4 you can make at most $2n \log n$ $2 n \log n$ operations of each type, in subtask 5 you can make only $n \log n$ $n \log n$ operations.

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

To split a group of bits into two halves, we will add into set $\frac n 2$ $\frac{n}{2}$ elements, $i^\text{th}$ $i^{th}$ element will have $i^\text{th}$ $i^{th}$ bit set to one, all other set to zero:

Copy

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

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

Copy

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 $\frac n 2$ $\frac{n}{2}$ bits correspond to the first $\frac n 2$ $\frac{n}{2}$ bits. In this example, we know that bits $1$ $1$ , $4$ $4$ , $5$ $5$ , and $7$ $7$ correspond to bits $0$ $0$ – $3$ $3$ . So now we will solve the same problem for them only, and after that solve the problem for other $\frac n 2$ $\frac{n}{2}$ 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 $0$ $0$ – $3$ $3$ into halves, we will make the following operations.

Copy

add_element("10001111")
add_element("01001111")

check_element("11110010")
check_element("10111010")
check_element("10110110")
check_element("10110011")

Comments

There are no comments at the moment.