Thanks for quick Editorial

Really. That much easy . Question A

like this contest,thanks

Just one XOR missile

The fastest Editorial in the Wild West

Took a WA for me to reread problem 1 and realize that subarray is the same as subsequence. Facepalm.

Was Expecting more XOR problems XD Super Fast Editorial...Nice Contest!!! Thanks

Can anyone guide me why Binary search fails for A!?

Having multiple different solutions in the editorial really helps in expanding how to approach a problem.

XXXXX killed me .. 8 WA :(

In E, why are we looking for cycles without edges cutting through it?

Is E tight? I have the same but my estimated probability is very poor. Can you provide a calculation of the probability of success?

Roughly estimation: Need to find out $$$(u, v)$$$ s.t. $$$bitcount(p_u | p_v)\le 6$$$ after $$$50$$$ queries. Run $$$10^3$$$ simulations, mostly fail at one simulation.

I was blank reading A for 20 minutes, smh.

It was my 50th contest. And it went well!!

Fastest editorial I have ever seen! Just after the contest have ended. Thanks Boss.

What was testcase 130 for problem D?

Super-fast editorial!

The problem A didn't seem like a Div.2 A

is it possible to do A with binary Search?

Here's another approach for D:

Start with an empty graph and keep adding vertices from 1 to K in increasing order, using a DSU to keep track of connected components. If you ever add an edge that joins two vertices that were already joined, you have a cycle of length at most K.

Otherwise, you have a forest of size K, and can split it into vertices of even and odd depth. The larger one will be an independent set of size at least (K+1)/2.

The data of problem D is not strong enough. 83681437

Will this work for E?

For all indices $$$i = 2...n$$$ query(1, i). The minimum of these values (let's call it min1) is one valid location (let's call it min_zero) for 0 to be present at (or is it not?). Index 1 is also a valid index for 0 to be present at as we're querying from here initially. Now, let's do for all $$$i = 2...n$$$ (i != min_zero) query(min_zero, i). If the minimum obtained value from this is lesser than min1, we can be sure that min_zero index surely has the value 0 (can we?), otherwise index 1 must be containing zero. Now, if we also store in a map all our queries, we can construct the answer easily.

If not, can you please explain why? If you do happen to look at my submission, I know it contains a tonne of implementation errors (and so I'm reimplementing my idea correctly again right now...). Thanks!

Good contest, lot to learn.

we have Xor problem but not xor problem :(

Short & Crispy Statements + Super fast Editorial.

I get another solution for E, but more luck is needed. My max queries is 4260. https://mirror.codeforces.com/contest/1364/submission/83685672

B and A should've been switched.

For D, you can also refer to this.

Problem D was copied from here . Just take any submission and change the required parameters to get AC.

What does my verdict of D mean exactly? 83649436

Forgot to think if the order would matter in cycle printing in D problem, Hence Still Blue :( RIP Rating

Can someone give me the video tutorial for problem for C?

Improvement 100.

Video Editorial for Problems A, B, C

After this round I was doubting myself. Now after reading comments got to know same was with so many people.

Why doesn't any of the system test cases for Problem C cover the -1 case?

What is wrong with this approach for B:

Keep selecting the biggest and smallest elements in the remaining segment of array until all segments have been considered.

E.g. given 4, 2, 8, 3, 1, 5, 7, 6
Iter1: Biggest and smallest are 8 and 1, so we take out segment [8, 3, 1] and are left with [4, 2, X, 5, 7, 6]
Iter2: We take out 4 and 2, and are left with [X, X, 5, 7, 6]
Iter3: We take out 5 and 7, and are left with [X, X, X, 6]
Iter4: We take out 6 and we're done

So ans (taken in order of input) is:
7
4 2 8 1 5 7 6

Why is this approach wrong?
A simple example that also fails with this approach will help. Thanks

I have a solution for E that does not search for the element 0. Instead, it searches for two elements a and b with disjoint bitmasks: a & b = 0. Then for each index i, we have p_i = query(a, p_i) & query(b, p_i).

To find two such elements, let's choose $$$m$$$ random indices, and for each one query it with $$$k$$$ other random indices. For each of the $$$m$$$ random indices, we have a mask that contains it. We just look for a pair that have disjoint bitmasks. This process is actually quite reliable for $$$m,k$$$, even if they're small enough for the constraint.

From the last few contests, Problem A seems to be more tricky than B.

My first contest(and hopefully the last) where I could not solve a single question. Is there anyone who could not solve a single question? Feeling too bad.

jesus christ i tanked this contest, i had the right idea for B for like 2 hours but my implementation was dog and i didn't know how to do it LUL

mohammedehab2002 In my approach after some discussion with lavish315 we found out that after we have obtained the set of size sqrt(n) instead of random queries we can take one element from the set and query it with other elements of the set. Atleast half of the numbers will be eliminated from the set (As our bit will be reduced by one) . So we keep on repeating these steps until the size of the set reduces to 1 and this will take atmost 2*sqrt(n) queries which is around 64.

Can someone give a counter example or point out where does this solution fail? https://mirror.codeforces.com/contest/1364/submission/83658431

This solution works as follows: suppose n,x:3,3 and arr[3]={1,2,3} Remainder over prefix sum when divided by 3 is: {1,0,0} So, the code looks for first non-zero remainder . Here it occurs at index=0. So, the answer is max of(index+1,n-1-index}. i.e. 2. The code was able to pass only 3 pretests. Can somebody point out error or give a counter example It would be highly appreciable.

Thanks, I learned so much from the contest

My idea for D: Code

It is simular to first solution, but I don't like term "cutting through it" and using DFS. You can alternately use BFS to find cycle — once you get to node that has been visited already, and it wasn't node's parent. Now you have cycle, and it doesn't have any edges "cutting through it" because if it had some edges cutting it, they would form smaller cycle — anyone knows that BFS is used when you need shortest path, so that can't happen. So lets say that you come from node $$$u$$$ to node $$$v$$$ that has been visited.

Now that I know there exists a cycle, and that it comes together at thoes two nodes — now I went on to make LCA algorithm to find where cycle begin, and to get edges along the way. There I use vectors $$$v1$$$ and $$$v2$$$, to get all edges on the way from $$$u$$$ and $$$v$$$ to their $$$LCA(u, v)$$$. To get full cycle I only needed to take $$$v1$$$ (to get from $$$u$$$ to $$$LCA(u, v)$$$) and reverse of $$$v2$$$ (original $$$v2$$$ is path to get from $$$v$$$ to $$$LCA(u, v)$$$, so its reverse is path from $$$LCA(u, v)$$$ to $$$v$$$). Note: we started with edge $$$u$$$ to $$$v$$$, so finally, we have some cycle!

So $$$veki$$$ now has full cycle! And now back to editorial: If its length is at most $$$k$$$, print it. Otherwise, take every other vertex (take a vertex and leave a vertex) and you'll end up with a big enough independent set.

Hope this clears some things up for people in comments asking how to find cycle.

Great contest mohammedehab2002! I really enjoyed problem!

Edit: some spelling mistakes (I spelled THROUGH as THROW), I have C in english for a reason :)

Thanks for the fast editorial!

thanks for the fastest editorial, the problems were a little bit tough,but I've enjoyed,love from bangladesh

In problem $$$D$$$ one can take an arbitrary connected component of size $$$K$$$ using dfs, if it can be painted in $$$2$$$ colors, then print the most frequent color, else print the odd cycle that makes it impossible.

Test cases for problem D were weak. My brute force solution to get the smallest cycle passed ^_^

https://mirror.codeforces.com/contest/1364/submission/83681740

for problem C: if a[i]>i..then answer doesn't exist. test case: 2 2 2 should give -1...but no system test checked this situation.

my solution got pretests passed in contest but after contest it gets TLE (B problem). I think codeforces should tell this at time of contest. Hard luck.

I don't understand this editorial statement of Problem C — "The key observation is: if for some index i, ai≠ai−1, then bi must be equal to ai−1, since it's the only way to even change the prefix MEX." Can anyone explain to me how one can come up with such an observation?

for the A: can anyone explain the answer for this testcase ~~~~~ 1 5 10000 10000 5000 5000 10000 0 ~~~~~ Shouldn't the answer be 4 with elements as 10000, 5000, 10000, 5000? The answer was given 3. Please help anyone UPD: there is new paragraph after 1 and first 10000. I dont know why it didnt work.

can anyone tell me what is wrong with this solution of C
https://mirror.codeforces.com/contest/1364/submission/83693458 upd:- I got that still you can downvote me for this stupid question and make my depressed ass worse!!

I really like the difficulty distribution of these problems. A was more involved than usual, and it felt more like a skill based contest rather than a speed based one. Thanks for the interesting problems and fast editorial!

C, I just noticed that my submission not handle the case where output is -1, for input like

3
2 2 2

But it is AC. So I checked the testcases. There is not a single one for output -1. Is this intended?

That's why I love codeforces, couldn't solve problem A in today's div2. contest :) .Btw, thanks for the quick editorial.

OMG!
Problem D and codeforces round 628th problem F are pretty much same! Ehab's Last Theorem

My solution for E was exactly like the one described by Mohammad_Yasser in the editorial. I also thought about why the third case $$$p_{a} | p_{b} = p_{b} | p_{c}$$$ doesn't appear often. Here's what I found.

Say number of unset bits in $$$p_b$$$ is $$$y$$$. Observe that $$$p_{a} | p_{b} = p_{b} | p_{c}$$$ implies that any bit unset in $$$p_b$$$ is set in $$$p_c$$$ if and only if it is set in $$$p_a$$$. Thus, assuming $$$p_a$$$ and $$$p_c$$$ are chosen uniformly at random (they aren't really random, but I will talk about that later), the probability that $$$p_{a} | p_{b} = p_{b} | p_{c}$$$ is $$$\frac{1}{2^{y}}$$$.

Now, with this observation, we have to find the expected number of times we need an extra query given we repeat the operation $$$q$$$ times. We can have the following dp for this:

Let $$$\text{dp}(q, y)$$$ denote the expected number of times we need an extra query given we repeat the operation $$$q$$$ times, and initially $$$p_b$$$ has $$$y$$$ unset bits. We arrive at the following recursion:

Now, you could either compute this dp for $$$q = 2048$$$ or just observe that as most numbers will have around half their bits set, this expected number is very less.

Also, as our algorithm basically tries to reduce $$$p_a$$$, the expected number of unset bits increases in general and thus the expected number of extra queries may actually be lesser.

My solution for Problem B — time limit exceeds in Java while passes flawlessly in c++, I'm using fast io for java and c++ in this scenario, JAVA coders .. can you please help me with the above problem ?