The problem E. Kachina's Favorite Binary String is saying that we have a binary sequence $$$s$$$ that we don't know and we can ask queries. In each query we can choose a subarray and ask about the number of subsequences of $$$01$$$ in this subarray. Your task is to determine the string $$$s$$$ or say that it's impossible.
It might be helpful to read an editorial or solve the problem yourself before reading this blog.
First let's solve the problem using $$$\frac{1}{2}\cdot n + \mathcal{O}(\log{n})$$$ queries(it is possible to do a bit better, but it would be helpful later). To do this we would like to know where is the last occurrence of $$$1$$$. Our first query will be the whole string. If the answer is $$$0$$$ we can just print IMPOSSIBLE, else we can binary search on a prefix. If some prefix gives the same result as a whole string, we know that each element not in this prefix must be $$$0$$$. Now we ignore all elements after this $$$1$$$(they are all $$$0$$$s). What we are interested in is the difference of the results of queries for the prefix ending on this $$$1$$$ and the query for the prefix ending just before this $$$1$$$. This difference is equal to the number of $$$0$$$s let's denote it by $$$k$$$. If at some point $$$k = 0$$$, we know the rest of the sequence(it's all $$$1$$$s). If $$$k=1$$$ we can binary search all $$$0$$$s by comparing the difference of the results for prefixes to $$$k\cdot \text{#elements not in the prefix}$$$. If they are equal, the last $$$0$$$ is in the smaller prefix, else it's not. The key upgrade to the editorial solution is an observation that since we know the number of zeros, we can ask queries not about each prefix but just every two prefixes. We can present the results in the following table.
| characters in s | difference |
|---|---|
| 00 | 0 |
| 01 | k |
| 10 | k-1 |
| 11 | 2k |
Now it's clear why we want to binary search for $$$k=1$$$($$$k-1 = 0$$$ and we cannot differentiate between $$$10$$$ and $$$00$$$).
So now how to solve the problem using $$$\frac{1}{3}\cdot n + \mathcal{O}(\log{n})$$$. We start asking about every three prefixes. And we get the following table:
| characters in s | difference |
|---|---|
| 000 | 0 |
| 001 | k |
| 010 | k-1 |
| 011 | 2k |
| 100 | k-2 |
| 101 | 2k-1 |
| 110 | 2k-2 |
| 111 | 3k |
The only problem being that for this we need $$$k\geq3$$$, so for $$$k=2$$$ we can't use it. Fortunately I've described the binary search part in such a way that it can be used for $$$k=2$$$. Seeing this you might think "Why can't we do more, like $$$\frac{1}{100}\cdot n+\mathcal{O}(\log{n})$$$, since the binary search part can be used for any constant $$$k$$$?". The problem is that for both $$$0110$$$ and $$$1001$$$ we have the same difference($$$2k-2$$$). So how could we achieve something better?
Interestingly enough we will achieve $$$\frac{1}{4}\cdot n + \mathcal{O}(\log{n})$$$, but as $$$\frac{1+4}{20}\cdot n + \mathcal{O}(\log{n})$$$. The idea is that for large enough $$$k$$$ you can differentiate between all the different differences from the table. For not large enough $$$k$$$($$$k \leq 100$$$) we just use binary search. The problem being that you can't differentiate between the sequences that have the same difference. To solve this we will ask four range queries depending on the results of the previous ones. The claim is that this works(you always can ask such $$$4$$$ queries to determine the sequence) for asking about every twenty prefixes and those four additional queries inside this substring. You can write a simple program to see that this is the case.
Sadly asking $$$5$$$ additional queries is hard to check brute force like.
Open questions: Can we get better constant than $$$\frac{1}{4}$$$? Maybe with some faster checker we can check the case with 5 additional queries in a reasonable time?
Comments (0)
