hope to reach Specialist!)

hope to reach pupil :(

:'(

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?

were you? idk man, earlier i could atleast solve 2, now i cant even solve the second prob lol. ig imma noob. gotta grind frfr.

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| > 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.

Think graph.

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 :(

Exactly!! The standard dp is easy to identify but dp when in disguise like this, its becoming impossible for me to identify

I think it should be this: If there's an S that occurs after a P then you print NO.

b/c everything after the s needs to be [1,2,...] and everything before the p needs to be [1,2,...]. You can't put the #1 in two places.

If there's an S before a P then you are OK. EXCEPT for an edge case where there's a space before the s and a space before the p. .sp. is NO sp.... is YES ....sp is YES.

It's DP

Dijkstra can be used only in cases where the answer is monotonic.

It's possible to Dijkstra this but it's essentially encoding the DP transitions as a graph and you get an extra log factor

Someone mentioned it in another comment, but I did the same thing: 1. First find a way to make a valid MEX cycle without the additional constraint of x and y being friends:

if n is even: 0,1,0,1,0,1..

if n is odd: 0,1,0,1,...,2.

e.x.

n = 4 --> [0,1,0,1]

n = 5 --> [0,1,0,1,2].

When you add in the constraint that x and y are friends:

n is even --> check if x and y are already valid (x = 0, y = 1 or vice versa). If not, then make one of them 2.

n is odd --> just rotate the array so x or y is the number 2.

You actually gained +1