Problem B - Blind Bottles — Solution¶
1. The Game in One Minute¶
There are n bottles, each labeled 1..n, arranged in a secret order.
A guess is a line of n numbers (a rearrangement of 1..n).
After each guess, you’re told how many positions are exactly right.
You win when all positions are right.
Our goal: figure out the secret order using at most 10,000 guesses for n ≤ 100.
2. Big Idea (No heavy math)¶
We stick to one baseline guess all the way through: the simple list:
1 2 3 ... n
Call its score B (how many spots were already right in that baseline).
Now we learn about the secret order by making very small, controlled changes to this baseline:
Swap just two positions `i` and `j` in the baseline and ask again.
If the score goes up, then those two positions are directly related in the secret ordering (they are neighbors in a loop).
If the score stays the same or goes down, those positions aren’t directly related.
Doing this for every pair `(i, j)` lets us draw a picture (a graph) of who is connected to whom. That picture always breaks into loops:
A single dot (no connections) means that position was already correct.
A pair of dots connected to each other is a simple 2‑swap.
Any longer loop (3 or more) means the correct bottles rotate around that circle of positions.
After we have these loops, we make at most one extra test per long loop to find which way it rotates. Then we can write down the final, correct order and win.
3. Why swapping two spots tells us anything¶
Think about what the final arrangement looks like around any one position:
There’s the spot where this position’s bottle really belongs.
There’s also the spot whose bottle belongs here.
Those are the two “neighbors” around that position in the final solution. Swapping i and j helps only when i and j are such neighbors (either the bottle from i belongs in j, or the bottle from j belongs in i). That’s exactly why the score goes up when we swap a “neighbor pair”.
4. Step‑by‑step plan¶
Baseline. Ask the identity order 1 2 … n once. Save the score as B.
Build connections. For every pair of positions (i, j):
Swap only those two in the baseline and ask again.
If the score is higher than `B`, draw an edge between i and j.
Read the loops.
No edges → position already correct (leave it as is).
One edge → a 2‑swap; those two positions want each other’s bottles.
Two edges → part of a longer loop (a circle of 3 or more positions).
Decide the direction (for each long loop).
Try pushing everyone in the loop one step forward (a “rotate once” guess), leaving all other positions as in the baseline.
If the score jumps by the loop’s length, that is the right direction. Otherwise, it’s the reverse direction.
Write the final answer. Now we know, for each position, which position’s bottle belongs here. Build the full line and print it once.
5. Tiny example (n = 5)¶
Say the secret order is: [3, 5, 2, 1, 4]
After checking all pair swaps, we discover a single loop:
positions: 1 → 3 → 2 → 5 → 4 → back to 1
That means the correct bottles cycle around those positions.
We do one “rotate once” test on just that loop. If the score jumps by 5, we already have the exact solution; otherwise we reverse the loop.
Either way, we now know the final arrangement and can print it.
6. How many questions do we ask?¶
One for the baseline.
One for each pair of positions (there are about n(n−1)/2 such pairs; for n = 100 that’s 4950).
At most one extra per longer loop (in the worst case, around 33 of them).
One final print of the full answer.
Total ≤ 4,985 guesses for n = 100, well under the 10,000 limit.
7. The Python solution (Accepted by Kattis)¶
# Blind Bottles — Python interactive solution
# Deterministic O(n^2) queries (<= 4985 for n<=100)
# Algorithm: pairwise swaps vs identity to reveal cycle adjacencies,
# then 1 query per long cycle to fix its orientation.
import sys
def ask(perm):
"""Print a permutation, flush, and read judge's reply (number of fixed points)."""
print(" ".join(map(str, perm)), flush=True)
line = sys.stdin.readline()
if not line:
sys.exit(0) # judge closed
k = int(line.strip())
if k == len(perm):
sys.exit(0) # solved; judge ends the game
return k
def main():
data = sys.stdin.readline()
if not data:
return
n = int(data.strip())
# 1) Base query: identity
base = list(range(1, n + 1))
B = ask(base)
if B == n:
return # already solved
# 2) For every pair (i, j), swap on top of identity and see if score improves.
# If it does, i and j are adjacent in the hidden permutation's cycle.
adj = [[] for _ in range(n)]
tmp = base[:] # mutable copy of identity
for i in range(n):
for j in range(i + 1, n):
tmp[i], tmp[j] = tmp[j], tmp[i]
s = ask(tmp)
if s > B: # Δ > 0 -> adjacency between i and j
adj[i].append(j)
adj[j].append(i)
tmp[i], tmp[j] = tmp[j], tmp[i] # restore to identity
# 3) Reconstruct the permutation.
perm = [-1] * n
used = [False] * n
# Fixed points: degree 0
for i in range(n):
if len(adj[i]) == 0:
perm[i] = i + 1
used[i] = True
# 2-cycles: degree 1
for i in range(n):
if not used[i] and len(adj[i]) == 1:
j = adj[i][0]
perm[i] = j + 1
perm[j] = i + 1
used[i] = used[j] = True
# Cycles of length >= 3: degree 2
for i in range(n):
if used[i]:
continue
# Collect one undirected cycle in order
cyc = []
u = i
prev = -1
while True:
cyc.append(u)
used[u] = True
a, b = adj[u][0], adj[u][1] # degree 2, so exactly two neighbors
v = a if a != prev else b
prev, u = u, v
if u == cyc[0]:
break
L = len(cyc)
# 4) Determine orientation with one extra query:
# try mapping cyc[k] -> cyc[k+1]; if we gain L matches, that's the direction.
test = base[:] # identity elsewhere
for k in range(L):
test[cyc[k]] = cyc[(k + 1) % L] + 1
res = ask(test)
if res - B == L:
# forward orientation is correct
for k in range(L):
perm[cyc[k]] = cyc[(k + 1) % L] + 1
else:
# reverse orientation
for k in range(L):
perm[cyc[k]] = cyc[(k - 1) % L] + 1
# 5) Final answer
ask(perm)
if __name__ == "__main__":
main()