As a resident of a warm country I downvoted.

as a -ummm ughh uhhh yes

.

As participant I want to thank coordinator Monogon and authors Asymmetry and Markadiusz

Mental health is much more important than competitive programming, so take it easy, hoping for some well wishes from a fellow stranger.

That way it will clash with Atcoder ABC

I am a specialist and started giving contests on this platform from last year itself. Excited for this another upcoming contest!! All the best everyone!

why are you a foolishgoat ? Btw I just want to say that number of characters in foolishgoat is also prime (11)

don't make it unrated because the problems are really good.

20min. queue. Should be unrated

20 minutes here bro!! I feel the same

That might be a stack, not a queue then!

If unrated, my possibility of becoming newbie will be ruined for this time.

Same :sob:

If unrated, my possibility of becoming pupil will be ruined for this time.

Same here . 2nd person to Solve C . Also A and B were pretty easy but here I'm crying

3ms TLE kinda sus tho..

lol

where i can see it? im about first image

I_Hate_Swaps you shouldn't feel sad

problem B.Swaps

Thank you for your support :)

do kickstart that is in ~80 mins from now

:(

Since a[0]!=b[0] we need to make those two elements so that a[0]<b[0]

That is, we iterate all a[i], and foreach one we find the smallest possible j so that a[i]<b[j] That pair of i,j need i+j operations, we search for the min such pair.

We can find the smallest j for a given i by binary search on the prefix arrays of a[] and b[]. make preA[i] the smallest value in a[0..i], and preB[j] the biggest value in b[0..j]. Binary search the smallest j where preA[i]<preB[j].

well I think: 2020 -> 0022 -> 0020 -> 0002 -> 0000

2020 -> 2002 (swap 3rd and 4th element) -> 2001 -> 2000 -> 0002 (swap 1st and 4th element) -> 0001 -> 0000

NVM. Thought it was D.

Using SCC is a bit overkill and definitely a waste of time for this problem.

The goal (when checking if understanding the book is possible) is to check if there is a cycle. We can do that with a DFS (or multiple, in case of a DAG, which we are dealing with here) which, instead of marking a vertex visited, can set two different kinds of flags.

The DFS works as follows:

1. Set flag "in progress" for current vertex
2. Consider all neighbours, for each 2.1. If its flag is "in progress", then a cycle is detected 2.2. If its flag is "unvisited", then run the DFS on the neighbour.
3. Set flag "visited" for current vertex

We can count the result with a DFS too, using dynamic programming on a DAG. Every vertex with no outgoing edges receives value 1, because that chapter will be understood during the first reading of the book. Every other chapter will be understood after all its prerequisite chapters are understood, so the result for the chapter is the maximum of the results for the prerequisite chapters... but slightly modified to account for the order of the chapters in the book.

I'm not the best at explaining so maybe my code will help.

Video solution for C using topological sort

First of all, xor of all the elements of the array should be $$$0$$$ (xor of all the elements of the array isn't changed after any operation).

From here, I am assuming that xor of all the elements of the array is $$$0$$$.

If n is odd, it's always possible to change all the elements to $$$0$$$.

Note that if $$$a_{i}=0$$$ and $$$a_{i+1}=a_{i+2}$$$, $$$a_{i}\oplus a_{i+1}\oplus a_{i+2}=0$$$. This is the main idea of my approach.

Now select indices $$$n-2,n-4,...,1$$$. It's easy to observe that now the first element of the array will be $$$0$$$ and $$$a_{i}=a_{i+1}$$$ for all even $$$i$$$ less than $$$n$$$. First element will always be $$$0$$$ because it is the xor of all the elements of the array Now select $$$1,3,...n-2$$$. After these operations, all the elements of the array will be $$$0$$$ and total number of operations performed is $$$n-1$$$.

If $$$n$$$ is even, you can split it into two subarrays of odd length. So if you can find an $$$i$$$ such that $$$i$$$ is odd and xor of first $$$i$$$ elements is $$$0$$$, you can change all the elements to $$$0$$$, otherwise you cannot.

First you must have an even number of 1s in the array, otherwise it's impossible to change all elements to 0s.

Then group all the 1s in pairs: (1st, 2nd), (3rd, 4th), ... we will solve the problem by changing each pair of 1s to 0s repeatedly:

1. if there are an even number of 0s between two 1s, we firstly change those 0s to 1s by performing operations on i such that $$$a_i=1, a_{i+1}=0, a_{i+2}=0$$$ repeatedly. Then perform operations on i such that $$$a_i=0, a_{i+1}=1, a_{i+2}=1$$$. Note that assume the indices of the two 1s are $$$l$$$ and $$$r$$$, we must have either $$$a_{l-1}=0$$$ or $$$a_{r+1}=0$$$ in order to solve this case.
2. if there are an odd number of 0s between two 1s, similar to case 1, we first change all zeros to ones except for the rightmost zero. Now we have $$$1\dots 101$$$, then we perform an operation on 101, then do the similar thing on case 1 but from right to left. Note that there are no extra requirement to this case.

So the strategy is firstly find one pair that can be solved then solve the remaining pairs from that pair in both direction. If none of the pairs can be solved, it's impossible to change all 1s to 0s. Submission: 129221560

since array a is odd numbers and array b is even numbers.
so lexicographically smaller/greater is defined at index 0.
so only comparing values at index 0 is enough


let cost[x] = # swaps to move a value v < x in array 'a' to index 0.

ans = 2n
and iterate over i = 0 to n - 1:
  ans = min(ans, i + cost[b[i]]); // i <- #swaps to move i_th number in array b to index 0

if iterating is over.
the ans will be the answer

----------------
how to create cost array?
intialize cost array with max value = n
for (int i = 0; i < n; ++i) {
    cost[a[i]] = i;
}
for (int i = 1; i < 2 * n; ++i) {
   cost[i] = min(cost[i], cost[i - 1]);
}

can you just briefly explain what you are storing/updating in the nodes?

1
4
3 2 3 4
0
2 2 4
0

Correct answer is 3 yours gives 2.

I have used a similar approach with the topological sort, except instead of storing the chapters to be read in the next iteration in vec, i just added n to the chapter and pushed it into pq. 129229753

Maybe you can solve the task in each bit, but the operation times may exceed $$$n$$$.

I think my solution doesn’t use the 0/1 condition so probably yes.

is the editorial rated ?

You are only considering making the swaps on either a or b. In some cases it is beneficial to do the swaps on both arrays.

Yes!.. No? Maybe.

Check this solution out!