Have you heard of quantum bitset?
nc quantum.challs.csc.tf 1337
Note: There is a time limit of 30 seconds on the remote.
First you need to solve the challenge with 2n ask queries
def ask(x0, y0):
sum = 0
for x, y in p:
sum += abs(x - x0) + abs(y - y0)
return sum
Let S = ask we have:
S(x0, y0) = Σ_(x, y) ∈ P {|x - x0| + |y - y0|}
S(x0, y0) = Σ_(x, y) ∈ P {(|x - x0| + |y|) + (|x| + |y - y0|) - (|x| + |y|)}
= Σ_(x, y) ∈ P {|x - x0| + |y|} + Σ_(x, y) ∈ P {|x| + |y - y0|} - Σ_(x, y) ∈ P {|x| + |y|}
= S(x, 0) + S(0, y) - S(0, 0)
Then ask all for x ∈ [0, n) S(x, 0) and for all y ∈ [0, n) S(0, y)
You now have the answer of S(x, y) for all x, y after 2n queries
def ask(x0, y0):
return S(x0, 0) + S(0, y0] - S(0, 0)
Σ_x ∈ [x0, x1] Σ_y ∈ [y0, y1] S(x, y)
= Σ_x ∈ [x0, x1] {(y1 - y0 + 1) * S(x, 0)}
+ Σ_y ∈ [y0, y1] {(x1 - x0 + 1) * S(0, y)}
- (x1 - x0 + 1) * (y1 - y0 + 1) * S(0, 0)
Can easily be done in O(1) using prefix sum
def query(x0, y0, x1, y1):
return (
(pSx[x1] - pSx[x0 - 1]) * (y1 - y0 + 1)
+ (x1 - x0 + 1) * (pSy[y1] - pSy[y0 - 1])
- (x1 - x0 + 1) * (y1 - y0 + 1) * S(0, 0)
)
You can refer to quantum.py to see how we implement these functions remotely
This is only possible thanks to the help of Aeren. Thank you so much!!
Query all even positions -> for each odd positions, if the 3 even numbers around it are colinear, try to determines the value at that position, otherwise you query it
Refer to solve.py for the implementation
There are also an interesting solutions by participants:
Basically the only optimization I did is first send every other point then if the change between 3 points I sent are same then we know the points in the middle has the same difference or well half the difference Then we run it a few times until we get a good rng on remote
Refer to solve_white.py for their implementation
Let f(x) := ask(x, 0) [It will be symmetric for y]
LEFT = (f(x + 1) - f(x) + n) / 2
RIGHT = n - LEFT
Due to 1 we only need to recover for each x, how many points has this coordinate.
f(i+3) = 3 * (LEFT - RIGHT) + f(i)
f(i+d) = d * (LEFT - RIGHT) + f(i)
With this observations we can compute f(i), f(i+1) and using 5 and 6 we can try to find how many frequencies are zero without asking for all of them. We start asking for f(i+3), then f(i+5), and so on f(i+2k+1), until we find something that is non zero.
I’m attaching the python code I used to check (empirically) the number of queries required.
from random import randint
def main():
# The bigger `n` is, less questions we need to ask
# 450 is the smallest value that n can take.
n = 450
xs = set([randint(1, n) for _ in range(n)])
queries = set()
i = 0
while i < n:
if i + 3 >= n:
# The last 3 elements are asked separately
for j in range(i, n):
queries.add(j)
break
queries.add(i)
queries.add(i + 1)
j = i + 3
while j < n:
queries.add(j)
if j - 1 in xs or j - 2 in xs:
# There are points at j - 1 or j - 2, so we need to ask for them.
i = j - 1
break
# Yay, we don't need to ask for `j - 1`.
j += 2
i = j
# Multiplying by 2 is ok, because we repeat this in both dimensions, and they are independent.
print(2 * len(queries) / n)