hope to reach Specialist!)

:'(

Don't curse me bro :(

Problem G will not be interactive. Probably because there will be no problem G.

how many interactives have you solved ever?

Happy?

Only if you are able to solve it.

Shield fan

Why not?

my guess 5th. let's see :p

I am wondering the same question. I tried multiple ways, I mean n has a constraint of 2^30 and there are 33 queries so there must be some sort of way to binary search on answer.

Yes, its binary search.

Lets first split the array into 4 equal sized ranges. This is clearly possible since $$$n$$$ is a power of $$$2$$$ and at least $$$4$$$.

If we queried these 4 ranges, we would either get back:

• 3 "0"s and 1 "1", indicating that 1 represents the range with the hidden value, and thereby $$$\frac{n}{4} \lt k$$$. In this case, we binary search on the size of the range $$$[l, r]$$$, always ensuring it completely contains the range which returned $$$1$$$. Since this range will always contain the hidden value, the smallest size where the value becomes $$$0$$$ is your answer for $$$k$$$.

• 3 "1"s and 1 "0", indicating that 0 represents the range with the hidden value, and thereby $$$\frac{n}{4} \geq k$$$. In this case, we binary search on the size of the range $$$[l, r]$$$, always ensuring it remains completely within any range which returned $$$1$$$. Since this range will never contain the hidden value, the smallest size where the value becomes $$$1$$$ is your answer for $$$k$$$.

This naively takes $$$4$$$ queries for the first part + $$$30$$$ for the binary search which is $$$1$$$ too much. But we can notice that the result for the 4th segment can be uniquely obtained from the query results for the first 3 segments, reducing our total to $$$33$$$ queries.

Code — 297544715

I tried to first do 3 queries on range [1, n/4], [n/4+1, n/2], [n/2+1, 3*n/4]. That way you can find where the 1 is present and if k is greater or smaller that n/4.

Afterwards ask for [1, n/2] in case k >= n/4. If with that you discover k >= n/2 then you search including the half you know contains the 1, otherwise you search in the half you know it has only 0s. This way you can binary search as the function changes from true to false at a single value which will be k.

I think the idea is right but wasn't able to implement correctly, please let me know if somebody finds any flaws.

I did 3 queries:

1. with first query I can determine which of [1,n/2] and [n/2+1,n] gives answer 1 (because these two intervals have to give different answers.

2. the chosen interval [l,r] is divided into two halves [l,m], [m+1,r] and they are queried.

3. If those two answers are the same: that means [l,r] doesn't contain 1, and we also determine if k is in range [n/4+1, n/2] or [2, n/4].

4. If the two answers are different: that means the [l,r] contains 1 and k is in range [n/2+1, n].

In all these cases, the remaining part is very simple binary search on k.

Problem, Problem B.

Slow specialist like us are tend to eat dust from the expert + CM. Time to upsolve and practice some more haha

Solved the latter 2 days back so this was a treat

It could be TLE on the main tests.

O(N^4) for N^2 == 50 000 and 2.5s sounds like it might actually fit. I might hate myself for not trying that solution... I literally thought about it...

do MEX operation as problem said, repeat it 10 times (probably only need 3 times, but I rather 10) and you AC

Fix $$$x$$$ and $$$y$$$, then brute force every other position. You can see that there exists an answer with element value never greater than $$$3$$$.

If $$$|x - y| = 1$$$, then if $$$n$$$ is odd, print $$$2, 1, 0, 1, 0, ....$$$, and if $$$n$$$ is even, print $$$1, 0, 1, 0, 1, ...$$$. If $$$|x - y| \gt 1$$$, if the number of dragon between $$$x$$$ to $$$y$$$ and $$$y$$$ to $$$x$$$ is even, then print $$$1, 0, 1, 0, 1, ...$$$, otherwise let $$$a_x = 2$$$, $$$a_{x + 1} = 1$$$, $$$a_{x + 2} = 0$$$, $$$a_{x + 3} = 1$$$, ... (I draw all of those cases and saw the answers LOL).

If there wasn't another condition on x and y, then the trivial solution is

• If n is even: 0 1 0 1 0 1 0 1 ... (0 1 repeating)
• If n is odd: 0 1 0 1 0 1 ... 2 (0 1 repeating, then 2 at the end)

But when there is another condition on x and y (And if they have the same parity), then you will have to make either a[x] or a[y] equal to 2 too. (Note: There is an edge case when n is odd and x == 1, y has the same parity as x, then you will have to make a[1] equal to 2 instead of a[n])

First, think about a simple cycle of size $$$n$$$. If $$$n$$$ is even, $$$[0, 1, 0, 1, \ldots, 0, 1]$$$ is an answer. If $$$n$$$ is odd ($$$n \ge 3$$$), $$$[0, 1, 0, 1, \ldots, 0, 1, 2]$$$ satisfies the condition.

For this problem, there are at most two cycles in the graph, and they share exactly one edge. You can allocate $$$0$$$ and $$$1$$$ to the two vertices the shared edge connects, and do the above for each cycle individually.

For $$$k = 5$$$, the response for $$$(4, 8)$$$ would be $$$0$$$ since range contains $$$1$$$ $$$($$$at $$$6)$$$ and length $$$= 5$$$ is atleast $$$k$$$.

You can break the big cycle down into 2 small cycles defined as (1) in between x and y, and (2) outside x and y. ans[x] = 0, ans[y] = 1. Then, for each cycle, we separately start from y and work through the cycle back to x, just alternating the values being 0 and 1. If we return all the way back to x and find that we placed 0 and 0 adjacent to each other, we make that last-placed value a 2.

I don't know if it's a beautiful solution but here is my solution : 297477253. I know that a[i]<=2, so for each i, I create a set containing 0,1,2 and erase a[i-1], a[i+1], a[x], a[y] if I've already calculated their value, then I take the minimum (I have no proof of why it works but it seems logical).

I thought B > C too while at it, but when I realize a trick in B it's simple

(I'm on panic af ngl, losing so much time shuffling between B-C, also losing too much unnecessary time on A because I'm late)

ugh, ok, I get the error in D2, it's due to LL handling in cpp :(