Hi Codeforces!
Igorfardoc, Vladithur, Alexdat2000, GlowCheese, 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, GlowCheese, DeMen100ns for helping us in some different phases of preparing the problem set.
- All-time mighty
redcyan testers: gyh20, Chenyu_Qiu, xiaoziya, feecIe6418, Little09, ShmilyTY, thenymphsofdelphi, neko_nyaaaaaaaaaaaaaaaaa, 6aren, tfg, Andreasyan, generic_placeholder_name, Mangooste, BucketPotato. - Other testers: darkkcyan, maomao90, tibinyte2006 (absolutely
faketrue color), Gheal, bugdone, cadmiumky, 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: QBaraki, LeCaToX, dinhsangBKA, Hungconmk, antontrygubO_o, 74TrAkToR, ShuiLaoshi, 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 | missravenlocks | 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. >_<
Anyway, give me contribution.
You are a green with the power of a grandmaster, and that is something to look up to.
i want contribution too :)
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.
++ratingI 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.
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!
As a tester,this is my first time.Also,i want tell you something important
neko_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!
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
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).
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
...
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!
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
cyanforces
You copy my comment
Help -is-this-fft- finish off 2000 problems.
The most cyan round ever. It will be interesting!
so~so~so~so~so~green~ ovo!
Why is everyone cyan now?
It's fun and nice
Time for VietnamForces!!
Specialist Forces
Today I feel Vietnamese.
Cool fact that div made by Russians and Vietnamese while im Vietnamese but born in Russia... Great job guys!
Nice editing for last point.
Div2 finally, its my time to shine!!
Hope to get Master again!
I love you!
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
DeMen100ns, what the ..?
it's just rollback rating issue :") sr
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)!
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)! * k
how 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.
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)/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
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
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
lneed dol - 1moves to sort cycle, and if in cycle exists two consecutive numbers then you needl - 2moves to get one inversion in that cycle.Incorrect
no such
ibut we'd subtract 1we cannot guarantee that the
iis 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
You can order the array first. Do operations on sorted array.
The order of exchange can be changed at will.
The 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 ?
WA on test 2 in problem C... can anybody help (188113413)?
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!
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!
.
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.
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)
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 :)