Binary search.

We can do a classic binary search for this task, in particular:

• If $$$x \le mid$$$, we assign $$$r$$$ to $$$mid$$$.
• If $$$x \gt mid$$$, we assign $$$l$$$ to $$$mid+1$$$.

The resulting number of queries is $$$log_210^9 = 30$$$, which is sufficient.

Try solving it without binary search <(").

With the given limit, we can ask at most $$$n \times log_2n$$$ queries. Does that remind you of something?

Suppose we have an array $$$p$$$ consisting of the indices from $$$1$$$ to $$$n$$$ which is sorted according to the value $$$a_{p_i}$$$, we can see that the value of $$$a_{p_i}$$$ is infact $$$i$$$. In order to find $$$p$$$, Merge Sorting is our best candidate since it stably uses $$$n \times log_2n$$$ comparisons.

The resulting number of queries is $$$n\times log_2n \le 10^4$$$, which is sufficient.

Let $$$f$$$ and $$$s$$$ be the array consisting of Finnish's scores and Swedish's scores respectively. If the first $$$k$$$ highest scores of these $$$2n$$$ coders include the first $$$i$$$ highest scores from Finland and the first $$$k-i$$$ highest scores from Sweden, the $$$k$$$-th highest score is $$$\text{min}(f_i, s_{k-i})$$$.

Let $$$F(i) = \text{min}(f_i, s_{k-i})$$$, then our answer is the maximum value of $$$F(i)$$$ in which $$$|f_i-s_{k-i}|$$$ is also minimized. This is because if not, there will be at least a $$$j$$$ between $$$[i+1, k-i-1]$$$ or $$$[k-i+1, i-1]$$$ which $$$f_j$$$ is greater than $$$f_i$$$ or $$$s_j$$$ is greater that $$$s_{k-i}$$$, making $$$F(i)$$$ is no longer the $$$k$$$-th highest score. After that, we just need to perform a binary search.

The resulting number of queries is $$$2\times log_2n \le 34$$$, which is significantly lower that the limit.

Note: In case you don't understand, you can try visualizing the idea (Sorry for that).

We have $$$2^{10} = 1024 \gt 10^3$$$. Does that remind you of something?

It turns out that each number from $$$1$$$ to $$$10^3$$$ can be represented by $$$10$$$ binary bits, so we can try to construct each bit of every number from the information we get from each query.

For the $$$i$$$-th bit, we will ask a string where the $$$j$$$-th character is $$$1$$$ if the $$$i$$$-th bit of $$$j$$$ is $$$1$$$. Then, the returned binary string will tell us where the number having the $$$i$$$-th bit on are located and we just need to add $$$2^i$$$ to the values at those positions.

The resulting number of queries is $$$log_2n \le 10$$$, which is sufficient.

Can we assure whether the row of chairs from $$$l$$$ to $$$r$$$ has two adjacent chairs having the same color or not?

Yes, we definitely can. In particular, the answer is yes if :

• Chair $$$l$$$ and chair $$$r$$$ have the same color and $$$r-l+1$$$ is even.
• Chair $$$l$$$ and chair $$$r$$$ are different in color and $$$r-l+1$$$ is odd.

For the first case, we assume that the color of chair $$$l$$$ is $$$R$$$. Then, this row of chairs will be unsatisfied if and only if it is something like $$$RBRBR...$$$ and since $$$r-l+1$$$ is even, chair $$$r$$$ will eventually be $$$B$$$ which leads to a contradiction. Thus, the given case is correct and we can prove the latter one by doing the same thing.

Based on the above cases, we can solve the problem using binary search. But remember to check the color of chair $$$1$$$ and $$$n$$$ as we will only perform this if they aren't identical.

The resulting number of queries is $$$2 + log_2n \le 20$$$, which is sufficient.

Try to construct $$$a$$$.

Let $$$inv$$$ be an array in which $$$inv_i$$$ tells us the number of inversions in the $$$i$$$-th prefix. For each $$$i$$$, we split the array into $$$2$$$ parts which are $$$[1, i]$$$ and $$$[i+1, n]$$$. Then, the number of inversions of the entire array will be $$$x + y + z$$$ where:

• $$$x$$$ is the number of inversions of $$$[1, i]$$$.
• $$$y$$$ is the number of inversions of $$$[i+1, n]$$$.
• $$$z$$$ is the number of inversions where the elements lie in two parts.

After reversing the $$$i$$$-th prefix, we define $$$x', y', z'$$$ like above and we can see that $$$x' = C^2_i-x, y' = y$$$ and $$$z' = z$$$. Let $$$pre$$$ and $$$cur$$$ be the number of inversions of the array before and after the reversal, we have:

Based on the above idea, we can find the value of $$$inv_i$$$ with only $$$2$$$ operations which is reversing the $$$i$$$-th prefix to get the value of $$$cur$$$ and reversing it again to get the value of $$$pre$$$ and the initial array. After $$$2\times n$$$ operations, we obtain the entire $$$inv$$$.

So how can we restore the values of $$$a$$$ from $$$inv$$$? Let $$$b_i$$$ be $$$inv_i-inv_{i-1}$$$, we can see that $$$b_i$$$ is the number of values larger than $$$a_i$$$ in the $$$i$$$-th prefix. For each value $$$i$$$, suppose we find the positions of $$$1, 2, ..., i-1$$$ in $$$a$$$ and fill them, the position of $$$i$$$ will be the largest $$$j$$$ sastifying $$$b_j + cnt = j-1$$$ where $$$cnt$$$ is the number of filled positions in the $$$j$$$-th prefix at that time.

After finishing constructing $$$a$$$, we can perform a Selection Sorting on $$$a$$$ by reversing subarrays, which takes another $$$n$$$ operations.

The resulting number of queries is $$$3\times n \le 4\times n$$$, which is significantly lower that the limit.