SciOI 2023 Open Contest

It is optimal for $MK$ students to use $M$ umbrellas, move to the SciCom Building, and then have one student return with $M$ umbrellas, repeating this process. Simulating this will yield the answer.

If $M=K=1$ and $N > 1$, it is impossible for all students to cross to the SciCom Building, so the output should be $-1$.

SciOI 2023 Open Contest - A-1 - Editorial

Let's start from $i=1$ and increase it up to $N$. For each $i$, we will be on one of the three cases below. Let $A_0 = -\infty$.

* If $A_i + K \le A_i$, we could not make $A$ an increasing sequence by any means. We should print $-1$.
* If $A_i \le A_{i-1} < A_i + K$, we should add $K$ to $A_i$ to make the sequence increasing. So we add $K$ to $A_i$.
* If $A_{i-1} < A_i$, we could either add $K$ or not. But if there is an optimal solution adding $K$, the sequence is still an increasing sequence if we don't add $K$ to $A_i$, and since the number of times we added $K$ has decreased, which contradicts our assumption. Therefore, it is always optimal not to add $K$.

Using this simple greedy approach, we can solve this problem in $\mathcal{O}(N)$.

SciOI 2023 Open Contest - A-2 - Editorial

## Dividing into Intervals

First, we will sort the students in the increasing order of  $A_i$. If multiple students have the same value of $A_i$, we will use $B_i$ as a tiebreaker. Now we assume if $1 \le i < j \le N$ then either $A_i < A_j$ or $A_i = A_j; B_i \le B_j$ holds.

First, we will group the students who should always receive the same grades. For example, if there are two students $i, j$ $(i < j)$ such that $B_i \ge B_j$ holds, we could not give these two students different grades.

* We cannot give student $i$ a higher grade since $A_i \le A_j$.
* We cannot give student $j$ a higher grade since $B_j \le B_i$.

So we must give two students $i, j$ the same grade. Additionaly, for every student $k$ such that $i < k < j$ holds, either $B_i \ge B_k$ or $B_k \ge B_j$ holds. Therefore, we should give all students in the range $[i, j]$ the same grade.

We define $prf[i]$ as the maximum of $B_j$ when $j \in [1, i]$. We can calculate this array with prefix sum in $\mathcal{O}(N)$. Now, we calculate the groups of students whom we should always give the same grade through the following steps.

* We choose a student with the biggest index whom we did not group yet. We define $j$ as the student's index.
* Now we initialize the starting position of the interval $i$ as $j$, and we expand the interval while calculating whether student $i-1$ should be included in the interval.
  * If there exists a student $k \, (i \le k \le j)$ which $prf[i-1] \ge B_k$ holds, student $i-1$ should be included in the interval.
  * Otherwise, students with indices smaller than $i-1$ have smaller values in $B$ than those with indices bigger than $i$, so they should not be included in the interval.
  * To quickly check the condition above, we make a variable to keep the value of $min_{i \le k \le j} B_k$, and renew the value when we decrease $i$ by $1$. In this way, we can check the condition in $\mathcal{O}(1)$.
* Repeat the above steps until all students are included in one of the intervals.

This interval division procedure can be finished in $\mathcal{O}(N)$. 

## Calculating the Answer

After the interval division, we define the size of the intervals $S_1, \cdots, S_k$, in the increasing order of the included students' index. The number of intervals equals $k$, and if there are less than $3$ groups, it is impossible to grade the students.

Now, the problem is to divide the sequence $S$ into three groups in a way that makes the difference of the lengths of the shortest and longest intervals as small as possible. Suppose that we partitioned the sequence $S$ to three intervals $[1, a]$, $[a+1, b]$, $[b+1, k]$ $(1 \le a < b < k)$. We define $A$, $B$, $C$ as the sums of $S_i$ in each intervals.

Then, we can show the following lemma:

* When $a$ is fixed, the answer $\max(A, B, C) - \min(A, B, C)$ reaches minimum when $\max(B, C) - \min(B, C)$ is smallest.
* Proof
  * When $a$ is fixed, the value of $A$ is also fixed. Also, $A+B+C=N$ holds.
  * The goal of the problem is to minimize the length of the interval $[\min(A, B, C), \max(A, B, C)]$, and since $B+C=N-A$, this interval always includes $\frac{N-A}{2}$.
  * When the values of $B$ and $C$ goes further from $\frac{N-A}{2}$, the value of $\max(B, C) - \min(B, C)$ increases, and at least one endpoint of $[\min(A, B, C), \max(A, B, C)]$ changes, so the length of the interval increases.

We calculate the prefix sum of $S$ and name the array $sum$. In other words, $sum[i]=\sum_{j=1}^{i} S_j$.

$a$ is always inside $[1, k-2]$. Then $A=sum[a]$, and the values of $B$ and $C$ should be the nearest values from $\frac{N-A}{2}$. Since $sum[b]=A+B$, $b$ should be equal to the value of $x$ where $sum[x]$ is the nearest to $\frac{N+A}{2}$. We can find the candidates with binary search, and therefore, we could find the answer for each $a$ in $\mathcal{O}(\log N)$.

In conclusion, we can solve the problem in $\mathcal{O}(N \log N)$.


SciOI 2023 Open Contest - A-3 - Editorial

## Subtask 1 (10 points)

We may try all $N!$ possible ways, each in $\mathcal{O}(N^2)$, to check if the permutation meets the condition.

## Subtask 2, 3, 4 (100 points)

### What condition should the permutation meet?

It is straightforward that $G$ must be connected if the permutation exists.

When the first $k$ elements of the permutation $\pi_1, \pi_2, \cdots, \pi_k$ are fixed, $\pi_{k+1}$ should be adjacent to one among $\pi_1, \pi_2, \cdots, \pi_k$, and when we remove vertices $\pi_1, \pi_2, \cdots, \pi_{k+1}$ from $G$, the remaining vertices should be connected.

### When does the permutation exist?

If the block-cut tree of the graph $G$ is linear, a permutation exist; if not, there are no possible permutations.

- If a block vertex is connected with three or more vertices, when the second cut vertex is added to the permutation, the graph with the remaining vertices is divided into two or more connected components. Therefore, there are no possible permutations.
- If a cut vertex is connected with three or more vertices, when the cut vertex is added to the permutation, the graph with the remaining vertices is divided into two or more connected components. Therefore, there are no possible permutations.

If the block-cut tree is linear, we can construct a permutation by finding a st-ordering for each block vertices, which will be described further in the paragraphs below.

In subtask 2, there are no cut vertices, so we can always construct a valid permutation.

### How can we construct a permutation if it exists?

If the block-cut tree is linear, we start from the vertex in one end and construct the permutation while following the block-cut tree.

Constructing a part of the permutation inside a block vertex is equivalent to finding a st-ordering in a biconnected component, and if we do it in $\mathcal{O}(N+M)$ or $\mathcal{O}((N+M)\log N)$, we can solve the problem.

In subtasks 2 and 3, we can solve the problem by repeating this process: find a vertex that is adjacent to at least one of the vertices already in the permutation, exists in the BCC we are currently working on, and is not a cut vertex in $\mathcal{O}(N+M) $ and add to the permutation. The time complexity of this solution is $\mathcal{O}(N (N+M)) $. It is impossible that all the vertices in the current BCC that are adjacent to at least one of the vertices in the sequence are cut vertices. This means that there always exists at least one vertex that can be added to the permutation.

SciOI 2023 Open Contest - A-4 - Editorial

## Subtask 1 (10 points)

For all possible $\binom{N-1}{K}$ cases, calculate the time for the fastest route among $K!$ possible ways and add them all.

## Subtask 2, 3 (100 points)

When we select $K$ nodes from the tree, to visit all selected nodes as fast as possible, we should visit the nodes in the following way:

- For all corridors connecting parents and child nodes, if there are any selected rooms in the subtree of the child node, the corridor should be visited twice.
  - We visit once when entering the subtree and once when leaving the subtree.
  - Exceptionally, the last-visited node is the one with the biggest depth, and the corridors between the node and the root should be visited once.

Therefore, we can calculate the answer as follows: (The number of corridors which has one or more selected rooms in the child's subtree) * 2 - (The number of corridors between the root node and the room with the biggest depth among selected). We can get the answer by double counting, concentrating on how many times each corridor is counted.

Firstly, let's calculate the first term. The number of cases where at least one selected node exists in the subtree of the child node is equal to $\binom{N-1}{K} - \binom{N-sz-1}{K}$. Here, $sz$ is the size of the subtree. We add the numbers for each corridor and multiply it by $2$.

Next, let's calculate the second term. Sort all rooms in the increasing order of the depths. For each room, when all the selected rooms have a smaller depth than the current room, the depth of the room is subtracted from the answer. In other words, if the room is in index $i$ in the newly sorted list of rooms, we subtract $depth \times \binom{i - 1}{K - 1}$ from the answer.

Now, we can get the answer using the two terms we calculated above.

When you calculate $\binom{n}{r}$ in $\mathcal{O}(N^2)$, we can solve Subtask 2. When we calculate them using factorials and modular inverses, we can calculate the answer in $\mathcal{O}(N)$ and solve Subtask 3.

SciOI 2023 Open Contest - B-1 - Editorial

## Subtask 2 (37 points)

For all $i$, it is obvious that both $S_{L_i} = A_i$ and $S_{R_i} = B_i$ holds, or both $S_{L_i}=B_i$ and $S_{R_i} = A_i$ holds. If the first condition holds, we consider this students as Type 1. Otherwise, we consider this student Type 2.

There are total $2^K$ ways to decide all types. For each cases, we will find the best solution. For all node $x$ which has two or more child nodes, we will decide the which order to traverse the subtrees below node $x$. In Subtask 2, there are no more than two child nodes for each vertices if we set the root to vertex $1$. Therefore we may assume that node $x$ has exactly two childs.

When we decide this order for node $x$, only the pairs $(A_i, B_i)$ which satisfies the conditions below are affected.

* Node $A_i$ is an ancestor of node $x$. $(A_i \neq x)$
* Node $B_i$ is a descendant of node $x$. $(B_i \neq x)$

From now, we will only consider the $i$-s that satisfies the two conditions above. Let the two childs of node $x$ as node $y$ and $z$. Let $a_1$ and $a_2$ the numbers of $i$ which node $B_i$ is in the subtree of node $y$ and student $i$ is Type 1 and 2, respectively. In the same manner, we define $b_1$ and $b_2$ as the numbers of $i$ which node $B_i$ is in the subtree of node $z$ and student $i$ is Type 1 and 2, respectively.

The added sum of travel distance by our choice in vertex $x$ equals to:

* If we visit node $y$ before node $z$:  $b_1\times len[y] + a_2 \times len[z]$

* If we visit node $z$ before node $y$: $a_1 \times len[z] + b_2 \times len[y]$

Here, $len[x]$ equals to the time it takes to traverse the subtree of node $x$.

All the choices for each nodes are independent, so we can solve the subtask in $\mathcal{O}(2^K \times N)$ time complexity.

## Subtask 3 (84 points)

Node $x$ could have multiple childs. Let each childs as $c_1, \cdots, c_l$, and for the $i$-th child, we define $d_i$ and $u_i$ as the number of $j$-s which satisfies the above two conditions and is Type 1 and 2, respectively.

If $u_i \ge 1$ and $d_i \ge 1$, it is able to remove $1$ from both of them. No matter what order we put $c_i$ in, the two students will traverse the subtrees before $x$ exactly once, and the subtrees after $x$ exactly once. $sz[x] - sz[c_i]$ should be added to the total cost.

So we can assume that for every $i$, $u_i=0$ or $d_i = 0$. We will divide the $i$-s into the three cases below.

* $u_i = d_i = 0$: Whereever we put $c_i$, there is no additional cost.
* $u_i \neq 0$: Students would visit every subtrees after $c_i$. These $c_i$-s should be visited as late as possible.
* $d_i \neq 0$: Students would visit every subtrees before $c_i$. These $c_i$-s should be visited as early as possible.

Therefore, it is optimal to visit all subtrees where $d_i \neq 0$, and the subtrees where $u_i = d_i = 0$, and the subtrees where $u_i \neq 0$. 

Now, we have to decide the order between the subtrees where $d_i \neq 0$, and the order between the subtrees where $u_i \neq 0$. Let two subtrees $c_1$ and $c_2$ satisfies $d_i \neq 0$. The condition which visiting subtree $c_1$ first is optimal is as below:
$$
sz[c_1] \times d_{c_2} \le sz[c_2] \times d_{c_1}
$$

This condition fullfills the law of conjunctions, so we can sort all $c_i$-s in this order and visit subtrees in the sorted order. Therefore, we can decide the orders between subtrees where $d_i \neq 0$. In the same way, we can also decide the orders between subtrees where $u_i \neq 0$.

The time complexity of this algorithm is $\mathcal{O}(2^K \times N \log N)$.

## Subtask 4 (100 points)

In fact, there are not that many meaningful vertices in the original tree. It is possible to reduce the number of tree vertices below $8K$ or fewer so that the answer is same as the original. Here are the list of vertices we need:

* $A_i$ and $B_i$ (At most $2K$ vertices)
* Vertices add when we compress the trees based on the above $2K$ vertices (At most $2K-1$ vertices)
* When we make a tree of $4K-1$ vertices above, for each edges, we need extra vertices to represent the 'branches'. (At most $4K-2$ vertices)
  * After the tree compression, for each edge $e$ in the tree compression, think about every branches which extends from edge $e$. For each branches, we should visit them either when we get down through the edge $e$, or we climb up through the edge $e$. However, for all branches, it will be optimal to select the time when Brue has less friends with him. Therefore, all branches must be visited in the same timeframe.
  * Any branches which are not included in this process does not have any effect in the answer.

Therefore, the number of vertices in the tree can be reduced into $\mathcal{O}(K)$, and we can solve the problem in $\mathcal{O}(2^K \times K \log K)$.



SciOI 2023 Open Contest - B-2 - Editorial

Let's create a new tree $T'_{1}$ by transforming the tree as follows:

For $i$ from 1 to $N$, merge nodes in $T_{1}$ that are adjacent to $i$ and have values smaller than $i$. Let the merged nodes be $s_1, s_2, ..., s_k$. Connect these nodes with $i$ in $T'_{1}$ such that their ancestor is $i$.

Repeat the above process, and you will end up with a tree $T_1$ containing only node $N$, and the root of $T'_{1}$ is node $N$. Similarly, transform tree $T_2$ to obtain $T'_{2}$.

For the ninja group set $S$, the node in tree $T_1$ where the party takes place is the Lowest Common Ancestor (LCA) of nodes belonging to set $S$ in tree $T'_1$. You can solve the problem using this property.

Let's fix the room number where the party takes place. If the node $c$ is the one where the party takes place, let $A_1, A_2, ..., A_s$ be the subsets of the descendants' subtrees in $T'_1$, and $B_1, B_2, ..., B_t$ be the subsets of the descendants' subtrees in $T'_2$. Assume these subsets are sorted in descending order of subtree sizes. Let $A$ be the union of $A_1, A_2, ..., A_s$, and $B$ be the union of $B_1, B_2, ..., B_t$.

There are two cases for $c$ where the party takes place:

1.  If $c$ is an element of $S$, then the remaining elements of $S$ must exist in the subtree of $c$ in both $T'_1$ and $T'_2$. (This ensures that the LCA is $c$.) In this case, the number of possible elements for $S$ is $2^{|A \cap B|}$.
    
2.  If $c$ is not an element of $S$, the remaining elements of $S$ must be in the subtree of $c$ in both $T'_1$ and $T'_2$, and $S \subset |A \cap B|$. Also, the number of elements $i$ where $S \cap A_i \ne \empty$ must be more than 1 for $T'_1$ to have $c$ as the LCA. Similarly, for $T'_2$, the number of elements $j$ where $S \cap B_j \ne \empty$ must be more than 1. Using the principle of inclusion and exclusion, the answer can be expressed as $(2^{|A \cap B|} - 1) -\sum_{i}^{} (2^{|A_i \cap B|} - 1) -\sum_{j}^{} (2^{|A \cap B_j|} - 1) + \sum_{i, j}^{} (2^{|A_i \cap B_j|} - 1)$.
    

To find the answer, we need to calculate $|A_i \cap B_j|$ for all $i, j$. To do this, we use the logic of Small-To-Large. We assume that the current sets are managed as sets through Small-To-Large Merging (possible in $O(N\log^2 N)$).

For $(i, j)$:

1.  If $i \ne 1$ and $j \ne 1$ (both are small), create an array $D$ to record which subset $x$ belongs to among $A_2, A_3, ..., A_s$. If it does not belong, do not record it. This can be done in $O(|A_2| + |A_3| + ... + |A_s|)$. Then, traverse the elements of $B_2, B_3, ..., B_t$ and use the record in array $D$ to calculate $|A_i \cap B_j|$. This process can be recorded using a map or hash map, and the time complexity is $O(|B_2| + |B_3| + ... + |B_t|)$. The overall time complexity is $O(|A_2|+ ... + |A_s| + |B_2| + ... + |B_t|)$, and when processed for all $c$, it is known to be $O(N\log N)$.
2.  If $i = 1$ and $j \ne 1$, traverse $B_2, B_3, ..., B_t$ and use the find operation in the set to check if it belongs to the managed set $A_1$. This takes $O((|B|-|B_1|) \log |A_1|)$ time, and when processed for all $c$, it takes $O(N\log^2 N)$ time.
3.  If $i \ne 1$ and $j = 1$, process similarly to case 2.

Only when $i = 1$ and $j = 1$ needs to be handled separately. Let $X_c$ and $Y_c$ be $A_1$ and $B_1$, respectively. For $N$ pairs $(X_1, Y_1), (X_2, Y_2), ..., (X_N, Y_N)$, calculate the values using Euler Tour, Segment Tree, and Small-To-Large, and the problem can be easily solved.

SciOI 2023 Open Contest - B-3 - Editorial

We denote the substring $S[l], S[l+1], \cdots, S[r]$ of the parentheses string $S$ as $S[l:r]$.

## Subtask 2 (38 points)

When $N$ is even, Junhui wins. A vaild parentheses string always has an even length. If $N$ is even, whenever Junhui erases a parenthesis, the string's length becomes even. Therefore, for Jimin to win, there should exist an odd-length substring $P$ in $S$, which the substrings obtained by erasing the first or last parentheses in $P$ should be both valid, but we can prove that no such parentheses string exists.

When $N$ is odd, if there exists an integer $x\ \left(0\le x < \left\lfloor\frac N 2\right\rfloor\right)$ such that $S[x+1:N-x-1]$ or $S[x+2:N-x]$ is a valid parentheses string, Jimin wins; otherwise, Junhui wins.

In the first case, if $S[x+1:N-x-1]$ is a valid parentheses string, Jimin should first erase $S[N]$, and from now on, erase the parenthesis on the opposite side of the one that Junhui had just erased. Then Jimin can make the string to $S[x+1:N-x-1]$, and Jimin wins. If $S[x+2:N-x]$ is a valid parentheses string, Jimin should first erase $S[1]$ and then apply the same strategy to win.

In the second case, Junhui will win if he erases the parenthesis on the opposite side of the one that Jimin had erased in his previous turn. In Jimin's turn, the length of the parentheses will be odd, so the parentheses string will not be valid. In Junhui's turn, the string will always be one of the forms of $S[x+1:N-x-1]$ or $S[x+2:N-x]$, which is not a valid parentheses string.

Therefore, we should determine if, for all $x$, $S[x+1:N-x-1]$ or $S[x+2:N-x]$ is a valid parentheses string. When $N\le 1000$, just determine whether each string is valid in $\mathcal{O}(|T|)$, then we can solve the problem in $\mathcal{O}(N^2)$. Similarly, we may use dynamic programming to solve this problem.

## Subtask 3 (100 points)

When $N$ is odd, we will only think about the substrings $S[x+1:N-x-1]$ (for all $x$) if they are valid parentheses strings. If this is possible, then checking if $S[x+2:N-x]$ is a valid parentheses string can be done symmetrically.

If a parentheses string $T$ is valid, it means that for a sequence $A$ which holds $A[i]=1$ when $T[i]$ is `(` and $A[i]=-1$ when $T[i]$ is `)`, all the prefix sums are at least 0 and the sum of all elements in $A$ equals 0.

We define $A$ as above and define $\Sigma$ as the prefix sum of $A$. We will use the results from $S[x+2:N-x-2]$ to determine if $S[x+1:N-x-1]$ is valid. In the previous step, if we calculated $M=\min_{x+2\le i\le N-x-2}\Sigma[i]$, then we can renew $M$ by $M:=\min\{\Sigma[x+1], M, \Sigma[N-x-1]\}$. To check if $S[x+1:N-x-1]$ is valid, check if $M\ge \Sigma[x]$ and $\Sigma[N-x-1]=\Sigma[x]$ both satisfy. This step is available in $\mathcal{O}(1)$, so we can solve the problem in $\mathcal{O}(N)$.

SciOI 2023 Open Contest - C-1 - Editorial

## $Q_{max}=N$ (10 points)

For all $i$, ask `diff 1 i`. If the answers for adjacent queries differ by $1$, it means the elements of the array have changed. Therefore, for all $i$, we can get $S_i$.

## $Q_{max}=3\lceil\log_2 N\rceil+8$ (42 points)

### Counting Numbers

Using the fact that $S_1=1$, ask `count 1 N` and `count 2 N`. Compare them and find the numbers that had decreased. That is the number of $1$ in the array. In the same manner, if we find the locations where $2$, $3$, $4$ first occur, we would know their numbers, too.

### Finding Locations

Let $B$ be the location of the first $2$. For all $i$ such that $1\le i < B$, the answer for `diff 1 i` is $0$, and for all $i$ such that $B\le i\le N$, the answer is at least 1. So we can get $B$ by binary search, and in the process, we use $\lceil\log_2 N\rceil$ queries.

In a similar way, we can also find the location of the first $3$ and $4$.

Therefore, using $3\lceil\log_2 N\rceil$ queries for location and $8$ queries for counts, we can solve the problem using at most 38 queries, which gives us 42 points.

## $Q_{max}=2\lceil\log_2 N\rceil+6$ (56 points)

The number of $4$-s can be calculated by subtracting the remaining number's counts from $N$, so we don't need to spend queries on it. We use $2\lceil\log_2 N\rceil$ queries for location and $6$ queries for counts, which uses at most 26 queries, giving 56 points.

## $Q_{max}=\lceil\log_2 N\rceil+6$ (90 points)

If $4$ does not exist in $S$, the answer for the query `diff 1 N` will be lower than $2$. Therefore, the queries `count 1 N`, `count 2 N`, `count 1 N-1` will give us the numbers of $1$-s and $3$-s ($2$-s, if there are no $3$-s in $S$), and we can know the number of $3$-s with these informations, so we can get all the counts in only three queries. From now on, we only consider the case where $1$, $2$, $3$, $4$ all exist in $S$.

For convenience, we use the following letters:

* $a$, $b$, $c$, $d$: the numbers of $1$, $2$, $3$, $4$
* $C$: the location of the first $3$ in $S$
* $a'$, $b'$: the numbers of $1$ and $2$ where $i \ge C$ $(a'<a, b'<b)$

We will use the a binary search process with the solutions above, but we will only find the location of the first $3$ and write it as $C$. Here, we only use $\lceil\log_2 N\rceil$ queries.

Next, we use six queries as below. We indicate the multiset obtained from each query on the right side of the queries. (All overlapping elements are indicated.

1. `count 1 N`: $P_1=\{a, b, c, d\}$
2. `count 2 N`: $P_2=\{a-1, b, c, d\}$
3. `count C N`: $P_3=\{a', b', c, d\}$
4. `count C+1 N`: $P_4=\{a', b', c-1, d\}$
5. `count 1 C-1`: $P_5=\{a-a', b-b', 0, 0\}$
6. `count 1 C-2`: $P_6=\{a-a', b-b'-1, 0, 0\}$

We can use this process to get $a$, $b$, $c$, $d$.

1. $P_1$, $P_2$ $\Longrightarrow$ $a$
2. $P_3$, $P_4$ $\Longrightarrow$ $c$
3. $P_5$, $P_6$ $\Longrightarrow$ $a-a'$, $b-b'$
4. $a$, $a-a'$ $\Longrightarrow$ $a'$
5. $a$, $a'$, $c$, $P_1$, $P_3$ $\Longrightarrow$ $Q_1=\{b, d\}$, $Q_2=\{b', d\}$

If $b=d$, we know all of $a$, $b$, $c$, $d$, so we print the answer. Otherwise, if $b\ne d$, we additionally use the processes below:

6. $Q_2$, $b-b'$ $\Longrightarrow$ $Q_3=\{b, d+(b-b')\}$
7. $Q_1$, $Q_3$ $\Longrightarrow$ $Q_1\cap Q_3 = \{b\}$

It holds that $d=N-a-b-c$, so we can know all of $a$, $b$, $c$, $d$.

Since we used $\lceil\log_2 N\rceil$ queries in binary search and inquired $6$ extra queries, we can get the answer in at most $16$ queries, which yields 90 points.

## $Q_{max}=\lceil\log_2 N\rceil+5$ (100 points)

The binary search process above can be done with the `count` query. The process of finding $C$ can be done by checking if there are at least two zeros in the answer for the query `count 1 k`. This also needs $\lceil\log_2 N\rceil$ queries.

We can get $C-1$ in this binary search, and during the process, the last query we ask will be either `count 1 C-1` or `count 1 C-2`. This is the same as the fifth or sixth query in the 90-point solution, so we can reduce one query.

Since this solution only uses $Q_{max}=\lceil\log_2 N\rceil+5 \le 15$ queries in maximum, we can get 100 points.

SciOI 2023 Open Contest - C-2 - Editorial

## Finding the Pivot

We can find the pivot $p$ using one of the $N$ numbers. When we put $N$ in the beginning of the sequence $A$, depending on the value of the pivot $p$, the sequence $A'$ becomes as below:

* $1 \le p < N$: $N$ is the leftmost element which are bigger than $p$. Therefore, $p$ is placed immediately before $N$.
* $p=N$: $N$ is the last element of $A'$.

We cannot distinguish the pivot $p$ if $N$ is the last element of $A'$. But since the location of $N$ does not give any information about the bitstring $S$, so although the real pivot was $N$, we may just assume that the pivot is the element immeadiately before $N$, and the information loss is the same as other general cases.

## Communicating Bitstrings

From now on, we ignore the element $N$ which was used to find the pivot. We consider that $N$ has decreased by $1$, but we now know the pivot $p$.

The statement below can be easily proved:

* If $1 < a < b < p$, or $p < a < b < N$, The order between $a$ and $b$ in sequence $A$ is the same as the order in sequence $A'$.

Let's think about encoding the bitstring as the following way.

* Repeat splitting the interval $[1, N]$ into half recursively, similar to making a segment tree structure. Here, we define the depth of the sequence $[l, r]$ as the number of splits we need to get this interval from $[1, N]$. **Note that the intervals with same depth does not meet each other.**
* Shuffle the numbers in the intervals, starting from the ones with bigger depths. For an interval $[l, r]$ with length at least $2$, if we define $m=\lfloor \frac{l+r}{2} \rfloor$, since we already shuffled the element between $[l, m]$ and $[m+1, r]$, we decide the order of merging these two intervals. There are $\binom{r-l+1}{m-l+1}$ ways to do this.
  * If we do not shuffle $A$ to $A'$, in other words, if the pivot does not exist, we can make all $N!$ possible sequences with the above procedure.
* Because of the pivot $p$, all the intervals $[l, r]$ such that $p \in [l, r]$ would be shuffled. Note that these shuffled intervals exist at most one per depth. Therefore, we will make it possible that we can recover the shuffling order of an interval with other intervals with the same depth.
  * For any interval $[l, r]$, we define the **order** of the interval as the lexicographical index of the order of elements $[l, r]$ in the sequence $A$, among all $(r-l+1)!$ possible ways.
  * For all depths, we select an interval $[s, e]$ with the biggest length, and put the length as $len$. We use the interval $[s, e]$ for recovery, not for additional cases we can make.
  * In this way, we can sacrifice only the informations from the longest interval for each depth, and can recover informations from any other intervals.

Using the above method, the number of possible cases we can make is equal to:

$$
59! \times \left( \binom{59}{30} \times \binom{30}{15} \times \binom{15}{8} \times \binom {8}{4} \times \binom{4}{2} \times \binom{2}{1} \right) ^{-1}
$$

The value is bigger than $2^{160}$. So we can solve $L=160$ and get 75 points.

For full marks, we should modify the structure as below:

* Split the whole interval to three intervals $[1, 20]$, $[21, 40]$, $[41, 59]$, then shuffle each of them as the same method in $L=160$.
* We shuffle the numbers between $[2, 20]$ and $[21, 30]$, and we shuffle the numbers between $[41, 59]$ and $[31, 40]$. Here we set the shuffling order of the two shuffles the same. Here, we can get additional $\binom{29}{10}$ cases.

Using the above method, the number of possible cases we can make is equal to:

$$
\left(19! \times 20! \times 20! \right) \times \left( \binom{20}{10} \times \binom{10}{5} \times \binom{5}{3} \times \binom{3}{2} \times \binom{2}{1} \right)^{-1}
$$

The value is bigger than $2^{171}$. Therefore, we can solve $L=171$ and get 100 points.

It is possible to get full marks in C나 C++ without big integer types such as `__int128`, but using big integer types will make the implemention more concise.

There is a solution of $L =175$, but the problemsetters agreed that increasing the value of $L$ for full marks was inappropriate for this contest. There may be solutions for larger values of $L$.
