# Hi Codeforces!

Igorfardoc, Vladithur, Alexdat2000, gluchie, DeMen100ns, SPyofgame and me (spelling "thanh-chau-n-s-2") are delighted to invite you to participate in Codeforces Round #842 (Div. 2). **This round will be rated for all participants with a rating lower than 2100.**

- Start time: Jan/05/2023 17:35 (Moscow time)
- Duration:
**120 minutes**. - Number of tasks:
**6**.

**This contest is brought to you by**

Special thanks to:

- errorgorn for his wonderful coordination.
- Vladithur for providing wonderful problems.
- Alexdat2000 for testing and translating our statements.
- Vip testers: Valenz, who spotted some critical issues in the problemset.
- Alexdat2000, Igorfardoc, SPyofgame, gluchie, DeMen100ns for helping us in some different phases of preparing the problem set.
- All-time mighty
~~red~~cyan testers: gyh20, Chenyu_Qiu, xiaoziya, feecIe6418, Little09, ShmilyTY, thenymphsofdelphi, neko_nyaaaaaaaaaaaaaaaaa, 6aren, tfg, Andreasyan, generic_placeholder_name, Mangooste, BucketPotato. - Other testers: darkkcyan, maomao90, tibinyte (absolutely
~~fake~~true color), Gheal, bugdone, valeriu, satyam343, alecs, 1DWalker, aineee, nyagami, vangtrangtan, hydroshiba, E404_Not_Found, DMCS, Duy_e, LetterC67, Ignr_h31, TrendBattles, kodomotachi. - Other people for some reason cannot participate officially in this round: QuangBuiCP, LeCaToX, dinhsangBKA, Hungconmk, antontrygubO_o, 74TrAkToR, felys, Qingyu, alexxela12345, _FireGhost_.
- MikeMirzayanov for amazing platforms Codeforces and Polygon.
- Last but not least, you for participating and then being rage while implementing some 200 lines of code.

Edit: there will be $$$2$$$ packages for two participants in Vietnam, the highest score and the luckiest. You have to set your region to Vietnam to be qualified.

The score distribution is $$$500-1000-1500-1750-2250-3250$$$.

Hope to see you in the final standings!

**Editorial is out.**

**Congratulations to the winners:**

Div.1+2 | Div.2 | |
---|---|---|

1 | arvindf232 | drizzlo |

2 | Hyperbolic | jiangly_fan_fan_fan_fan |

3 | drizzlo | BedzieMagikZa2Lata |

4 | jiangly | BeautifulChicken |

5 | Um_nik | AE-3803 |

**And the first solver for each problem:**

A | B | C | D | E | F | |
---|---|---|---|---|---|---|

Div.1+2 | dapingguo8 | tourist | youknowiknowyouknow | A_G | nok0 | jeroenodb |

Div.2 | celestialcoder | 1024mb | youknowiknowyouknow | MIOC69 | cmk666 | drizzlo |

As a slave~ setter, wishing you all peace, joy, and unconditional love at Christmas and always. And of course, with ++rating :Đ

As a tester, love you SPyofgame

love you SPyofgame orz

As a person that likes the colour cyan, this post is just pleasing for my eyes.

As a tester, I'm only GREEN.

But they promote me to...cyan! Thanks a lot. >_<

SpoilerAnyway, give me contribution.

You are a green with the power of a grandmaster, and that is something to look up to.

Spoileri want contribution too :)

I as participant i love you aineee

As a tester [insert joke]. I liked the problems as I've put some effort in upsolving, hope you'll enjoy them as well.

I like the way you made your rating become that beautiful number lol

permutationforces

Flashback

It's hard to increase your rating by only one.

`++rating`

I did that. actually

prvocislo: And I took that personally.

lol and then they removed cheaters and rating++ was gone :')

Nah because it was ++rating++, the bonus score is the gift from the main route mission to LGM.

Thank you! I wish you the same! May this year be the cause of new titles.

Good luck to all! I want to become a student in this round! and thank you by the way

I am a setter.

As a do-nothing-setter, gluck everyone!

As a do-nothing-setter, I found another do-nothing-setter and that's pretty POG.

As a tester, Merry (late) Christmas everyone!

Hi!As a tester,this is my first time.Also,i want tell you something important

Spoilerneko_nyaa has 17 ‘a’s on his name

cyanforces

As a tester, I can guarantee that you'll find interesting tasks in this round! GL & HF.

as a tester, nya

Cyan Supremacy

As a tester, this contest is worth participating and learning how to brainstorm ideas efficiently. Good luck and have fun in the last days of 2022!

Um_nik will finally be deemed less worthy after this cyan round.

omg cyan round

omg cyan round

omg cyan round

omg cyan round

omg cyan round

omg cyan round

omg cyan round

omg cyan round

omg cyan round

omg cyan round

haaa

omg cyan round

omg cyan round

omg cyan round

omg cyan round

omg cyan round

omg cyan round

omg cyan round

Broke your silly chain haha

omg cyan round

omg cyan round

omg cyan round

omg cyan round

omg cyan round

omg cyan round

omg cyan round

omg cyan round

omg cyan round

omg cyan round

omg cyan round

omg cyan round

omg cyan round

Regardless of my experience testing this round, the problems are good.

omg cyan round :)

As a cyan tester, I recommend partipating

orz feecle6418

as a tester, this round is better

Hoping for a problem E solvable for me (to keep my current rating)

Please downvote me

Round of specialists! (NY's magic)

I enjoyed the "you" trick and the hidden text (doesn't work on the dark theme).

still work with me

CYAN IS EVERYWHERE!

cyan round, so maybe i've got a chance

MikeMirzayanov😎One of the most visually pleasing announcements!!

This round should be named "Specialists Round"

omg cyan round

great contest will arise tomorrow...

definitely it will be a great and awesome contest. So all the best. All the best everyone

How about every participant changing their color to cyan for this round ?

Or they get so much -ve delta that they become cyan

You are on your words, LOL!

I am in, lol

Done !

Hope I don't become green after this cyan round.

1000 cyans versus a LGM, just as in the old days.

Hocus Pocus Abrakadabra , turn me into cyan

Viet Nam contest legoo

Cyan_Forces ✪ω✪

wow, Filled with cyan on all sides

Very eager for upcoming contests!!

cyanforces

You copy my comment

Wow. what an environment.. cyan on everywhere

Help -is-this-fft- finish off 2000 problems.

The most

cyanround ever. It will be interesting!so~so~so~so~so~green~ ovo!

Why is everyone cyan now?

It's fun and nice

craynforces

"you" is a good highlight.

Time for VietnamForces!!

Specialist Forces

I like the specialist magic here! Good luck everyone, have fun!

Today I feel Vietnamese.

OMG. Cyan round.

Cool fact that div made by Russians and Vietnamese while im Vietnamese but born in Russia... Great job guys!

Specialists are ___!

Wish everyone can solve more problems in this round.

Nice editing for last point.

Div2 finally, its my time to shine!!

Hope to get Master again!

This second competition this new year. I'm sure this competition will be great for everyone. Good luck! Let +1000 be added to your ratings.

Thank you!

Everything Cyaned !!

I love you!

as a tester, wishing you the best, gud luck.

is the contest unrated?

Added that it's rated for everyone with rating < 2100.

how to calculate the contribution?

I pressed on LG "you", but it shows me grey :|

THE ONE PIECE IS REAL!!!

And I'm gonna get it

Excited for this round.

DeMen100ns, what the ..?

it's just rollback rating issue :") sr

Specialists Round!!!

https://imgur.com/a/ZzDKJuT

I cant relate tho I cant write 200 line solutions

As a tester, I became cyan.

I hope to become cyan in the cyanforces

just made it in time (i ran from the bus station), hopefully i won't turn cyan

excited!

All the best guys....

Speedforces!

Permutation forces

Loved it

Task F is really awesome!

As a participant I love Vietnamese Contest! (tks for free rating)

Permutationforces. I love it.

Any ideas for C?

I was also stuck at C , what was your approach?

Nothing special, was implementing whatever was coming to my mind

What did you guy stuck on C ? You can check for da editorial, but you can also give your question here and I will reply :v

stupid speedforces

Why are there so many permutation problems?

From expert to pupil. I don't understand why this is happening...

Happening to me too :(

A<F

I am almost sure that 99% people simply saw the testcases and returned n-1 :P for A

Anyone with > 0.5 braincells can see that n! = n * (n — 1)!

i didn't see it and failed to solve A. how did u realize this observation?

is this not correct??

yes that is, but no one derived it I meant.

i have 10 min i doesn't see that it ask for max i think it ask for min i tried binary search but when loking at sunmission rate i rewrite then just a second to solve k! + (k-1)! = (k+1)(k-1)! k-1 is best choice

haha.. happens bro

F>A

permutationForces.

Why would you do that??? So many problems on permutations! It's just ridiculously disrespectful for those who suck in this theme!

Now its time to chnage the color After very long time

Hate permutations, hate sortings, hate myself. Goodbye chance to become pupil :(

+1 hate permutation problems, therefore hate this contest...

I wonder how many people actually proved their solution for A.

it was kinda easy to prove .

take the (x-1)! common from (x ! + (x-1)!) which will end up giving this equation . (x-1)! * (x+1). take a x such that x+1 = k .

It was clear to me that if there is a solution it should be k-1 to obtain the maximum number of factors from the factorial. To prove that this answer always works, I did a simple proof.

for x = k — 1

x! + (x — 1)! = (x — 1)! * (x + 1) = (k — 2)! * khow to solve C anybody ?

You can check for da editorial, but you can give your question here ?

https://www.youtube.com/watch?v=xPRvXKv6uPU&t=4s check this.

Hi guys I have uploaded editorial solutions here — check.

have uploaded A,B,C for now and would upload D in a few mins :) let me know if you find these helpful :)

thanks brother . keep up the good work

Link doesn't work for me.

I don't know why link expires or such — does this work for you : https://www.youtube.com/watch?v=hpYCvj7zOrQ&lc=UgwiODTb_axafSBRenZ4AaABAg ?

This link works. Thank you.

nice

Permutation Round!!!

BTW, how to solve D?

Permutation with inversion number can only be in form $$$s := {1,2, ...x-1, x+1, x, x+2, ...n}$$$.

So the basic idea is to try each $$$x$$$, there are $$$n-1$$$ possibilities.

When changing your permutation from $$$p$$$ to $$$s$$$, it is equal to swapping $$$x, x+1$$$ in $$$p$$$ and sorting $$$p$$$. It is well known that the minimum swap required to solve $$$p$$$ is $$$len(p) - component(p)$$$ (p after $$$x, x+1$$$ swapping). So we need to find $$$x$$$ that maximizes the number of components after $$$x, x+1$$$ swapping.

Another conclusion is that if $$$a$$$ and $$$b$$$ are in the same component, then swap $$$a, b$$$ adds one component. Otherwise, if $$$a$$$ and $$$b$$$ are in different components, then swap $$$a, b$$$ decreases the number of components by $$$1$$$. So we need to check whether there exists an $$$x$$$ such that $$$x, x+1$$$ are in the same component~

Besides, how to solve B???

Best possible arrangement is for any N is 1 2 .... N , in sorted order.

You just need to find the longest best arrangement possible

For eg : N = 5 , A[] = [ 1 , 3 , 2 , 5 , 4 ] , the best possible arrangement that is already possible is taking [1 , 2] & not perform any operation on them as they are in longest sorted order & perform the operations on the remaining elements, taking the ceil of [Remaining elements / K] as the answer.

Thanks!

How to solve B, please??? A+C+D <= 40min. Unfortunately, I have no idea to solve B in the left time. I have to admit I am stupid.

Find 1 in the permutation. On the right of it, find 2. Continue this process until you can't find the larger number. ( n — numbers you've found )/k is the answer (round up).

Thank you!

check editorial here — click

Yes, scan $$$1,2,3...$$$ in LEFT->RIGHT direction. E.g. dynamic regex:

`/\b(??{ $s })\b(?{ $s ++ })(*F)/`

How to solve problem — B ?

Please help in problem D My idea was to find minimum moves to make the array equal to the sorted permutation in which exactly one pair of adjacent elements is interchanged This gave WA

try this example:

idea is the same just you have to make component s if the adjacent is not in the same component at all first we find all then all +1

very fast editorial

For Problem D , I tried with finding cycles for shifting/swapping. Then was trying something based on the cycle size. Something similar to min swaps needed to sort an array. but couldn't get it. Any ideas?

One observation I had was : to have exactly 1 inversion, we need i and i + 1 to be swapped , rest entire array needs to be sorted.

You were correct in your approach and observation.

Let x — min swaps required to sort the array. You just need to check if the cycle has a consecutive number then the answer is x-1.

Else answer is x+1.

yes thats the main observation after that you have to grp them (components) type then just find the ans

Let $$$x$$$ be the min swaps to sort the array, let if $$$i$$$ and $$$i + 1$$$ are in the same cycle, you need $$$x - 1$$$ swaps to get the array where the only inversion is $$$(i + 1, i)$$$, otherwise you need $$$x + 1$$$ swaps. (can't really prove it tho)

Problem A is very bad for the CP contests, it is better for math competitions.

It is bad because it doesn't check any skills and knowledge because it was worth to try just $$$k-1$$$ after looking at the sample tests.

First time ranked top100 in div2. Hope for no FST!

Any hints for D?

i think this is a hint: answer is min swaps to sort + 1 or min swaps to sort — 1

What I was able to analyze is that eventually our answer would look like 1.2.3.4...i+1.i....n So yes the answer should be the swaps to sort + 1 or -1 depending upon can we make the above state just before the last swap to sort. Now IDK whether this is correct or not but if we have some i which is at position(i-1) or (i+1){1 based positions} then we'd subtract 1 otherwise we'd add 1. Is the above correct? Please give reason as well

Incorrect.

2 in position 3. But answer is 4. Because 2 and 5 (in position 3) belongs to different cycles (1 3 5) and (2 4). So you cannot in two moves get 1 2 4 3 5.

If you'd get cycle likee 2 5 x x 1 (two consecutive numbers in one cycle) then you can in one move get 2 1 x x 5.

the positions are 1 based but u gave 0 based.

Ok, then that

You got cycle x 7 5 x 2 x 3 x, so you can in two moves do

x 7 5 x 2 x 3 x

x 3 5 x 2 x 7 x

x 3 2 x 5 x 7 x

So you need to substract one, but there is no such i in i-th or (i + 2)th position

Reason: all cycles can be treated indepenedent, so in cycle with len

`l`

need do`l - 1`

moves to sort cycle, and if in cycle exists two consecutive numbers then you need`l - 2`

moves to get one inversion in that cycle.Incorrect

no such

`i`

but we'd subtract 1we cannot guarantee that the

`i`

is the inversion by just looking at this, this is actually my proposed solution in the contest :/ which i got Wrong Ans2Reason: idk, have some counter case

Hint1You can order the array first. Do operations on sorted array.

Hint2The order of exchange can be changed at will.

Hint3The answer is always n-1 or n+1.

Yo, could u check my soln once? the one i wrote above

Hint 1: A permutation has one inversion if and only if the permutation is $$$(i,i+1)$$$ for some $$$i$$$.

Hint 2: The minimum number of transpositions from a permutation $$$\pi$$$ to change it to the identity is $$$n-c$$$ where $$$c$$$ is the number of cycles in the permutation.

hint 3: The distance between two permutations is the distance between the permutation given by the composition of first with inverse of second, and the identity permutation.

hint 4: count number of cycles $$$c_i$$$ in $$$p$$$ composed with $$$(i,i+1)$$$ for all i in O(n) time. The answer is $$$n- max(c_i)$$$

Just check out this. All Will be clearminimum-number-swaps-required-sort-array Secondly check if there is any x+1=y element in the cycle.

Is problem C a little difficult to write? I wrote it twice.

Besides, the problems of this competition is very interesting.

You know, it's permutationspecialistforces. :)

I dunno, my solution was straightforward and simple :think:, maybe you can hack me I guess

But as a setter, can you give detail for the issues you have to deal with during the contest ?

Linear Solution for Problem CWA on test 2 in problem C... can anybody help (188113413)?

Take a look at Ticket 16681 from

CF Stressfor a counter example.SolvedSolvedFucked Up ManSpoiler...

Is Um_nik stronger than 1000 cyans? Let's find out! Screencast with commentary

Problems A, B, C, D, and E were all very straightforward and meaningless to solve. With all respect to the authors, it was one of the worst contests that I participated in.

I wish I could say this in some rounds.

fuck this system bro i swear to god half of c submissions from youtube channels

I hope all of those skipped! If you can make a blog as you spotted those similar solutions. Go on, Do!

finally cyan in the cyanforces <3

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

Nice

permutation_forces

So happy today !!! Became Specialist for the first time !!

Thanks a lot for the contest

I m shocked to observe that I somehow solved C in O(N)

Became Cyan (finally) in the Cyan round!

I would like to point out that the first to address F in Div.2 should be drizzlo. derekFeng's rating is 2746, and I think it may have been New Year's magic that led to an oversight on the part of the blog writers.

Updated:

Already fixed at light speed! Thanks again to the author for preparing such a great round and for the attention to feedback!

Short Statements = Beautiful

Can anyone help me figuring out why I'm getting runtime error for problem C on test case 7.I'm trying from 3 hours still not able to figure it out.Your time will be worth a lot.Thanks in advance . Here's my code 188125909

Your code is such a mess. You can Google your exit code (-1073741819 )on test 7, it is something about memory access violation. My !guess! is x--; q[i]=*x; s.erase(x) Or x--; k.erase(x); p[i]=*x;

But I haven't tried to fully understand what your program is doing

One of my favorite rounds, all of the problems have short statements and very clean solutions. I hope you guys author more rounds in the future!

.

Boring contest.

I became cyan for the 7th time. Thanks for this contest, created by 7 'cyans'.

Why are the top 2 in division 2 new accounts?

me sitting happy with +0 delta.

Solved only 1 but since it was div2, solving even one of them as a low rated newbie should have increased my rating. A few months ago, people who had similar rating solved 0 in div2 and still their rating got increased. For a newbie whose rating falls in (0-1000),solving 1 div2 problem is leading to downfall in rating, if it would have been div4,then it makes sense but it's div2 and still.

MikeMirzayanov Hi, I received this message: Your solution 188082997 for the problem 1768C significantly coincides with solutions csegura/188082997, Sahil9259/188104072, UnRiVaLeD__/188104217, Frieza_Comeback/188106033, ashu1509goel/188107094, atharv_soni/188109171, BS_BISWA/188109314, POSEIDON_RAGNAROK/188119467, soumabha_12/188120764. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details.

I see that I was not skipped because I was the first one to submit the code; Good job in identifyng the copy. I don't use any online system, so it was leaked through the codeforces system. By the time that my code was leaked, it seems that the only person in my room that had closed the problem was coderpro2, so, if this is confirmed, in my opinion, actions against this account should also be taken.

Got WA, can somebody help me? I still can't figure out the testcase which my code fails on. (188511376)

Take a look at Ticket 16686 from

CF Stressfor a counter example.I'm having a serious trouble solving Problem F with Java 8.I believe my code is essentially the same as the description in tutorial, but all I got is TLE in case 24/25. Is there anyone ACed this problem with Java? Or can someone tell me why my code is so slow?

Here's my code:188557390 Sorry for the trouble

solved by fixing multiple mistakes. turns out I understand nothing of the solution :)

I have been informed of an alleged matching of answer in my mail received from codeforeces, if possible, I would like a review of same because the logic of linked are same. I tried it 2 times I would like to see that and see my past submission they will look the same. I would really appreciate if it is reviewed manually..

MikeMirzayanov Help me out, please.

Such a wonderful cyan text consisting of specialists' nicknames