PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: wuhudsm
Testers: iceknight1093, rivalq
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Familiarity with bitwise XOR
PROBLEM:
There’s a hidden array A of length N.
You can provide the judge with two values i and X, following which the judge will set A_i to A_i\oplus X.
Then, the judge will tell you the maximum element of the array.
Use at most 10^5 operations to make all the elements 0.
EXPLANATION:
The constraint on A_i being 2^{30} and the fact that 30\cdot N \leq 10^5 (since N \leq 3000), along with the operation being a bitwise one, should hint at doing something bit-by-bit.
I’ll denote the operation where A_i is xor-ed with X as \text{query}(i, X).
We have no information to start with, other than the fact that the elements are distinct.
Let’s analyze what happens we perform a query.
- First, we can obtain the initial maximum of the array by choosing X = 0, since this doesn’t change any element.
- Now, let’s see what happens to the maximum when we do \text{query}(i, X).
- If the maximum doesn’t change, we don’t get too much information.
- If the maximum does change, we in fact get a lot of information!
- If the maximum reduces, then A_i used to be the maximum. This means the current value of A_i is \text{prev\_max} \oplus X, so performing \text{query}(i, \text{prev\_max} \oplus X) sets A_i to zero.
- If the maximum increases, the A_i is the new maximum, so performing \text{query}(i, \text{new\_max}) sets A_i to zero.
Either way, if we perform a query and the maximum changes, we can set the current position to zero: which means we never need to both with it in the future.
This should give us some idea: we just need to be able to trigger this change at least once for each index, and we’ll be done.
Combined with the ‘look at bits’ intuition from the start, here’s one way to do that:
- Let’s iterate over b from 0 to 29. Fix some i such that A_i \neq 0.
- Do \text{query}(i, 2^b). If this changes the maximum, set A_i to 0 as discussed above; otherwise do nothing.
- There’s one caveat: if b = 0, run this loop from 1 to N twice.
- This is only really needed for the case when the initial maximum is 2^{30}-1, so other ways of dealing with that case work too: for example, choose a random integer x and operate it on every array element (which works with reasonably high probability)
This obviously uses a small enough number of operations: we loop across the entire array 31 times, and then use at most one more operation for each index to set it to zero, for a total of \leq 32N operations, which is within 10^5 for N \leq 3000.
We only need to prove that it is indeed correct, i.e, sets everything to zero.
Proof
Let M denote the maximum value of the array. Note that M does change as we perform operations.
We do a bit of casework on the value of M.
First, if M \lt 2^{29}, then our algorithm is easily seen to be correct: no matter how the lower bits change during our operations, A_i \oplus 2^{29} = A_i + 2^{29} will always be the maximum element, so the last iteration of the loop will set everything to zero.
Now, we deal with M \geq 2^{29}.
Next, let’s consider the case when M \lt 2^{30}-1, i.e, M doesn’t have all its bits set.
In particular, let k be the highest unset bit in M.
Once we’ve performed operations on bits 0, 1, 2, \ldots, k-1, the maximum may have changed; but it’s still true that the current maximum cannot have all the bits 29, 28, \ldots, k+1, k set.
Now, let’s perform \text{query}(i, 2^k) for some i. Of course, if we can set A_i to zero after this, we do so.
Notice that (before the operation), if A_i has bits 29, 28, \ldots, k+1 set then k must be unset.
\text{query}(i, 2^k) then sets this bit, making A_i the unique largest element of the array (and hence we can immediately set it to zero).
This means the only remaining non-zero elements are those with at least one bit from 29, 28, \ldots, k+1 missing; and so we’ve increased the largest missing bit by at least 1.
Since we’re iterating from lower to higher, these elements will also eventually be set to zero.
Finally, we’re left with the case when M = 2^{30}-1, when we can’t choose the largest unset bit to operate on.
If we can somehow make M \lt 2^{30}-1, we’ll be happy, since we have an algorithm for that case.
Here’s where we use the fact that all the elements are distinct.
Suppose A_m = 2^{30}-1.
Notice that performing any non-zero move on position m will reduce it, hence changing the maximum.
So, if we do \text{query}(i, 1) for every i, we’ll eventually change the maximum.
However, there’s one small pitfall here: if there exists a j \lt m such that A_j = 2^{30}-2, then \text{query}(j, 1) will set A_j = 2^{30}-1; and then when we change A_m the maximum doesn’t actually change, so we’re back where we’re started.
A simple way to solve this is to simply run \text{query}(i, 1) on every index again!
This works because if the maximums did swap position as mentioned above, it can’t do that a second time (since 2^{30}-2 now occurs after 2^{30}-1).
Also, if the maximum after the first loop is no longer 2^{30}-1, then the second loop cannot create 2^{30}-1 as the maximum — it can be seen that if the loop removes 2^{30}-1 as the maximum, then 2^{30}-2 cannot be the new maximum at the end of it.
Alternately, you can also just pick a random integer X and do \text{query}(i, X) for every i.
With probability at least 1 - \frac{N}{2^{30}} \geq 0.999997206, you pick an X such that 2^{30}-1-X isn’t in the array, which means no collisions can occur.
TIME COMPLEXITY:
\mathcal{O}(N\log{2^{30}}) per testcase.
CODE:
Setter's code (C++)
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=29;
const ll TMD=0;
const ll INF=2147483647;
int n,last_max,cur_max;
void work(int bt)
{
for(int i=1;i<=n;i++)
{
printf("%d %d\n",i,(1<<bt));
fflush(stdout);
scanf("%d",&cur_max);
if(cur_max==0)
{
printf("0\n");
fflush(stdout);
scanf("%d",&cur_max);
return ;
}
if(cur_max!=last_max)
{
printf("%d %d\n",i,cur_max);
fflush(stdout);
scanf("%d",&cur_max);
if(cur_max==0)
{
printf("0\n");
fflush(stdout);
scanf("%d",&cur_max);
return ;
}
last_max=cur_max;
}
}
}
int main()
{
scanf("%d",&n);
printf("1 0\n");
fflush(stdout);
scanf("%d",&cur_max);
last_max=cur_max;
for(int i=0;i<=LOGN;i++)
{
work(i);
if(!i) work(i);
}
return 0;
}
Editorialist's code (Python)
queries = 0
def ask(i, x):
global queries
queries += 1
assert queries <= 100000
print(i, x)
mx = int(input())
assert mx != -1
if mx == 0:
print(0)
correct = int(input())
assert correct == 1
exit(0)
return mx
n = int(input())
mx = ask(1, 0)
zero = [0]*(n+1)
import random
if mx == 2**30 - 1:
x = random.randint(0, 2**30 - 1)
for i in range(1, n+1):
newmx = ask(i, x)
if newmx > mx:
mx = ask(i, newmx)
zero[i] = 1
elif newmx < mx:
mx = ask(i, mx ^ x)
zero[i] = 1
assert mx != 2**30 - 1
for bit in range(30):
x = 1 << bit
for i in range(1, n+1):
if zero[i] == 1: continue
newmx = ask(i, x)
if newmx > mx:
mx = ask(i, newmx)
zero[i] = 1
elif newmx < mx:
mx = ask(i, mx ^ x)
zero[i] = 1