This is a cool problem I thought of, I challenge you to solve it (please put the solution in spoiler in the comments):
This is an interactive problem
There is a hidden array $$$a$$$ of size $$$n$$$.
You can ask at most $$$2n$$$ queries of type:
- $$$?$$$ $$$i$$$ $$$j$$$ ($$$1 \le i \le j \le n$$$) — the jury will answer $$$a_i$$$ $$$\oplus$$$ $$$a_j$$$. Where $$$\oplus$$$ denotes the bitwise XOR operation.
After done asking the jury, you should output "$$$!$$$" to mark as finished. Then you need to handle a total of $$$q$$$ queries of type:
- $$$l$$$ $$$r$$$ — compute $$$a_l$$$ $$$\oplus$$$ $$$a_r$$$
Output the answer for each query.
You can't be slick and ask all the queries at first because you don't know the queries yet, you have to ask, then the jury will give you the queries
Input:
- The first line contains $$$2$$$ integers $$$n, q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the size of array $$$a$$$ and the number of queries
What is your stratergy to solving this?
Can you solve with strictly less than n queries to the jury and not using a temporary element?
gkos, Hyder1102, nik_exists, zeyd1234, SrabonGitikar, srvntofthejudge (sorry for pinging, just wanted to know how you would solve this)
Ask all XORs with the first element and for the query just perform XOR on their queries, that is, (a[l] ^ a[1]) ^ (a[r] ^ a[1]). That way you solve the problem in n-1 queries.
i think N-1 queries are enough, we just need to ask (1,i) for i>1
Yea, $$$2n$$$ is just for fun :)
A rather interesting problem would be to interact with same ai ^ aj queries, but the queries asked by the jury should be range queries (l,r)
return -1 if the length of segment asked by the jury is odd
The information extracted using '?' contains of 2 distinct elements, and xor of 2 expressions which are composed of even number of distinct elemetns, always results in even number of distinct elments,
as we have : |A^B| = |A| + |B| — 2*|A&B|
for segments of even lengths, we can break them into subsegments of length 2, hence we need to ask the jury (i,i+1) for 1 <= i < N
Before I finished reading the problem, I thought it was asking for this.
For the even branch, you can also just create the array $$$b_i = a_i \oplus a_1$$$, then the solution is a range xor on the resultant array (so accumulate xor on $$$b$$$ then do standard inclusion-exclusion). Even parity of $$$a_1$$$ in a given range means it naturally cancels out.
What does "results in even number of distinct elments" mean? XOR is just one result. A proof for your -1 is that if replace each $$$a_i$$$ with $$$a_i \oplus x$$$ for some $$$x$$$, then the answer of all queries asked by you remains the same while the result of an odd sized query asked by the judge is different.
okay so what i meant is,
lets say A is the xor of x different indices, (need not be contiguos) and B is the xor of y different indices,
then A^B must have the xor of x + y indices, minus common elements in both A and B which get reduced from both x and y.
so — 2*delta
Hence if x and y are even, then so should x + y — 2 * delta be
Use n-1 queries to calculate $$$a_1 \oplus a_i$$$ for all $$$2 \leq i \leq n$$$ Then, if $$$l$$$ or $$$r = 1$$$, we have the solution, otherwise, we can do $$$(a_l \oplus a_1) \oplus (a_r \oplus a_1) = (a_l \oplus a_r)$$$
Just ask and store all XORs with the first element. Then (a[l] ^ a[1]) ^ (a[r] ^ a[1]) for every queue. It's trivial, i solved it in 5 min... maybe i'm just good at "observations" XD
You do not need $$$2n$$$ queries. This can simply be solved in $$$n$$$ queries. In each query, let $$$i=1$$$ and traverse $$$j$$$ from $$$2$$$ to $$$n$$$. Now you have $$$a_1 \oplus a_i$$$, for $$$i = 2, \ldots , n$$$. Now for each query, for the particular, given $$$l, r$$$, the answer is:
This is because this expression evaluates directly to $$$a_l \oplus a_r$$$, and with the queries that we have asked, we already have the elements $$$a_1 \oplus a_i$$$, for $$$i = 2, \ldots , n$$$. Therefore we can calculate the above expression.
Xor is its own inverse. Pick an element a_1 and xor every el with a_1 then js do their 2 xors together: it cancels out
Idk what they talking about
deleted
Um, yea, they both have mace PFPs, what did you expect? :)
deleted
$$$n-1$$$ queries are sufficient. We can query it pairwise ((1,2),(2,3),(3,4),...(n-1,n))
then if i have to answer for (l,r) i can just xor (l,l+1)'s answer, (l+1,l+2)'s answer,... (r-1,r)'s answer cuz l and r occurs once but l+1,l+2,...,r-1 occur twice and we know that if a number xors itself then it's 0
Formally,
When i query the judge, I can construct an array $$$B$$$ of size $$$n-1$$$ where $$$B_i$$$ is the answer to "? i i+1" $$$(1 \le i \le n-1)$$$
When the judge queries me with "l r", I can reply with $$$B_l \oplus B_{l+1} \oplus ... B_{r-1}$$$
YES! That was my original intended solution, but no one used it to solve my problem :(
Won't this run in O(N*Q) time, unless we use prefix xors? And if you use prefix XOR, then it will just become the solution everyone else has, to take xor with a1 and ai...
ofc, prefix XOR should be used; In my solution, I described my approach, not the complete implementation
usage of prefix xor only make my solution have the same time complexity as others (O(n+q)); except for the usage of property $$$x \oplus x = 0$$$, my solution is different from others (more specifically, different in terms of visualization)
I agree, after all there are many ways to solve a problem.
:)
Ask "$$$?$$$ $$$a_1$$$ $$$a_i$$$" for every $$$i$$$
Then for each query: $$$(a_1 \oplus a_i) \oplus (a_1 \oplus a_j) = a_i \oplus a_j$$$
Everyone is solving this problem under n queries. what was the intended solution for 2n queries?