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

## E - Guess the Sum Editorial by en_translator

This is similar to ABC349-D Divide Interval in that the allowed queries form a segment tree. The difference here is that we can do subtractions. For example, suppose that $$N=3,L=1$$, and $$R=7$$. If you split the segment in the same manner as ABC349-D, three queries are required: $$A_1,A_2+A_3$$, and $$A_4+A_5+A_6+A_7$$. On the other hand, in this problem we can ask $$A_0+A_1+A_2+A_3+A_4+A_5+A_6+A_7$$ first, then $$A_0$$, and finally subtract the second response from the first to obtain the answer.

In the following equations, the modular equivalence are modulo $$100$$.

For integers $$x,y(0\leq x,y\leq 2^N)$$, we define $$S(x,y)$$ as follows:

$S(x,y)\equiv \begin{cases} 0\ (x=y) \\ \displaystyle\left( \sum_{i=x}^{y-1} A_i\right)\ (x<y)\\ -S(y,x)\ (x>y) \end{cases}$

What we want is $$S(L,R+1)$$, and what we can ask is $$S\left(2^ij,2^i(j+1)\right)$$. Since $$S\left(2^i(j+1),2^ij\right)\equiv-S\left(2^ij,2^i(j+1)\right)$$, we also assume that we can ask $$S\left(2^i(j+1),2^ij\right)$$. If we know $$S(x,y)$$ and $$S(y,z)$$, we can obtain $$S(x,z)$$ as $$S(x,y)+S(y,z)$$.

Here, consider a graph $$G$$ with $$2^N+1$$ vertices labeled $$0,1,\dots,2^N$$, with an edge between each pair $$x,y$$ such that asking $$S(x,y)$$ is allowed.

For two vertices $$x$$ and $$y$$ whose distance on $$G$$ is $$2$$, one can determine $$S(x,y)$$ by asking twice, $$S(v_0,v_1)$$ and $$S(v_1,v_2)$$, where $$v_0(=x),v_1,v_2(=y)$$ are the vertices on the shortest path from $$x$$ to $$y$$ on $$G$$.

Likewise, for two vertices $$x$$ and $$y$$ whose distance on $$G$$ is $$3$$, one can determine $$S(x,y)$$ with three questions, $$S(v_0,v_1)$$, $$S(v_1,v_2)$$, and $$S(v_2,v_3)$$, where $$v_0(=x),v_1,v_2,v_3(=y)$$ are the vertices on the shortest path from $$x$$ to $$y$$ on $$G$$.

More generally, for two vertices $$x$$ and $$y$$ whose distance on $$G$$ is $$d$$, one can determine $$S(x,y)$$ with $$d$$ questions.

Therefore, it is sufficient to find (and reconstruct) the shortest path from $$L$$ to $$R$$ on the graph $$G$$. Since graph $$G$$ has $$2^N+1$$ vertices and $$2^{N+1}-1$$ edges, one can use BFS (Breadth-First Search) to find the shortest path in a total of $$O(2^N)$$ time.

from collections import deque

N, L, R = map(int, input().split())
n = 1 << N
edge = [[] for i in range(n + 1)]
for i in range(N + 1):
for l in range(0, n, 1 << i):
r = l + (1 << i)
edge[l].append(r)
edge[r].append(l)

parent = [None] * (n + 1)
parent[R + 1] = -1
dq = deque([R + 1])
while dq:
v = dq.popleft()
for u in edge[v]:
if parent[u] == None:
parent[u] = v
dq.append(u)

ans = 0
now = L
while parent[now] != -1:
p = parent[now]
sgn = 1
l, r = now, p
if l > r:
sgn = -1
l, r = r, l
i = (r - l).bit_length() - 1
j = l >> i
print("?", i, j, flush=True)
T = int(input())
ans += sgn * T
now = p

print("!", ans % 100)


posted:
last update: