Contest Duration: - (local time) (100 minutes) Back to Home

## E - Guess the Sum Editorial by Kiri8128

O(N) solution

For simplicity, add $$1$$ to $$R$$ in the problem statement. The problem is to construct $$[L, R)$$ using the minimum number of half-open intervals $$[2^i \cdot j,\ 2^i \cdot (j+1))$$. When combining intervals, both addition and subtraction operations are allowed.

Let $$j_0$$ be the smaller LSB (Least Significant Bit) of $$L$$ and $$R$$. It’s clear that there is no need to consider queries for $$j < j_0$$. Furthermore, at most four queries need to be considered for $$j = j_0$$. Specifically, if the smallest bit value of $$L$$ (represented by the position of LSB as $$2^k$$) is $$a$$ and the smallest bit value of $$R$$ is $$b$$, the following four queries need to be considered at most:

$$[L - a, L)$$ $$[L, L + a)$$ $$[R - b, R)$$ $$[R, R + b)$$ If $$a < b$$, the latter two queries are unnecessary, and if $$a > b$$, the first two queries are unnecessary. This allows us to reduce the problem to half-open intervals where the LSB is strictly larger in $$O(1)$$ time. Although there may be concerns about the number of intervals increasing exponentially as the LSB increases, the only points that need to be considered for each $$j$$ are the closest points to the left and right of $$L$$ and $$R$$, resulting in at most four intervals for each $$j$$.

Therefore, we can solve this problem in $$O(N)$$ time.

posted:
last update: