Xin chào, Codeforces! (Hello, Codeforces!) ٩ (◕‿◕｡) ۶
Me, FireGhost and SPyofgame are glad to invite you to Codeforces Round 779 (Div. 2), which will take place on Mar/27/2022 17:35 (Moscow time). The round will be rated for participants with rating lower than 2100. You will have 2 hours to solve 6 problems, one of which is divided into two subtasks.
In this contest, you will meet Kitagawa Marin and her friends Gojou, Juju and Shinju from My Dress-up Darling! We hope you will find our problems interesting. Good luck to you all! (ﾉ ◕ ヮ ◕) ﾉ *: ･ ﾟ ✧
We sincerely thank the following people for their contributions in the round:
errorgorn for
rejecting 20 problems from SPyofgamecoordinating the round and KAN who guided him in his first coordination.SPyofgame and myself for setting problems and FireGhost, mewnian, _LEOS_, Mondeus for helping us prepare problems.
antontrygubO_o for providing the idea for one of the problems.
Kuroni for being
the problemsetter team's caretakerthe English proofreader.FireGhost, mewnian, _LEOS_ and SuckTinHock for setting tasks which failed to make the final problemset.
Monarchuwu for breathing and SPyofgame for being the team's punching sandbag.
antontrygubO_o, Kuroni, thenymphsofdelphi, darkkcyan, rama_pang, Yurushia, ngpin04, hieplpvip, Pichu, maomao90, FallingStar, Mike4235, Lyde, BaoJiaoPisu, HynDuf, NguyenDangQuan, thanhchauns2, vodacbaoan, hieudxm, novaland, DMCS, Dirii, welleyth, QBaraki, Minhho2005, Kriz_Wu, sweet_hope25, kieusontungcva, CrazyDave53, tien_noob, damnson, lk2147, 2qb, OnionEgg for testing the round and providing useful feedback.
unreal.eugene, geranazavr555 and MikeMirzayanov for Russian translations.
MikeMirzayanov for great Codeforces and Polygon platforms.
Score distribution: $$$500-1000-1750-(1250+750)-2500-3000$$$
UPD: Editorial
Congrats to the winners:
As a tester, f--k you SPyofgame.
f--k you SPyofgame
f--k you SPyofgame
f--k you SPyofgame
f--k you SPyofgame
f--k you SPyofgame
f--k you SPyofgame
f--k you SPyofgame
f--k you SPyofgame
f--k you SPyofgame
f--k you SPyofgame
F--k you SPyofgame
f--k you SPyofgame
f--k you SPyofgame
f--k you SPyofgame
im not a tester, but f--k you SPyofgame
f--k you SPyofgame
Shame on all of you
as Sheldon said
Poor Guy! What did he do???
f--k you SPyofgame
f--k you SPyofgame
f--k you SPyofgame
f--k me SPyofgame
f__k yOu
f--k you SPyofgame
f--k you SPyofgame
f--k you SPyofgame
f--k you SPyofgame
f--k you SPyofgame
f--k you SPyofgame
f--k you SPyofgame
poor for SPyofgame, but still f--k you
What is going on? Poor SPyofgame
I set a problem that its hardness keeps jumping around d2A, d2B, d2C, d2D, d2E, and d2F.
It is once being rejected when making more tests but then brought back by replacing other setter's problem.
poor for SPyofgame
f--k you SPyofgame
Why is everyone fanking our guy
This thread got me really curious. My guess is SPyofgame set a very annoying implementation problem. Am I right ? :)
dunno, I set problem F, which used to be all d2A, d2B, d2C, d2D, d2E, d2F.
Its difficulty belike :clown:
f--k you SPyofgame
Round is good.
Source: trust me dude I'm the authors' caretaker.
I'm only here because our beloved coordinator told me to
As a tester, I recommend participating in this round.
Nice elephant!
Elephant in Vietnamese is spelled "voi", which coincidentally is an abbreviation for "(V)ietnam (O)lympiad in (I)nformatics". The results are gonna be published in just a couple more hours, so you'll see some of the Vietnamese participants mention about elephant or have an elephant avatar for this reason.
as a person who suffers from their goddang Marin cult (and because I'm jalsol), please give me contribution
bloody hell they are coming at me lmao
i can confirm this
Monarchuwu orz
does Monarchuwu live in Antarctica??
oh yes, that's why he is breathing :))
As the person whose tasks were rejected by DeMen100ns, I strongly recommend participating in this round.
As a tester, please give me contribution. Try not to cringe as long as you can.
orz tien_noob
why are there always contests on usaco weekend :(
I want to be pupil. I wish I will reach the pupil as soon as possible. Good luck to everyone. I wish everyone will do well in this contest. And I wish all newbies will pupil.
same to you
As the results of Vietnam Olympiad in Informatics (VOI) are coming very near, I wish all of the problemsetters who participated in VOI a wonderful prize.
Edit: The same goes for all the other Vietnamese participants.
even though I failed to achieve anything at the olympiad, thank you very much
No I believe jalsol will have a good result, because jalsol orz
PS:
hydroshiba orzzzzz
no u orz sir, seal is just a noob
Veryyyyyyyyyyyy near...
... number of newbie tester > (number of specialist,pupil tester)
hope that Marin won't cause me another trauma like VOI
goofy ass announcement made me skip round
Anime propaganda moment
Who cares you participate or not?
My sincere appreciation for Marin Kitagawa <3
As a contestant f--k you SPyofgame
My rate-up darling!
We need an Emilia themed round in the future
Good luck and have fun.
I thought it was gojou from Jujutsu Kaisen :)
I start every contest hoping it will be better than my last. I hope I don't brick :)
Looking forward to this round, especially after I read, that there will be My dress up darling characters! Great anime, I recommend watching it! Good luck on contest!
Picture in the blog:
How are you going to make me choose between going to the gym and participating in this round.
https://mirror.codeforces.com/problemset/problem/698/A
Where's the gif from?
Here you are: link
Thank you so much!
sus
why is everyone harsh on SPyofgame
eh, I don't feel harsh tho, don't worry. Actually, I feel funny since most of them are my friends.
Jokes on you. He's into that.
RIP SPyofgame
rest in peace
I am fine, dont worry
DeMen100ns is so handsome
Soon, codeforces will be launching CodeTinder for you.
love you SPyofgame
love you too, but do yah love problem F too ?
Kitagawa Marin already hyped for this round. Good luck guys.
Monarchuwu orz
wuvforces.....
Judging by all the tester's reactions I think SPyofgame's problem statement had manga spoilers lmao.
Ahaha, I pray not to be so, otherwise, I will f--k him too
Fact: My problem F used to be d2A, d2B, d2C, d2D, d2E and now d2F
Anime collab ? My delta definitely will be positive.
Marin is best anime girl of 2022, even, Gigguk said this ! Thanks to authors
Marin is the top, and the others are photoshop.
Uwwuwuwuwuu
Want to view all blogs on Codeforces? Check this out
https://mirror.codeforces.com/blog/entry/101288
It is going to be the cutest contest that have ever been on CF
Hello, I'm new here. What are the cutout ratings for the different divisions?
So yeah you're eligible
I hope that I can be master
And I do it, thanks a lot
good luck
saying "good luck" after the result comes up... Interesting
How could I know whether he will get good luck before the contest? He knows my meaning well because we come from the same nation and the same province.
permutationforces!
Is the name of problem D haiten code ??
hentaiforce
how to solve problem C ?
check that there exists exactly one 1 check that v[(i+1)%n]-v[i]<=1 holds for all 0<=i<=n-1 check that v[(index_of_one+i)%n]<=(i+1) holds for all 0<=i<=n-1
Feeling so angry i implemented above all condtions but forgot to check count of 1 should be 1.. damn!
Yeah I feel you. I implemented all of these conditions but the one in the middle and had to come back an hour later to figure it out. So many unnecessary points wasted.
D2 should have worthed more.
Sad to see lots of people solved D2 ranked below people who don't.
maybe D1(750) + D2(1250) will be much better.
How to solve D2?
You can check if x is good with trie, $$$min(a_i \oplus x) = l$$$ and $$$max(a_i \oplus x)=r$$$. D2 solution: since $$$min(a_i \oplus x)=l$$$ you can just check $$$a_i \oplus l$$$ as candidates.
Let's fix some index i. Now we assume that before performing operation (^ x) this element had value of l. Okay, this means that after permorming operation its value is l ^ x. So, if we do (A[i] ^ l) we get a possible value of x. How to check that value x is good? It's easy to see that after performing operation all our values will be distinct. So, minimum value of (A[i] ^ x) over all i should be l and maximum value of (A[i] ^ x) ovel all i should be r. How to check this? Using trie. Sorry for my bad English.
Wonderful, I just fall into my D1 idea and try to optimize it, because I can not find out this idea.
lbm364dl have provided a bit by bit solution below, which I think is an optimization of D1 idea.
how to solve C?I struggle with it for more than an hour:((((
errorgorn should have rejected more problems
I expected you are not aiming my problem :<
Hints for D1 (Easy): Precompute the number of ones at every bit position for first $$$N$$$ natural numbers.
Then, for each bit position, compare the expected number of ones and zeroes. If $$$x$$$ had 1 at that bit position, the count of ones and zeroes would have been swapped. If it had 0 at that position, it would've stayed same. However, it $$$cnt[zero] == cnt[ones]$$$, there's no way of finding out if any swap did occur. Hence, this bit position is, in some sense, free.
Finally, $$$x$$$ has to be present in the array, since $$$0 \oplus x = x$$$. Iterate over the array elements to return any element which does not violate the non-free bit positions.
discovered the solution few minutes before the contest's end, guess that's what i deserve for arriving late to the contest.
Using the idea of free bits, you can also solve D2. Just iterate over all subsets of the free bits and try to use them in the xor answer. If every number of the array remains between l and r, then you have an answer. You can check my submission.
This is really cool.
Well, somehow I just realized this should TLE. The subset thing is $$$O((r-l+1) \cdot 2^{free})$$$ where $$$free$$$ is the number of free bits, and it should be around $$$10^{10}$$$ operations. I stop the iteration when it finds an element out of range, so I guess this happens many times. There may be some obscure math that can prove that I always stop a lot of iterations or just weak tests.
Actually I tried to hack your solution, but failed. And then I realized that it is just theoretical but really hard to find a real case.
Are there proofs that any element in array which does not violate the non-free bit positions will be the answer ? It's clear that one of them will be the answer, but why any ?
Suppose you found a valid $$$x$$$ with $$$i$$$-th bit free and does not violate the non-free bit positions. Suppose $$$x$$$ is $$$0$$$ in the initial array ($$$x = 0 \oplus x$$$). The $$$i$$$-th bit being free means that it has the same number of ones and zeroes on that bit. This happens when you initially had a prefix of a multiple of $$$2^{i+1}$$$ numbers, so in particular, $$$2^i$$$ must be in the initial array (you had at least numbers between $$$0$$$ and $$$k \cdot 2^{i+1}-1$$$). If you have $$$2^i$$$ in the initial array, then applying the operation gives you $$$2^i \oplus x$$$ which must be in the final array. This number only swaps the $$$i$$$-th bit of $$$x$$$, which was free, so it still does not violate the non-free bit positions. Therefore, $$$2^i \oplus x$$$ is also valid.
Thanks very much. That was a great answer. I finally understood all only just now.
condition: "If you have 2^i in the initial array, then applying the operation gives you 2^i⊕x which must be in the final array." result: "Therefore, 2^i⊕x is also valid." I can't understand the reasoning, why we can get the result from the condition, could you please explain it more detailedly?
I reread my comment and you are right, there's something off with that. It was kind of a circular reasoning. Let's try again.
We know that if $$$x$$$ is a valid answer, then it must not violate the non-free bit positions. We still don't know anything about the free bits, we know there is at least one solution, nothing else. This is a necessary condition.
We want to check the sufficient condition, that is, any $$$x$$$ that does not violate the non-free bit positions is actually a valid answer.
To show this, we first notice that $$$set(a \oplus 2^i) = set(a)$$$ for any free bit $$$i$$$, where $$$a$$$ is the initial array. That is, the set of numbers will be the same (still $$$[0, r]$$$) if we XOR every number with $$$2^i$$$, where $$$i$$$ is a free bit. Why? Because, as mentioned in the previous comment, if $$$i$$$ is a free bit, then the size of $$$a$$$ is a multiple of $$$2^{i+1}$$$, which means that for each number with a $$$0$$$ in bit $$$i$$$, the equivalent number with a $$$1$$$ (everything else the same) is also in the array. This proves the equality since XORing by $$$2^i$$$ just swaps pairs of numbers like $$$p0q$$$ and $$$p1q$$$, and they are all in the array.
Now, suppose $$$x$$$ is a valid answer. Then denote $$$a \oplus x$$$ as the final array. From the previous result we then have $$$set(a \oplus (x \oplus 2^i)) = set(a \oplus 2^i) \oplus x = set(a) \oplus x = set(a \oplus x)$$$, which means that $$$a \oplus (x \oplus 2^i)$$$ generates the same final array and is therefore also a valid answer.
From this you can set or unset free bits as you like, and in particular, you can unset all of them and you have the claim in the editorial.
Awesome! Now I got it, thanks a lot.
So difficult div2
This contest is a rubbish
151135032 I submitted a random solution on D1 and it passed pretest. Does pretests weak ? UPD : FST :))
I was confident in solving C until I looked at todays third! : (
What does 388535 mean, the title of problems D1 and D2 ?
haiten
sauce
This contest is sponsored by permutations
...
How does it happen that I notice a difference between the statement and input format for the second time this month? Perhaps I could help you test these things in advance?
Can I say that I am in love with Marin Kitagawa? Thanks for your time.
The idea of considering parity and considering bits individually while solving bitwise problems really helps.
https://mirror.codeforces.com/contest/1634/problem/B
The above idea used in this problem helped me in today's D1 :)
i remembered that problem too, but didnt solve d1 :(
can someone explain me why my code in d1 give runtime error on pretest2 ( look at the submission before the last one )
You need to replace
for(int i=0;i<n;i++) {at line 34 forfor(int i=0;i<40;i++) {and you won't have runtime error. This was happened because size of arrays vars and need is 40 and if n>= 40 you are requesting a non-existent element of this arrays.Beside this I know, why your code gets TLE (Time limit exceeded). If it's interesting to know the reason, it is under the spoiler
You must delete this line
if(n==0){ cout << "0" << endl; return;}If you doing this thing you don't input the only one element from the array a for this testcase and for another testcase your programme inputs its as variable dum so all numeration from the input values breaks.firstly thx so much on advice(it got ac :D) , but I just want to know why it give TLE when I broke the input values rather than wa , since I was inputting wrong values from a point
Probably this happens because in some test case after breaking numerations your programme inputs some big value as n and wants to input then n values but this test doesn't have so many values. So your programme waits for them endlessly.
oh now I get it , ok thx so much :)
Whoever decided the name for D problem is a true man of culture. Respect.
What does it mean?
Got my answer
Obviously?
Just whining since I went from +150 to +22 :(
Sucks to solve more problems but still have a performance difference of +350 with someone solving less :/
I Accepted the problem C without understanding the justification for the solution at all...
I feel like D is a little bit too standard?
Solve numbers of D2 says it's not so standard.
How to solve D1?
It is provided that we can always convert [0...r] to array by xor for all test cases. So for each bit, we count its occurance in [0...r] as well as in array. If the count is changed we add current bit to xor value, otherwise we can skip it.
How to solve problem C ? (with proof of correctness please)
you can shift input,to make first number in input 1(if there is not 1 answer NO),it means that N is first,then every next number can be at most one bigger than last(cuz after every shift by one in right it can increase not more than one .,u should check about there exist only one 1
how do we know that we can always contruct the array if these conditions are true?
when in the given array c[i]=1, it means at that moment n will be the first element inside the permutation because c[i]=1 means the first element is greatest ,after c[i]=1 we r confirm that the lowest value of c[i] should be 2 because no other element greater than n will come in the beginning and the greatest value of c[i] should be 1 greater than the previous one because it is not possible to increase the value by more than 1 just by adding one number in the starting of the permutation . so we r having lowest and highest values , we have to just check either these are following properly from i+1 to n and then from 0 to i-1. just assume your permuation is having nth element in the starting and after that what can be the range of next c[i]..
There is exactly one cyclic shift that gives $$$1$$$ (when $$$n$$$ is the first element). We can start from this position (let it be $$$pos$$$) and iterate in the right direction (cyclically) until we process $$$(pos-1+n)$$$ $$$mod$$$ $$$n$$$.
Each iteration denotes the movement of all permutation values one position to the right (the last element comes first). Let the current power be $$$p$$$, the new $$$1^{st}$$$ element should either be $$$ \lt $$$ the new $$$2^{nd}$$$ element (increasing $$$p$$$ by $$$1$$$), or $$$ \gt $$$ the new $$$2^{nd}$$$, $$$3^{rd}$$$, ..., $$$i^{th}$$$ and $$$ \lt $$$ the new $$$(i+1)^{th}$$$ element ($$$i \lt $$$ the new position of $$$n$$$), which will give a new power $$$np$$$ in the range $$$2\le np\le p$$$.
We can always construct a permutation satisfying the previous flow. Proof: Assume we represent each $$$ \gt $$$ or $$$ \lt $$$ constraint in the previous flow by an edge going from the larger to the smaller value. The resulting graph is acyclic and we can assign permutation values to its nodes by traversing in topological order.
How to solve E?
Compute the answer for cells in decreasing order of $$$v_{i,j}$$$, starting from $$$n^2$$$ (the maximum $$$v_{i,j}$$$), for which the answer is $$$'M'$$$. Let's call each cell marked by $$$'M'$$$ so far, a winning cell. For every other cell, if there exists a winning cell having distance $$$ \gt k$$$, Gojou can jump to that cell after the first move, guaranteeing him a win. If not, Marin wins (and we mark this cell as 'winning'). Checking this condition can be done by maintaining segment trees for diagonals.
Thanks, I didn't know what data structure to use, I will try that idea.
Interesting difference gaps. Not very easy Problem A, not very hard Problem F. But nice contest, thank you, problem setters.
However, I poorly misread "the cuteness of concatenated string" as "the sum of cuteness of all selected strings" in Problem F and got stuck into it until encountered those unbelievably brief solutions... I could have done better TwT...
Can I get your feedback for problem F ?
I mean "How hard is this adhoc ?"
If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.
If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.
Eh, dont you have problem F :<
HeHe, was too lazy to write the checker. Moreover, people who attempt the last problem are able to debug it by themselves, so I skipped it.
Do you want me to add it? (However, my generator won't be as good as yours, since you're the author).
Eh, if you really want to add it then I can provide you with my validator, checker, generators, and tests.
For the ones confused by name of problem D. Here is the meaing.
True Men of Culture. The author's Rental Girlfriend "parody" series is pretty great as well. It has 4 stupendous chapters so far.
396419 this one is better. Or this one 396084. So much ntr stuff, nice!
Codeforces Round 779: problems A-D1 explained
When you try to cheat and google the name of problem D, then everything goes wrong -_-.
I expected someone will gonna try to google that tho
I somehow managed to wait till the end of the contest XD.
I was just wondering — in the announcement it says that the round would be rated for users under 2100. However, it says that the round was unrated for me. I looked around at other participants and it was also unrated for them.
Just a bit unsure of if its just a processing thing or if the round wasn't rated for anyone.
It is rated. What makes you think it's not?
The contest has finished and it is at final standings — so ratings should have been added right?
If you look at your profile on progress and look at only rated this is not the last contest — for you it is the TON contest.
If you then switch from only rated to all, you can see this contest as the last one greyed out and it says unrated.
It usually takes a few hours until the rating changes are applied.
Thanks, that makes sense now.
Most of the other contests that I've done released the rating changes when the final standings were released I think.
I guess they just need to process the data or smth.
The problems are all about the "permutation"
how difficult!
f--k you SPyofgame
I just received a message from the system telling me that my solution(151118707) for the B problem is similar to notnotTehlka/151113394. I had reviewed the code of both the people; the fast io template of python is matching. Moreover, the solution was simple and trivial. So, Please look into the matter.
Dude, it's obviously the same solution as the notnotTehlka's one...
But it is a straightforward question it's the obvious answer is what I wrote.
One of the most terrible rounds I have seen.
Eh, why tho :< Can I have your feedback for better improvements in the later rounds ?
It is the first time we set a round on codeforces so there might be some advantages we can further improve, some disadvantages that we need to learn to fix.
I don't mind learning from feedback but I think you should go into detail about what made you annoyed.
Actually I didn't take part in this round. I just felt it hard to understand the statements when I reviewed it. Maybe it's because of my poor English.
If you cannot represent a problem with a clear concept DO NOT TRY TO DO SUCH NONSENSE!!
FACT Problem A
Never want to see you again in any contest @SPyofgame
.... you!
ehh, I am not the tester of this problem but you can still give feedback to me tho. I will try to improve myself along with these experiences too.
Could someone help me understand why this code is getting TLE? 151271702
The posts that say dirty words are placed on the top, while the posts that speak regularly are hidden.
My reaction to this contest blog on the front page:
Thanks for reminding me of the contest where I resubmitted to a question not knowing it skips the old submission and as a result lost tons of ranks due to it