Bitwise Optimisation for Finding the Last Number

🧩 Problem Recap

You’re given a hidden permutation in Equation 1.

$$p = [p_1, p_2, \dots, p_n] \qquad (1)$$

You can’t directly access the nth value and can only query using the following instruction, where the inequalities Equations 2 and 3 apply.

$$? \qquad i \qquad x$$

$$ 1 \leq i \leq n - 1 \qquad (2)$$

$$ 1 \leq x \leq 10^9 \qquad (3)$$

The judge replies:

The goal determines the last element at index n in 2n queries. The algorithm uses a bit-by-bit operation expanding from the bitwise partitioning logic on how numbers in a permutation share set bits. Each bit is inferred by comparing the response distributions to the expected value if that bit were 0 or 1.

⚙️ Problem Insight

Since we can’t query p[n]​ directly, we must infer its bits indirectly by observing how other numbers in the permutation interact with various bitmasks. Because the permutation is fixed and non-adaptive, each query gives consistent information about which bits are set in each p[i]. Comparing these results with the full range of numbers, 1…n, determines the missing element.

🧠 Algorithm

Step 1: Initialise sets and parameters

• Input: an integer n.

• Initialise:

  • rest = {1, 2, …, n-1} : indices that can be queried.

  • likely = {1, 2, …, n} : possible candidates for the nth index value.

  • ans = 0 : reconstructed number.

  • D = ⌈log₂(n)⌉ : number of bits to test.

This sets up the search space for both indices and candidate values.

Step 2: Iterate through each bit position

For each bit in the following expression:

$$d=0,1,2,…,D−1$$

1. Compute the bit mask through Equation 4.

$$\text{bit_mask}=1≪d \qquad (4)$$

1. Query all indices in rest:
   For each i∈rest:

   • Print ? i bit_mask

   • Read response r[i] ∈{0,1}

   • Partition indices:

     • index_0 ← indices where r[i]=0

     • index_1 ← indices where r[i]=1

2. Simulate how this bit divides possible numbers:

   • Partition likely into:

     • likely_0 ← numbers with this bit = 0

     • likely_1 ← numbers with this bit = 1

3. Compare counts of responses and theoretical partitions:

   • Let: zeros=∣likely_0∣ , ones=∣likely_1∣. If zeros=∣index_0∣:

     • It means all numbers with bit = 0 are already used among known indices.

     • Hence, p[n] must have bit d = 1.

     • Set ans=ans ∣ (1≪d).

     • Update active sets: rest=index_1, likely=likely_1

   • Else if ones=∣index_1∣:

     • Then p[n] must have bit d = 0.

     • Update: rest=index_0, likely=likely_0

4. Early termination:

   • If likely contains only one element, assign: ans=that element

Step 3: Output result

After processing all bits:

! ans

This prints the deduced value of p[n]​ to the judge.

⏱️ Complexity

This guarantees the algorithm stays within the problem’s 3-second and 256 MB limits.

✅ Conclusion

This approach, bitwise optimisation through logical partitioning, elegantly transforms a combinatorial search into a deterministic deduction process. By systematically using bit positions as filters, the algorithm determines the unknown element in at most 2n queries. It’s a powerful demonstration of how bit-level reasoning and information theory can solve interactive problems efficiently.