TheForces Orz...

"I did nothing for this official round, but I did most things for TheForces"

O--O

Excitement limit exceeded !!

Orz Radewoosh.

Thanks, updated!

Orz k1r1t0

😎

Orz chromate00 round!

Thanks.

As a tester, I am also here to comment :))

definitely sir!

callmepandey Orz

Thanks for your support, have fun and good luck! (●'◡'●)

How can I be as good as you, Nanani. You are already a test for a codeforces round which is a achievement I've never reach. I hope I can one day be as 1% good as you, Nanani.

By the way, for reference, there once was a task with 5000 score in another round.

You'll enjoy them for sure.

Lord spotted of TOAS

OOOh, thank you very very very very very much.. I don't know what would have happened if you didn't tell us. Now, I started thinking of searching for another CP site.

Yeah, you should register, PURE MASTERCLASS from the problem setters.

It is related to the team's (setter/tester) subjective thoughts about the proportional difficulty compared to other tasks. It may or may not correlate to absolute rating, but we do aim for it to.

yes

You should not think about neg delta. If not in this contest, then in future you will become pupil. But , if you miss this good contest which is even rated for LGMs then, you will miss a good experience that you could have done.

goodluck, i hope solve 2 problems FAST xD

Nope! Well, maybe it might be, but my approach (please don't FST) was limited to MSD-RadixSort, bit manipulations, and basic combinatorics.

Good luck! Hope u can solve 3!

greedy

Iterate over rows from top to bottom. Notice for each 1 that remains in the current row, you are forced to use an operation.

Thus, the idea is to loop over rows from top to bottom and count the number of ones. Then, you have to find a way to efficiently store the effects of the operations on future rows.

This can be done by keeping track of the number of operations performed on each diagonal and using prefix sums for each row.

My submission: 220552191

if k is even, result is sorted string.

// * * means swapping elements above the stars
// **** means reversing elements above the stars

abndp
* *
nbadp
 ****
npdab
* *
dpnab
 ****
dbanp
* *
abdnp

abndp -(2)-> apdnb -(1)-> dpanb -(2)-> dbnap -(2)-> anbdp -(1)-> adbnp

10 more seconds and I'd have F, :(

If the window length is even then reversing the string will change parity of all values,thus each value can be positioned at any index(both odd and even) using two types of operations.

Because of the first kind of operation you can sort all the odd indices and even indices separately. Now if the other kind of operation allows to swap characters at the end of an even window then you can use it to send any odd index element to even index. This allows us to sort the whole array.

Assuming you got the part when window is odd. position 0, 2, 4 .. will be sorted position 1, 3, 5 .. will be sorted

Now, you have arrived at this, then you can change the parity of any element with even window which again can be sorted with i, i+2 swapping,

Think of it in this way, let's say you have $$$2$$$ components (graph) of even indexes and odd indexes. Reaching from one node to another means you can swap these $$$2$$$ indexes in the original string. Now if, $$$K$$$ is even that means you have an edge between the $$$2$$$ components of graph making it a single big component, while if $$$K$$$ is odd, parity of swapped indexes will not change, and they will still lie in the same component as their original one.

.

Let 1 represent a character than belongs at an odd position ($$$1, 3, 5,\dots$$$) in the sorted string and let 0 represent a character that belongs at an even position ($$$2, 4, 6,\dots$$$) in the sorted string.

Lemma: If we can make the string 011010...10101 equal to 101010...10101, we can always sort the original string.

Construction:

Start by moving the incorrectly placed 0 (first character) as far back as possible. Now our string is 111010...10100.

Now, reverse the first $$$k$$$ characters. Now our string is [0101...010111]10...10100 ([] contains the reversed part).

How many incorrectly placed ones 0's our string currently have? Before the operaiton, we had one such 0. Every 0 included in the reversed segment was good, so now they're all bad. The reversed segment included $$$k/2$$$ elements at an even position, one of which was a 1 and the remaining $$$k/2-1$$$ were 0's. These now became bad, so we have a total of $$$k/2$$$ bad 0's.

Now, we have $$$k/2$$$ incorrectly placed 0's. Thus, we also must have $$$k/2$$$ incorrectly placed 1's. We can move all of these to the first $$$k$$$ positions of the string and reverse that segment, making all of these good. This concludes the proof that it is always possible to do the operation required for the lemma, which proves that the string can always be sorted. $$$\square$$$

Let A be the minimal set of odd index values we would like to be even, and B be the minimal set of even index values we would like to be odd.

Clearly |A| = |B|

By induction, we only need to decrease the size of these sets.

Place some value of A at index k-1, and some value of B at index k

Preforming the window operations [0, k-1] and [1, k] will only change the parity of the values at index k-1, and index k.

So the order of |A| and |B| decrease.

Thank you so much, i am so happy that you love my problem! (〃'▽'〃)o

Dunno if this is helpful, but I initially failed this because I multiplied by $$$k$$$ instead of $$$k!$$$ when rotating some subset of $$$k$$$ rows. Fixing that got me AC.

Dunno but my solution ended up being very simple — rotate all you currently can in one direction (horizontal/vertical), switch direction, repeat.

Since I'm doing this for both initial directions, I had to handle $$$A=B$$$ as a special case.

I become Expert)))

If your solution for E is correct then it means you are able to solve it. The contest is over only means that it doesn't receive more submissions to judge for the standings and the rating which you can still earn whenever there is contest, it's not over for your journey on solving them.

For me I need about more 5 seconds to submit solution for C.

Cheer up bro! Let's get ready to revenge in the upcoming contests!

See my comment for my solution

Just do greedy?

DP, kinda like https://leetcode.com/problems/minimum-falling-path-sum/

AC with 2D Fenwick tree: https://codeforces.com/contest/1864/submission/220595323

wuhudsm has always been orz in problemsetting

C can be done using the concept of powers of 2

How to solve D?

Can you explain c ?

I think it's the same as my solution — for every pair $$$A_i = A_j = v \in [L,R]$$$, check if the maximum value $$$\lt v$$$ that lies between $$$i$$$ and $$$j$$$ is $$$L$$$, if yes then it adds one operation since we can't make both $$$A_i$$$ and $$$A_j$$$ zero "together", there have to be operations changing that maximum $$$\lt v$$$ between them to zero, then some separate sets of operations changing $$$A_i$$$ and $$$A_j$$$ to zeros.

I didn't expect G to have so few ACs during contest.