Waiting for our 16th one

who told you that cf will die before round 10000.

At least we get ternary contests for a while

And base 10 contests, weird, seems like every contest is a base 10 contest

if contests pick up speed in the future, I will take in another binary contest when I am 90 (¬‿¬)

Why downvote me....

I'd say speedforces ABCD1,
if lucky D2, if blessed by Great Mike E.

Your begging will not stop his descend into the comment section.

Maybe the admins will add more contests between the two.

Even if they won't, you can still enjoy contests like ABC or ARC:)

Answer is always a power of two (or zero if the array is already sorted).

I can tell it we had to go by powers of 2 I suppose, however I couldn't figure out, but point of interest was near the powers of 2. Waiting for editorial

Binary search

When checking for k, you can notice that each block of size x (smallest power of 2 greater than k) can be swapped arbitrarily, so the smallest x numbers need to be in the first x, next x numbers in the next x positions, ect

idk for D2 tho, someone pls help, is it segment trees?

The thing is that we group elements by groups of 2^m from left to right. For example: A = 2, 1, 5, 2 -> [2]. [1]. [5]. [2] -> [2, 1], [5, 2] -> [2, 1, 5, 2] And we check whether sorting every group independently sorts the whole sequence: A = [2], [1], [5], [2] Not sorted A = [1, 2], [2, 5] Sorted so we print the size of the group.

This solution works for every array A except for when A is already sorted, in which case we print '0'.

k = max(k, MSB(current index after sorting ^ index before sorting))

You can try this. First,a = [1,0],b = [1,1] Second,a = [0.0,0],b = [1,1,1] These two pairs of data helped me find my bug.

Try this Python script: https://pastebin.com/0Xypd6RZ

It writes a bunch of testcases to C-test.in and the answers to C-test.ref. I used it to debug my own solution, so I might as well share it.

First solve D1 with merge sort.

Then, the initution of that using some data structure comes out.

Well, let's try segment tree first(for convience, push $$$10^9$$$ to the back of $$$a$$$ until length of $$$a$$$ is a power of 2). So, our segment tree must maintain the answer itself.

Let's say a chunk is an interval starting at $$$x \times 2^y$$$ with length of $$$2^y$$$. $$$y$$$ can be 0.

By looking at the procedure of D1, we'll see that for a chunk, if the maximum of the left half is strictly greater than the minimum of the right half, then $$$k$$$ must be at least the length of the chunk divided by 2.

So we just maintain range minimum, range maximum, and answer(note that we made the length of $$$a$$$ a power of 2, so a node on the segment tree just maintains a chunk).

TC: $$$O(n + q \log n)$$$

Implmentation

I thought log(n)^2 = log(n^2) = 2log(n) lmao :(

I got a O(q*log(n)^2) solution using binary search and segment trees, but it TLEs :(

Having blocks-split array, and knowing max and min in each block, array can be sorted if $$$max_i \leq min_{i+1}$$$. You can keep such "broken" pairs of blocks for each log-level if you do segment tree updates, and verify the vertex against it's left and right neighbors

I think the $$$10^6$$$ is meant to prevent some $$$O(n log^2n)$$$ ideas for D2 like maintaining a set for each $$$2^k$$$-sized interval.However they didn't make it tight enough to prevent some $$$O(n log^2n)$$$'s from passing on D1 (like sorting on each $$$2^k$$$ interval)

Here is from somebody in my friend list Solution

In problem c the only observation was you have to see how many 1's you have to invert as you can invert any number of zeros with a 1. So if number of 1s to invert are even than answer is 2 otherwise answer is 1. However you have to also check one case where number of 1s to invert are zero but there are zeros you have to invert to 1. so in this case the answer depends on whether ther is a 0 that doesn't need to be inverted in which case answer is 2 otherwise answer is -1.

edit: yeah there is one more annoying case when there are no 1s than the answer is -1. I was dumb enough to get wa on this case and got stuck in it for nearly an hour :(

If subsequence of elements that must be inverted consists of only 0s, ans can be -1 or 2. If there is at least one index where ai=0 and bi=0, and at least one "1" in a, ans=2

Bro went from DSU to bs in 3 min :)

hi, can you explain mei D1

From the official Codeforces rules:

If a contestant submits several times a problem's solution that passes all pretests, then the last solution is considered as the contestant's verified solution for this problem. All other solutions will be considered as unsuccessful attempts.

New to codeforces and solved all the questions in a div 2? Lol

Fixed