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: