Hello, Codeforces!

I'm glad to invite you to my first round Codeforces Round #632 (Div. 2), which will take place on Apr/08/2020 17:35 (Moscow time).

"Thank you" time!

I'd like to thank:

- antontrygubO_o for coordination of the round.
- 300iq, nvmdava, aryanc403, antoshkin, lkosten, pavel-afonkin for testing and useful advices.
- MikeMirzayanov for great systems Codeforces and Polygon.
- CuriOusQuOkka for listening to my mumble while I came up with tasks.
- antontrygubO_o for coordination of the round (again).

You'll be given 6 problems and 2 hours to solve them. Point distribution will be announced as soon as possible.

Hope you will enjoy the round! Good luck and have fun!

**P.S: YES, IT'S RATED.**

**UPD**: Score distribution: 500 — 750 — 1250 — 1750 — 2000 — 2500.

**UPD2**: Congratulations to the winners!!

Div2:

Wow, there is no unrated in div2 round!

All:

**UPD3**: I will post solution in several hours.

**UPD4**: It was very long several hours, I'm very sorry for that :( Editorial

Auto comment: topic has been updated by ReD_AwHiLe (previous revision, new revision, compare).Hope it will be rated. But im pretty sure it won't.

Actually it is rated

Is that your real face in your profile ?

I'm sad because I won't be able to score in this round

But still your rating will not be updated .

why not?

I think Masters aren't trusted participants in Div 2.

Hope your dream of become rated in div2 contest come true one day

why aren't there more contests?? :(

Because it takes time and effort. You can solve practice problems at any time.

:v

You can solve practice problems right now and become expert in only one rated contest!

But... This requires work... I want instant gratification! (•̀o•́)ง

But there is no shortcut for instant gratification in competitive programming.if u practice more then u will need less contests to become expert.

Aaaaaaand you missed the joke :))...

OH.Cool next time i will try not to miss.

Whoosh

Because it's not easy for problem setters to set a problems with good test cases within a day. It takes a lot of effort to think corner test cases. One of my friend was problem setter it took 2-3 days to make 1 problem with test cases.

yes definitely and it is codeforces not normal coding platform such that problem makers will make problem easy ; they have to think twice while making it a problem whether it will be very easy or not or something else.

You can find list of competitions on other platforms here

Good Job. It is your first contest. I hope it will be good

I think I saw a few days ago that the round was of 2.5 hours. Correct me if I am wrong.

Its true and it was my mistake. Sorry for misleading. Round will be 2 hours long.

can you post link of previous contests by you ?

Hoping for no queueforces and strong pretests!

I pledge not to submit without checking the sample cases.

Nope! I code in submit page and I submit without compiling.

Great bro! I need that level of confidence in my life XD.

That level of confidence in real life can be real baad!

Well, this kind of joke in real life is very baad.

are you sure?

I am pretty sure. :P

Now I'm thinking there should be such a round every few months. A 'No IDE' round, only Notepad.

No need for Notepad, just type into the "submit code" tab! ;-)

Is it really RATED???????

yes it will be rated for division 2 .

Of course and without jokes

Nah,man.We are all messing with you (even the contest statement) :/

Coding > Singing

isitrated?

Yes of course it is rated.

no, itisrated

I think u are trying to comment some thing.lol

I hope i'll become expert in this contest

Me too , good luck :)

is it rated?

Of course rated.It's a normal division 2.

Why are so many people asking this question over and over again？

May be to get downvotes

May be they wanted to increase their absolute value of contribution.

Many contestants had trouble entering competitions at work and study times, but now everyone in home, so let's have fun. good luck everyone ^_^

rtd?

Yes, in bold at the bottom, it says:

"P.S: YES, IT'S RATED."rtd for me?

In that case, no, as div. 2 means under 2100 rating

thx

Darn had to be one day before my birthday T-T

I hope strong pretests are there this time.. Can't we have both strong and small number of pretests?

I tried to do so :)

I hope to become a

specialistin this round!good luck!

All the best :D

*Codeforces round starts*Codeforces servers:

наелся и спит

Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com.

I hope to get Candidate Master in this round!

You didn't even participate...

Perhaps he started, and did not submit anything. Like me.

Thanks, you both didn't participate, otherwise my rank must be (current_rank + 2)

I just had a sleepless night, so I skipped. It was unfortunate. However, I participated today but was slow on D. I will try my best on the next one!

I know, you will very soon become Candidate Master..

Congrats on your first round. Looking forward to solve your problems

contest made life easier to pass quarantine

Why so negative?

GO CORONA CORONA GO ....

Ｉ got 2 "fst" in the last round, then I became blue. So I hope this round will have strong pretests.

Any suggestion how should I practice to become a blue coder? Nowadays codeforces is giving hard implementation problems in c no and I find it hard to solve somehow.

Solve a lot of Div. 2 C and D problems, they are great for practice. Also, try to upsolve at least one problem after each contest. For example, I see you solved A and B in the last contest. Try to solve C, it's a good problem.

I'll try :) Thank you

C was a nice one

how to solve C ?

May i ask how many hours you and whoever helped you with making problems in polygon spent on the contest?

Hm, I don't know... Maybe about 15-20 hours I was spent only with polygon, without creating test scenarios and problems, just for writing code and statements. It took much longer to come up with the tasks (~1 year). But it was passive work. One month I didn't do anything, and the next I create 2-3 tasks.

Thanks for reply, i hope you get better and better in problem-setting, i think 20 hour is very nice for the first time :).

Thank you for putting in the effort to create the contest! Wishing everyone luck.

you make me green this time i dare you

Congrats, I'm excited :) I hope there is going to be more contests.

Constest starts... ... Codeforces servers down

True :(

If we register for the contest but don't enter it. Will my rating still go down?

If you don't submit anything, it doesn't count as a participation.

thanks :)

What about F? :)

I wanted to put it but each line has 2 photos I Didn't want to ruin that :P

Press F...

no me

We want more contest!!!!!!!!!!!

Don't be so entitled, just be happy for the contests we get and for the efforts that the creators put into it. If you want more contests you can solve old ones at any time.

Any particular reason for thanking antontrygubO_o twice for coordinating the round?

This round would not have existed without his help during the entire preparation process. This is my way of especially thanking him :)

I think if someone accepts my contest proposal after 3-4 months or more, then i would be too happy to just thank whoever accepted my contest less than 2 times, or maybe just because anton helped him with making problems(then its one for accepting the proposal and reading it perfectly, and one for helping with making problems as a coordinator).

Even if there aren't a lot of contests on CF,there are a lot of contests on different platforms.Stay inside and safe!

Codeforces contest coordinators have been pretty lazy recently. Bad pretests, not many contests to begin with. Out of all the contests they still turn out bad.

I don't think you have a good understanding about coordinators' work, they are not making contests, they check contests made by Codeforces Community and help them to prepare the contest as well, which really takes time.

Maybe it takes 2-3 day to prepare a contest, and there is tuns of contest proposals, it means tuns of tuns of problems, reading a contest should take about two hour at least, so even if 4 man are working 6 hours a day for preparing contests and checking contest proposals, then they can at most check 10 contest proposals in a day, which i dont think is enough for such a big community.

So guess what, can coordinators spend some time on they're own?, far away from working and reading random proposals? for sure they have to sleep.

I know there is few number of coordinators, and not all of them work full time for codeforces, probable the only way to increase number of good contests is to support community to make contest proposals more perfectly and prepare they're contests faster(codeforces is really doing it very well i think), or if the problem is the really long queue of contest proposals(which i think is the case), they may increase the number of coordinators and support them.

Fully related to the topic: I wanna be a coordinator later in my life, so i should plant the seeds from now, yes? =P

Thank you!

@ReD_AwHiLe hoping for the short statements and strong pretest.....?

We want more contest in this quarantine :(

I don't understand why people commented asking this and got lots of downvotes, though it's clear in the post.

Maybe people are getting bored staying home and commenting to have fun.

I don't understand why you are getting so much downvotes .

Is she rated?

And then you make memes xD

Div 1 coders in Div 2 contest everytime

I will just print Hello world then

I was doing this today for div2 C XD

Please arrange more contest during these corona days. :p

We try T_T

I hope there won't be a long queue, good luck:)

I can't able to submit solutions in JAVA, getting RUNTIME error, tried with previous accepted submissions. I don't know where to post this, this site doesn't even have a contact page.

Got it I forgot to remove package declaration at top.

Better post a link to one of those submission, then somebody can tell you why it fails.

hope this contest not to be like previous one !!

!

TRUE AF

I will provide you video tutorials for the round after it's done!

yes please

Whats ur channel?

I think it's called Algopedia (not sure tho)

Algopedia

Here it is brothers: https://www.youtube.com/watch?v=SS5eONgsluE&feature=youtu.be

Your photo is so cute.

O kawaii koto

All the best for your first contest. Nice time to get better at CP in this quarantine. Thank you guys.

what is score distribution for this contest?

It will be announced 10 minutes before the contest

CF-Predictor, In the last 6 contests he was giving wrong results, I hope that the mistake has been fixed and gives correct results in tomorrow contest.

Maybe,

CF-Predictorhas Coronaforces XDI am here after almost 11.5 months! 18 months if we ignore one-off contest I participated last year! Feels great to be back!

And I see that the number of participants has gone ~23-24k over past few contests. Used to be ~7-8k back in my days!

Great job guys!

It's Corona time!

Don't you guys use TikTok? Why so many downvotes??

Contest registrations are increasing at a higher rate than the COVID-19 cases.

I hope to become a specialist and stay that way .....

Best of luck^_^and i thought my graph was funny

I cannot register for the contest.

Yea, I'm facing the same issue

Me too.

Я почему то не могу зарегаться, выходит окошко Ooops! Something has broken down in Codeforces. Do not panic, you can try to reload the page or return Home Шо делать?

give me one contest please let me be green

I will be master tonight. Screen it

Wait, 2 more hours!! :p

Wow, you really did it

I became Candidate this round)

nice done :3

Dear Codeforces web developers, there is a typo in setting->social->city section which is "City where you live

otcity you are representing"It is city where u are representing.

I highlighted the typo! it should be

`or`

not`ot`

ohh i mistaken it .I thought whether u are asking about the city.

Hope we can all score and make progress in this contest!

Finally, a contest after so long...

Hoping for small queus, and strong pretests, gud luck guys...

I think the round isn't simple(for a newbie) My English isn't very good，please forgive me.

Why make such a pointless comment in the first place if you're so worried about your english.

Sorry，it's my problem

Why hasn't the score distribution been published yet?

Already published . you can check that now .

Here it is!

I am enjoying by reading comments.

First contest for me too, wish me good luck :D

I hope it is a nice competition and we earn points in it ..

best of luck.

this my first contest. hope to solve many as possible..

good luck.

I did some virtual contests of division 2 ,i would try to give my 100%. No matter whether my rating increases or decreases .wish me luck and beft of luck to everyone.

Hope this raund will help to me be 1600+, good luck all

hope so.

22k participants ? can a rank under 3k will make me XXXprt

on each contests .. people ask "is it rated" for atleast 5 times.. probably gonna change my username to "alwaysRatedPleaseReadFirst".

thats moment when div1 participants not able to solve div2 D or even C

thats mean it will be fair contest for div2 participants!

thanks!!

nice round. I solve F and fail at C.

Seriously man. After seeing div 2C, I was like I am no more div 1 :D

I used Segment Tree to solve C:) It's more like a Div2D, if you ask me.

Can you explain your idea on how to solve using segment trees.?

Basically I try to count the number of bad segments. Lets fix the right border $$$r$$$. Now the segment is bad if it has some zero sum subsegment. For each $$$r$$$ lets find the biggest $$$l$$$, such that sum of $$$[l, r]$$$ is zero. Now if our right border is more (or eq) than $$$r$$$ and left border is less (or eq) than $$$l$$$ it's a bad segment. Now we are doing scanline and whenever we see $$$[l, r]$$$, we update some prefix with ones. You can do this even without sgtree, but I didn't think of it on the contest.

My approach is somewhat similar, but I don't know why I'm getting TLE my code

Try using map instead of unordered_map

Thanks! It worked, but why unordered_map was giving TLE?

Welcome to the club buddy. C++ unordered_map uses a fixed modulo, so it can be blown up to $$$O(n^2)$$$. You can look at this blog, to know more.

Thanks for enlightening me :D

Interesting problems, but I think they are too hard for Div2

I have never related to something so hard.

Even though I didn't solve C but I solved D and I think it's because my mind was not clear.

relatable :/

In Problem C I dont know what the Pretest 8 was but I wasnt able to pass it till end of contest

Maybe this:

ans = 12

Why the hell would you make 4 heavy implementation problems in a row. We are so fucking tired of debugging and shit lord.

What are you talking about? These problems required a few good observations and had simple implementation. I mean first three problems needed less than 40 lines of code.

Hilarious

I Got Internet disconnection due to my provider problems and i got connected about 30 mins ago

Is there any solution for me ?

Yes. Get a new Internet provider.

LOL! For some reason, I pictured Jian Yang from Silicon Valley saying this..

I have friends who face similar issues. All internet providers in Egypt are terrible. I don't think codeforces will do something about though, since it's not an issue a lot of people face.

In Div-2B, I was first solving the wrong question and stuck thinking that we can a[i] to a[j] and a[j] to a[i], instead of only able to add a[i] to a[j] for i<j. Can someone tell me how to solve the above version of the problem ?

Video editorials for C and F out!

C

F

I think it's great to have short explanations in video just after the end of the contest. If only I could press like multiple times!

Still didn't get C. During the contest I figured out how to find out bad subarrays using prefix sums. But then I need to remove all superarrays of this bad subarray as well. I was counting it twice in some cases. How are you handling this? I didn't get that.

Basically, I keep the rightmost starting position of such a subarray.

This helps me to count only the subarrays starting at positions which are bigger than that position.

for each index i, find how many subarray ending on that index have sum non zero, for that, we find the highest index j < i starting from which, sum is 0, then we know ans += (i — j);

How to solve C?

Right above you :))

I solved using map and prefix sum .We can calculate number of bad segments .Suppose while doing prefix sum we calculated value 'a' till position 'i' and suppose last such value 'a' has been found at position 'j' , then sum of numbers from 'j'+1 till 'i' is zero and number of bad segments it contributes is equal to (j+1-las)*(n-i+1) (provided (j+1-las) is positive) where 'las' is left position of previous such segment whose sum is zero. We include 'las' to avoid adding contribution multiple times.

submission

How comes that it contributes $$$(j+1-las)*(n-i+1)$$$

suppose array has length 20 . Let first segment whose sum is zero is [3,6] then number of bad segment is contributes = 3*15 . Now let next segment whose sum is zero is [8,12] then number of bad segment it contributes is 8*9. But [2,13] is calculated for both segments . Hence we use las = 3 for second segment.

I thought in the same way. But couldn't implement it. I missed the point of multiplying it by (n-i+1) and I ended up adding n-i+1 only :-(

Hey. I was trying on similar grounds during the contest and I am still trying to figure out my mistake. Can you please help me out?

Here is my submission: 75899238

I think it would be more convenient if you count the number of good subarrays. Just store last index position of the prefix running sum and the answer is equal to the i-map[prefix_sum], update map and last position at each index.

It would be very helpful if I could get any feedback on my code.

Your explanation is very clear, thanks!! I was just facing the problem of adding contribution multiples times.

even I did the same way..problem was not that difficult. My code is clean so may be easy to understand MY CODE: https://codeforces.com/contest/1333/submission/75954346

Another problem on similar concept is : https://codeforces.com/contest/385/problem/B ENJOY

1333C - Eugene and an array It can be solved using hashing/ mapping. Firstly calculate the prefix sum or cumulative sum. To check the 0 sum subarray. Visit this link for more details ... https://www.geeksforgeeks.org/find-if-there-is-a-subarray-with-0-sum/ ...

Then, iterate through the prefix sum and check whether it came before. If the prefix sum is repeated, then it indicates that the 0 sum subarray has.

Then, increasing the pointer to that place, where all valid subarrays have found. My solution : 75964709

Cheers, another crowded contest end. Look at the number of participants.

The contest ran smooth tho (for me, atleast). Normally, I'd face lag while submitting and loading problems but today it was different. Submissions didn't last in queue for more than 2 secs. Really nice problems too.

Was the n=3 case for E possible or not? I thought it wasn't (couldn't find a good proof but spent a while trying to construct cases to no avail, but I got WA and I was pretty confident about my construction for n > 4.

It's possible

Same problem, for n>4 you can just copy his solution and add stuff the border, but not sure for n = 3.

1 2 4 5 3 8 9 7 6

SpoilerSeems to work for n = 3

Hey man , How your contest rating went up ?

??? This has nothing to do with the contest lol you can just message me about that

bruh

what is pretest 5 in C

I suppose this is the test like:

5 -1 0 0 0 1

or

5 0 1 2 -2 -1

or

6 1 2 4 -5 -1 -1

After I fixed this I got all pretests passed.

the same as me

my solution was failed at pretest 5 too!!!!

I am not sure, but try this:

Expected answer should be 2

your testcase is very helpful ,thanks a lot

For me the text of problems was hard to understand. Especialy 1333A - Little Artem was demotivating, since the expectation to solve a more or less nice first prob was not met.

In D i was getting TLE just because i was using endl instead of "\n".

What is pretest 7 in D?

I think it is something like 6 6 RLRLRL After accounting for this TC, i got AC. Previously, my solution too was failing on TC7

My code gives the correct answer for this test case. So, it must be something else.

I don't think so. My code is also giving WA on Test Case 7 but it is giving the correct answer on the Test Case that you mentioned. T-T

Lol i randomly started my comment like you xD.

I dont think so, i know what i missed and i got wrong answer in testcase 7, but i'm pretty sure that its not the case, i say something like 6 7 RRLRLL.

DeadlyCritic bingo

Did you know how happy i was when i saw that after years someone called me? happy to hear that.

WTF, how to solve B and C?

For C, check my video editorial, the comment is on the blog!

For B, I think:

If $$$B[0] != A[0]$$$, solution is not possible.

Else, for every position starting from 1, if $$$A[i] > B[i]$$$, you need to check if a -1 exists in A [1...i-1], if $$$A[i] < B[i]$$$, you need to check if 1 exists in A[1...i-1].

Something like this maybe:

CodeCan you tell me how did you post your code such that we can collapse it? I always wanted to know lol

Use

`Spoiler`

.Zeus_Not_Zues I have a doubt, A=[-1 3 0] B=[-1 1 2]. Output is 'NO',But if we choose (0,1) twice -> A=[-1,1,0] and (1,2) twice -> B=[-1,1,2],we can convert array A to array B. any help would be appreciated.

Your A is an invalid array. A can only contain elements {-1,0,1}.

So, if you go step by step through my code, you'll see that A = [-1 3 0] would become equivalent to [-1 -1 0]. And it is impossible to obtain B from this A.

yeah,,how did i miss this!!!! Thank you very much....

Nice Solution.

My first two submissions in the contest: WA Time I finally solved A: 16 minutes into the contest Codeforces DELTA: +125

This round was so cool! Thank you all who preapred this wonderful competition!

when will the editorials be out??

The verdict I got for problem E seemed wrong to me, am I missing something?

Input : 4

Output:

1 2 3 4

13 15 16 5

14 12 11 6

10 9 8 7

Verdict: wrong answer rook teleports: 0, queen teleports: 0

Doesn't queen teleports 1 time?

Link to submission: http://codeforces.com/contest/1333/submission/75904855

No it wont teleport at all, u could use the output examples in the statement instead of finding the answer for $$$n = 4$$$.

No. The queens route is:

1 2 3 4 5 6 7 8 9 10 12 11 14 13 15 16

If I'm not wrong.

oh i see now, i thought we cant go through visited cells. Thanks.

Can anyone explain how to solve C ?

Its a simple prefix sum problem.

For each index i, calculate the next index next[i] such that the interval [i..j] has a sum of 0 (this can easily be done with a map and prefix sums). If no such index exists, let next[i] = N+1.

Then, the answer is just the sum from 1 to N of (next[i]-i), since these are the number of arrays that don't have a subarray whose sum is zero.

Thanks for the explanation it really does make sense now. However, I am still failing test case 5, I have no idea why, do you mind taking a look at my submission (anything I am doing wrong)

My solution: maintain on the prefix $$$ [0, p] $$$ such maximum $$$ i $$$ that there exists $$$ j $$$ such that $$$ [i, j] $$$ is a bad subarray.

Then let's count the number of good arrays that end in $$$ p $$$. For that we notice that any array $$$ [l, p] $$$ with $$$ l \leq i $$$ is bad, and any with $$$ l > i $$$ is good.

When I see such questions like counting subarrays I usually think in two ways:

Iterate over lengths of subarrays i.e. count valid subarrays of length = 1,2,3,..,n and so on. OR

Count number of valid subarrays starting from index i = 1,2,3,4 (assuming 1-based indexing).

In this case, I used the 2nd way.

For each index

i, count how manygoodsubarrays exist.How?

i. If there exist multiple such subarrays, take the subarray with minimum ending index. (Why?). If there is no such subarray starting fromiand having sum = 0, then store (n+1) for that index.Let this be stored in

subarray_becomes_zero_at[].subarray_becomes_zero_at[i] = jimplies subarray from [i+1,....,j] is a 0-sum subarray. This basically happens when prefix_sum[i] = prefix_sum[j].For iterate from right, and store what is the minimum j >= i and k >= i such that subarray_becomes_zero_at[k] = j. Let this j be stored as

can_go_till[i] = j. This means, from every starting indexiyou can go tilljth index without having any 0 sum subarrays in it.ans = sum(

can_go_till[i]—i) for every1 <= i <= N.looks like Div 1.5

God I literally misread B and for the entire contest I thought there was no restriction $$$ l < r $$$.

It was a horrible feeling of absolute stupidity when you see over 9k people having solved it and having absolutely no idea of even approaching it.

Luckily I could notice it in the end and implemented it in the remaining 5 minutes but god was it stressful.

Also it is actually now interesting how to solve that (apparently MUCH harder) problem.

same :-(

Lol same here. I made the same comment above. I was stuck in B for a long time, then moved to C and was able to solve in 15 minutes and again came to B and thankfully saw it.

i dont know ..what i did wrong in B? couldn't think of any case failing?

same :P

How could we solve the harder version B? If i<j constraint wont be there?

I actually thought that this was B and was not able to solve it till the end when I noticed the constraint $$$i < j$$$

I believe the question becomes slightly easier if the constraint i < j is omitted.

If A does not contain -1, but B contains a number lesser than its counterpart in A, solution is impossible. Likewise, if A does not contain 1, and B contains a number greater than its counterpart in A, solution is impossible. 0 in A would not play any significant role.

I think a harder version of this problem would be if we were only allowed to use a pair of indices (i, j) only once to construct B or maybe if A consisted of other elements instead of just (-1,0,1).

It is not possible in those cases. But they are not the only cases where it is impossible. It gets very tricky to choose the order and which element to use first.

the hardest c I’ve ever met.

Yup, A and C were extremely hard for their problem class.

A was pretty simple. Just print white in the top left cell and black for all the rest.

i am crying now!!!

Yup, I figured it out too in 7 minutes. But still, I think A was extremely hard for a D2A.

Doesn't make it a bad problem though, just should've been a B and C should've been a D.

yeh, 30 mins for solve A, unsolved C and -100 rating! Good job

me either lol

me toooo..

Needed swap(E, F)

swap(F,D) would be better

Actually I think swap(C,D) and swap(E,F) would be ideal. D is more straightforward than C IMO.

swap(A,B), since A has some pitfalls if you do not see one of the simplest solutions in the first place.

I think F is even easier than C,it took me half an hour to solve C and got WA one time,an hour to solve D and got 3WAs and 1TLE,but only 7 minutes for F and passed it.

Pending system testing.... There are nervousness in Codeforces... XD HI! How solve C?

The problem C bothered me too much, This is not an enjoyable contest.

listOfAuthorsWhoSetBadContests.push_back("ReD_AwHiLe")

Why such a hard C?

You know it's a fair contest when div 1 Candidates have to go through div2 Problem C and D's editorial !

I dont have any idea how people could solve problem D, the solution for E was expectable, sadly i got stuck in case $$$n = 3$$$ for an hour i guess, after all it wasn't a bad contest if it had a little less ad-hoc problems, in fact i say solving problems in this contest needed luck more than coding power and knowledge.

It was a little modified bubble sort, you have to sort the array. Record all the swaps you can do in one pass, then make those changes, then do the same again. After we have all the operations required. Just distribute them into k groups.

I tried this algorithm, but am getting Wa at test case 7 -> submission

Here is my submission Let me explain a bit more

We just have to sort the array. We traverse the array and store the places we can do an operation. Now after we have recorded the possible operations in one pass. Now make those swaps. This way do it n times. Store all the swaps required to sort the array in n arrays. So we store in a vector<vector> operations all the operations we can do in the ith pass.

At the end, you will have all the swaps that are needed. Thus we also have the operations.size(), which denotes the number of passes required to sort. Let's call this min_operations.

Total count of all operations is max_operations needed to sort.

Now min_operations <= k <= max_operations

Let's take an example k = 6 string = RRRLLL

so min_operations = 5 (if we swap all possibilities at once) max_operations = 9 (if we swap one by one)

now if k = 6, we divide them into 6 groups instead of 5 I just used greedy for that, I filled them by one by one and k-=1 Until k was equal to the number of groups(indexes left) So we got our final answer.

Here is my submission for reference. https://codeforces.com/contest/1333/submission/75908994 Can you stop downvoting me now guys. T_T

Thanks a ton for the detailed explanation! I'm finally able to understand what's happening

My approach was exactly similar, but couldn't pass TC 7. I guess there was some mistake in the implementation. Thanks a lot, bruh.

@sonu628 The mistake you have made is you have made the changes while storing the swaps. So in a case like RRRLLL You first swap RR LR LL Then you can again swap here, which is wrong.

So we will first record the indexes we can store in an array. And when the inner loop is over, then we make those changes. So you should do something like this

Code...

Also note that inner loop goes till n-1 now everytime.

yeah, saw that after some time. The algo does work, thanks mate finally ac submission

I had an off-by-1 error on D, which I noticed a couple of seconds after the contest ended. I haven't felt such frustration in a long time.

Can you discuss your approach to D?

You can notice that the head turn has the effect of turning a

`RL`

into a`LR`

i.e. moving one`L`

one position to the left. It's easy to see now how many moves you have to make (i.e. the number of times you have to move an`L`

to the left, until all`L`

are to the left). Let's call this number`needed`

.The maximum amount of seconds you can have is if you do only 1 move per second, so that is

`needed`

seconds. Therefore, if`needed`

is less than`K`

, we have no solution. Then, during each of the K seconds, while`needed`

is still bigger than`K`

, greedily do as many moves as possible. Each move decreases`needed`

by 1. At some point,`needed`

will either become equal to`K`

, meaning you will successfully finish with 1 move per second, OR it will stay bigger until the end, which means there is no solution.It's no were written that

if "needed" is less than K, we have no solution.It says you have to do the process in exactly

`K`

seconds. If you only do 1 move per second, you will have`needed`

seconds, and that is the maximum amount of seconds you can have. Therefore, if that maximum number of seconds is less than`K`

, you cannot do it in exactly`K`

seconds.