# KOITST 24 Fruit Game Editorial

## Sub-problem 1

Since the constraints are very small, we can try all possible methods for each query using backtracking. This will solve the problem in $O(QN!)$ time.

## Sub-problem 2

For each fruit, we can calculate the largest fruit that can be created by starting with that fruit on the leftmost end. This can be done using a greedy algorithm that merges fruits whenever possible using a stack. By calculating this for all fruits for each query, we can solve the problem in $O(QN^2)$ time.

## Sub-problem 3

This sub-problem involves cases where the number of each fruit is 2 or less. If the fruits numbered 1 are positioned consecutively groups of even size, they can all be paired and converted into fruits numbered 2. However, if the fruits numbered 1 are positioned consecutively in groups of odd size, the fruits on both sides cannot be merged. Therefore, we observe the positions where the fruits numbered 1 are positioned consecutively in odd numbers, merge the fruits as much as possible, and find the size of the largest fruit. This can be computed in linear time for each query, solving the problem in $O(NQ)$ time.

## Sub-problem 4

Let's use dynamic programming. Define $D[i][j]$ as the rightmost end position of a fruit with number $j$ created by starting from the $i$-th fruit on the leftmost end. We can calculate these values in $O(|A_i|N)$ time for each query and solve the problem in $O(|A_i|NQ)$ time.

## Sub-problem 5

Considering the solution to Sub-problem 3, the important information is the positions where fruits numbered 1 are positioned consecutively in odd numbers. Knowing these positions allows us to merge all the fruits in between, thus calculating the size of the largest fruit. By managing this information using a data structure like std::set, we can quickly calculate the answer each time a fruit is updated. This solves the problem in $O((N + Q) \log N)$ time.

## Sub-problem 6

Let's precompute the dynamic programming used in Sub-problem 4. Using the DP information, we can quickly determine the largest fruit number that can be created for a given range query. For a query range $[l, r]$, to check if a fruit with number $x$ can be created, we verify if there exists a valid DP value $l \leq i, D[i][x] \leq r$. Observing the monotonicity of valid DP values, we can use binary search to find the smallest $i$ such that $l \leq i$ and $D[i][x]$ is valid, then check if $D[i][x] \leq r$. By checking this for all fruit numbers $x$ for each query, we can find the largest fruit number, with a time complexity of $O((N + Q \log N)|A_i|)$.

## Sub-problem 7

### Original text

Represent the fruits as $(x, y)$ if there are $y$ consecutive fruits numbered $x$. Consider cases where $x_{i-1} > x_i < x_{i+1}$. If $y_i$ is even, we can pair and merge them as in Sub-problem 3, i.e., $(x_i, y_i) \rightarrow (x_i + 1, y_i/2)$. If $y_i$ is odd, one fruit will remain unmerged, thus preventing merging of the adjacent fruits, i.e., $(x_i, y_i) \rightarrow (x_i, y_i - 1), (\infty, 1), (x_i, y_i - 1)$. Repeating these transformations until no more are possible will result in a bitonic sequence around $(\infty, 1)$. We can greedily merge smaller numbered fruits to find the size of the largest fruit. By using a segment tree to manage this bitonic sequence, storing the sequence shape and the largest fruit number for each segment, we update the maximum answer if more than one $(\infty, 1)$ exists within a segment. The complexity is $O((N + Q)|A_i| \log N)$.