Hi Codeforces! Happy Dragon Boat Festival!
We are glad to invite you to our first Codeforces Round Codeforces Round 796 (Div. 1) and Codeforces Round 796 (Div. 2) which will be held on 03.06.2022 17:35 (Московское время). This round will be rated for participants of both divisions. Participants in each division will be offered 6 problems and 2 hours to solve them. The two divisions will share 3 problems.
In this round, as the best friend of the characters in Touhou Project, you are going to help them solve the problems they meet.
The problems are prepared by xiaoziyao, Yakumo_Ran, SSerxhs, Cocoly1990, LilyWhite, Elegia and me. We hope you will enjoy this round.
Great thanks to:
- 74TrAkToR for good coordination of this round and translating all statements to Russian,
- Yakumo_Ran for providing most tasks,
- SSerxhs for preparing most tasks,
- LilyWhite for polishing statements,
- Elegia, QAQAutoMaton, jqdai0815, Kevin114514, Suika_predator, loveye, Serval, ix35, Miko35, mrsrz, SanweiTreap, Eden_CY,wind_whisper,xuezhe, Cocoly1990, KaguyaH, meowcneil, plagues, marzipan, nhc, SCL_, zarubin for testing our round,
- KagamineRin, huhaoo, juju054, JohnVictor and Zcusss for other help,
- MikeMirzayanov for the amazing Codeforces and Polygon platforms.
- NEAR for supporting this round, details can be found in this post.
Please pay attention that there will be no more than 998244353 interactive problems in this round, so learn more about interactive problems here before the contest.
Good luck & Have fun!
UPD 1:
Score Distribution:
Div2: $$$500 - 750 - 1250 - 1500 - 2000 - 3000$$$
Div1: $$$500 - 750 - 1500 - 1500 - 2000 - 3000$$$
UPD 2:
Editorial is out.
UPD 3:
Winners
Div.1:
Div.2:
official:
unofficial:
You mean no more than 998244352 interactive problems
998244352 not a prime number, 1e9+7 is the best
998244352 is not but 998244353 is
actually 998244853 is the best
ancient history
What's your current hobby?
My current hobby is to talk to my wife through linkedin
$$$1004535809$$$ is the best.
1000696969 is the best prime number.
1000696969 is good but 269696969 is just better :)
Actually 1145141 and 19260817 are also the best.
As a tester and writer,I think it's such an interesting round(and I want contribution).Good Luck & Have fun!
Chinese round,great!
Also the tester list is quite impressing as I know most of the people on it.
now->know?
Fixed
When I see Elegia in the setters, I know D1F won't be solvable.
As a writer, I want to know how Elegia's mind works,too :)
You'll see
How EI's mind works?！
Chinese round, good round!
As a writer, I want to know how Elegia's mind works. If you don't know too, please give me contribution :)
As a Statement Writer, I want to know how Yakumo_Ran's mind works. If you don't know either, please give me contribution.
nice one lol
As a partcipant, I want to know how all the writers' minds work. If you don't know either, please give me contribution.
Problems are really interesting, hope you all have fun!
As I'm a tester, I want my contribution back above 0
-44 now:)
-49 now:)
-56 now. When can I reach -56?
just a link to its Chinese edition
世有伯乐，然后有千里马。千里马常有，而伯乐不常有。故虽有名马，祗辱于奴隶人之手，骈死于槽枥之间，不以千里称也。马之千里者，一食或尽粟一石。食马者不知其能千里而食也。是马也，虽有千里之能，食不饱，力不足，才美不外见，且欲与常马等不可得，安求其能千里也？ 策之不以其道，食之不能尽其材，鸣之而不能通其意，执策而临之，曰：“天下无马！”呜呼！其真无马邪？其真不知马也！
北海若曰：“井鼃不可以语于海者，拘于虚也；夏虫不可以语于冰者，笃于时也；曲士不可以语于道者，束于教也。今尔出于崖涘，观于大海，乃知尔丑，尔将可与语大理矣。天下之水，莫大于海。万川归之，不知何时止而不盈；尾闾泄之，不知何时已而不虚；春秋不变，水旱不知。此其过江河之流，不可为量数。而吾未尝以此自多者，自以比形于天地，而受气于阴阳，吾在天地之间，犹小石小木之在大山也。方存乎见少，又奚以自多！计四海之在天地之间也，不似礨空之在大泽乎？计中国之在海内，不似稊米之在大仓乎？号物之数谓之万，人处一焉；人卒九州，谷食之所生，舟车之所通，人处一焉。此其比万物也，不似豪末之在于马体乎？五帝之所连，三王之所争，仁人之所忧，任士之所劳，尽此矣！伯夷辞之以为名，仲尼语之以为博。此其自多也，不似尔向之自多于水乎？”
Cant disagree
luogu round!
Chinese Edition
So many famous Chinese OIers, looking forward to this!
Usually div.2 ABC will be easy to solve but now since so many high-skilled users from luogu participated in making problems I'll be thankful to solve A
if you agree give me contribution, or give me contribution
Don't worry, you'll make it.
I agree.
Touhou round, good round!
Touhou win again
Glad to see a Chinese round and a Touhou round, sounds interesting.
Hope I can get an assert(Rating_change>0).
Beware of Luogu's problem group invading codeforces
As a Chinese round,why not set the time earlier?
Ran thinks it's ok xD
Because not only Chinese will participate in the Chinese round.
But it doesn't mean that the author can ignore people like us who cannot get up late,especially in China.
Don't you think there are too many contests at this point in time?
Is it needed to learn interactive problem for first 3 problem in div. 2 contest ?
I like your confidence.
oh yes chinese round finally
Touhou round, Great! xD
AnimeForces Round
why codeforces don't support emojis?
By the way, Beware of Luogu's problem group invading codeforces. (just for remind again)
https://codeforces.net/blog/entry/103348?#comment-917966
Use HTML code of emojis
As a Touhou fan who has
never played Touhou before. Although, I did play once. I hope to get back at it someday :DI am looking forward to the round!
Animeforces round with almost all problemsetters having anime profile pictures. Is it me or the Chinese are more likely to have anime pfps than the Japanese (somewhat ironic, since animes come from Japan)?
Japanese animes are popular in China
Please pay attention that there will be no more than 998244353 interactive problems in this round..., but there will be a problem with mod = $$$998244353$$$, right?Please pay attention that there will be no more than 998244353 interactive problems in this round, so learn more about interactive problems here before the contest.Actually, I am going to learn more about combinatorics/counting problems after seeing that number.
What is rated range for div2 ?
<1900
Will Div1 A be Div2 D this time as both divisions share 3 problems this time?
A supercalifragilisticexpialidocoius Chinese Round!
But as a Chinese OIer, I still cannot participant this round as the time is still too late for me.
Unfortunately, the word should be "supercalifragilisticexpiadocious".
As an OIer in China, my parents will never let me take part in a 22:35 contest. So sad.
Chinese round, good round!
Can't wait to see PinkieRabbit get -154 rating.(
Can't wait to see PinkRabbit get -154 rating！（
I got -147. Thank you bro.
You'd better say thanks to Yakumo_Ran and your horse waifu.
big celebration:)
big celebration:)
big celebration:)
(nearly laughed out my lung)
Hope to turn blue today :)
Well Well!! This wish came true
your hope turned true today
Accomplished
question c makes me wanna leave the contest rn
I am unable to even understand the problem
Some stooopid anime boy made this question, thinking he was being "cool".
wtf does question C mean?????????
First, read the sample test cases and then read the problem. It's not hard to understand the problem.
i am a high expert on main, and i can't even understand Div2C. question is written very poorly. also, i don't see you getting AC on question C, so how about you solve it first before telling me to understand the problem?
most of the people have understood the problem. it's just hard to capture the idea to solve it.
you have starting string of one character a-z, you need to find that character which can be used for transformation process where you should apply next operation N times: take pair of string (x, y) from 2*N strings where x — substring of current string, y — string you should put instead of x in current string only once. ending string must be equal to final one given in description
storyforces
History repeats itself
I was able to solve only A lol (Div. 2, ofc)
Or maybe not....
Bruh Cdiv2's question is so confusing XD.
This contest sucks.
I agree
Yeah, I think div2.c is too hard (maybe have a strange idea too) and its statement is not good. Sorry for your bad experience. I hope I won't create such bad problem again.
Apology accepted, now please make the contest unrated :)
Good suggestion, but nope :)
sorry to say but this round really f***** my brain. did not like the problems even a bit. should've gone out with my friends instead.
Completely agree.
Guessforces and adhocforces.
Div2DE were nice problems.
in this contest we are all equal
Solved C with 0 confidence about the proof.
How does A sample passes on CodeBlocks, but do not pass on ANY compiler on cf? I have wasted approximately an hour to fix that :( 159364881 I think today is just not my day...
Your toDec function might access elements outside the string giving garbage values at times.
Thanks! Will be more cautious next time...
how to solve div 1C?
Notice that an operation on prefix sums is: if $$$s[l-1] = s[r]$$$, set interval to $$$s[l-1]$$$ We can ignore non-zero $$$s$$$ values and simulate copying intervals in any order with a queue.
You can use a set or union-find to find non-zeroes.
Zero idea about div2C and zero idea why my Div2D works(solved by guessing at brute force values)
Not an enjoyable contest.
Edit: My bad I should have read that the initial length of the string s in C can is 1. Stupid me.
Frequency count all characters. Only one that is odd is answer.
div2C is you either guess solution or you don't
turns out the letter that occurs odd number of times (over all t's) is the solution.
In that case , I wonder how so many AC's . For me Difficulty was , A < B < E < D < C .
I could not understand the problem statement of E :(
Yeah , that was one of the hardest things in E . I understood problem statement using Sample Testcase.
Basically , you are given N nodes and M edges , each edge has a weight assigned to it . In each query you pass a string of length M , where for i'th index 0 represents the current edge is not present , whereas 1 represent current edge is present . Now each query returns you the sum of weight of the edges present in maximum spanning forest for the string you passed.
But why??
For any transformation (t1 -> t2), the character count increases by 1 for both LHS and RHS.
Let's forget about the LHS of the first transformation first.
For any character that is not present in the final string, it must have occurred at least an even number of times (first time on the RHS, second time on the LHS), since it's parity is 0 in the end.
If it is present in the end, its parity is one, so add these characters to reset their parity to 0 (i.e. add the transformation "final_string" -> "").
Finally, the only one that is present on LHS but not on the RHS is the original string (i.e. the only character with parity one).
chinese lied us. they can't solve hard problems, they just guess the solutions.
Pardon?
To me div2C looks like what I personally call "Wishful thinking" or what I think I saw, perhaps more generally, in a blog made by Mike Mirzayanov as "Bold hypothesis". You just really wish that you could ignore X. In this problem, the structure of the strings seems like the problematic part. So you just "hope" that you can ignore the structure (or the order of the characters) of the strings. Once I realised that, I reduced it to the counts and tried thinking mathematically of it. A bit of experience reminded me that if I have a bunch of ones that I either subtract or add in order to get zero, the number of ones has to be even...
Agree on Mike Mirzayanov part, true life
I think div2C was too pure lol.
parity
how to solve div1 B ?
first check if there is an odd number in the array, if there is then answer will be number of even numbers, because you can just add even number and an odd number and get odd number as a result, if there is no odd number then you have to create one, to created one you can should choose an even number that needs least divisions to become odd , once you get odd number then you can do the thing I mentioned above.
First find the weights of all edges in m queries.
Then, just use a similar idea as Kruskal's algorithm. Adding the ith edge with weight $$$w_i$$$ creates a cycle if and only if the value returned from the query after adding the ith edge < weight of the current spanning forest + $$$w_i$$$.
sorry I replied for wrong problem
How to solve Div2 C?
Let $$$count(c, s)$$$ be the count of a letter $$$c$$$ in $$$s$$$.
If $$$t$$$ is given in the correct order, then for each $$$c$$$ that's not the initial letter,
$$$\sum_{i = 1}^n (count(c, t_{2i}) - count(c, t_{2i - 1})) = count(c, s)$$$.
Rearranging, we get
$$$\sum_{i = 1}^{2n} count(c, t_i) - 2\sum_{i = 1}^n count(c, t_{2i - 1}) = count(c, s)$$$.
This implies that the parity doesn't change for all letters except for the one you have started out with.
For each lower case character, e.g. 'a', the total number of 'a' in all the input must be even except the initial character. You can transverse [a-z] to find the one only occur an odd number of times.
I think it was a very nice competition!! Thanks a lot!
Problem div1C was wonderful, congratulations to the authors.
Oh! Div1C is so hard that I try my best to do,but I failed. :(
Agreed. I enjoy the problem too.
How did you solve it?
weak pretests for div2A
Why x <= 2^30 instead of x < 2^30? :(
Wish I thought of 1546B - AquaMoon и украденная строка for today's div2C with enough time left during the contest, but alas, bricked B and kept burning time bouncing back to it...
Why was final string given in div 2c when it is was of no use??
It's not of no use, is there anything wrong with your sol?
c problem has very bad description see codeforces please see this
need to improve queue. clearity
I'm sorry the description of div2.C is not so good, we will try our best to write better descriptions next time.
Div2E's statement is still unclear, at least can you please update the statements now so that they can be understood easily by the ones who are/will be practicing?
Could you please tell me what is described unclearly? I'll try to fix them.
The value of a railway system is defined as the total length of its all tracks. The maximum (or minimum) capacity of a railway system is defined as the maximum (or minimum) value among all of the currently functional system's full spanning forest.
In brief, full spanning forest of a graph is a spanning forest with the same connectivity as the given graph.
This whole statement is at least not clear for those (like me) who don't know full spanning forest (or spanning forest) and the link provided in the problem statement has two definitions, first one is somewhat understandable but still, I could not understand it fully.
I thought we have to tell which edges to activate. Then it will give us the maximum value among the connected components formed from the activated edges. But this assumption fails for the 2nd query of the sample test case given :(
The best thing which can be done is to explain the answers to the sample test case or add examples of which kind of graph you are talking about and what we have to maximize or minimize.
Thanks!
I agree with the "Unclear statement". It took me quite some time to figure out what the author meant by it.
The maximum (or minimum) capacity of a railway system is defined as the maximum (or minimum) value among all of the currently functional system's full spanning forest
Can anybody tell the testcase for which my submission is failing ? https://codeforces.net/contest/1688/submission/159358654 Div2A
1 536870912
I even can not understand the Div.2 F
Only reason i figured out that A was by looking at Note for second test case :p.
Div1C is very hard for me, but quite interesting. I will upsolve later T.T
Happy Dragon Boat Festival to you all!
Pretests for D are very weak .
Agreed, an obvious mistake in my programme wasn't shown by pretests, and my detla went from +150 to +7 :(
Different participants got fst on different tests (as you can see in status). It's difficult to make strong pretests with limited number of tests.
Very fast editorial. Thank you!
I hated d2c until I solved it
WHATTTTT!!! Div2E was just kruskal? how couldn't i see it
Can anyone hack my submission on Div.1 D?
https://codeforces.net/contest/1687/submission/159399180
First,find $$$O(n+a_n)$$$ numbers that may be the answer; Random_shuffle the permutation,then one by one check if they are available in a query. When one number isn't available,then push it to the front of the permutation when dealing the rest queries — that makes most of the hacks of making only one number unavailable unsuccessful.
Can anyone find some hacks?
Thanks to the problem setter for not killing my code. ;)
Hack mine as well 159406136
Why the number of possible numbers is $$$O(n+a_n)$$$?
There are two scenerios.
1) all numbers are in the same range. In this case the answer should be $$$k^2-a_1$$$ , so there will be at most $$$O(\sqrt{maxans})$$$ numbers.
2) not all numbers are in the same range. In this case there must excist $$$i$$$ and $$$k$$$ such that $$$a_i\le k(k+1)$$$ and $$$(k+1)^2\le a_{i+1}$$$, so $$$k\le a_i-a_{i-1}$$$, which means that there will be $$$O(\sum a_i-a_{i-1})=O(a_n)$$$ possible numbers in this case.
Thus the total is roughly $$$O(a_n)$$$
I actually loved the problemset.
A can be messy if you solve it wrongly, but doesn't have to. B is rather easy interactive one. C is definitely from AtCoder Problem Generator (analyze given process and try to look for properties which might be useful), but seems more enjoyable than most of such problems, and as it's only one problem, that's perfectly fine and there are no problems with that. In D you can allow yourself for some randomization, if you feel that you do it right, which is always nice. In E you can do something without worrying too much about constants and just check with submission if it's correct. F I guess requires some knowledge (some fun with generating function stuff I guess?), and that's find for last problem.
Everything works good. The only problem is a lack of implementation-dependent-data-structure-like problems, but they doesn't have to appear every time and anyway it's a great way to go!
I really enjoyed Div1 A~D(I was working on E but failed). I felt every problem challenging when I was working on it, but found it brilliant after solving it. I'd say just focusing on the problems, this round is the best Div1 round recently. Thanks to the authors!
Div2E is easier than the observation needed to solve Div2C
I mean I take some time at the beginning of the contest to think in Div2C and then skip it and solved Div2D then I return to div2C. I couldn't realize that I need to skip it again and solve Div2E lol
I agree. Div2C is a great idea
piece of shit round
My first contest with >2500 performance!!
D1D statement:
"[Let] g(x) be the maximal square number not strictly less than x"
I think this kind of statement is unclear, especially given the range of English ability on this site. In particular, one I can see this being read is
$$$! (g(x) < x)$$$
However, this contradicts the example that $$$g(8) = 4$$$. Especially since you need to be able to read inequalities to understand the bounds on the problem statements, I think problems like this would be much clearer if stated using unambiguous mathematics. Something like "Let $$$g(x)$$$ be the largest positive integer where $$$g(x) \leq x$$$ and there is some integer $$$k$$$ such that $$$k^2 = g(x)$$$." What do you think?
Also, loved the contest. I will come back stronger.
Sorry for the unclear statement, we'll try our best to do better next time. Thanks for your support!
Thank you for a great contest!
Agree. I think it is also fine to just use "at most" here.
I read it exactly the way you said it could be misinterpreted lmao. I agree, it would be nice if it was stated symbolically, it removes possible confusion.
Was it only me or the statement for Div1B was really confusing ¯_(ツ)_/¯
Yeah it is a little bit confusing
Your face is confusing too
It's really hard to understand.
Two last rounds, like in good old times:
If that's interesting, I find it pretty funny that I wouldn't call any of these fails "a bug".
I believe this is "a curse"
Unlucky! :(
If you would have submitted your solution to E in C++20, it would have passed
My skipped submission also was correct and was passing.
Question C is not correctly explained that things ruined the whole contest
Hello, in div2 C for test case: 1 2 z abcz ab abab
should not the answer be z? most submissions print c as an asnwer.
Is there any glitch in rating change? Many of my friend's rating didn't change till now. But my rating is changed.
mine rating has been changed but still showing pupil,xd !
me too, 1940-rated expert xD
hi me
Why didn't rating change for anyone under 8000th?
It seems only my solution didn't pass pretests :( div2D?
I changed int to long long for n and k and it worked
worst pretests that I can saw
No spoiler hint for Div2D?
It seems that this contest is too Codeforces(in Chinese mind),which means solution(or the key idea) first.It will be much better if there would be more normal problems.
Hey, I know a place where you can compete without requiring any ideas. Here you go.
Hi MikeMirzayanov my rating is above 1400 but i haven't been promoted to specialist please check it.
I'm went below 1400 after this contest and it still shows that i'm specialist
I couldn't even do task A. I'm suck.
Don't lose heart. Keep in touch and you'll be able to solve it easily
Who can tell me why my friend passed the question in the contest but didn't get A rating change (not 0)? Another friend of mine checked question A 7 times but didn't get A rating change either. Who can tell me the scoring rules? thank you
I have noticed an interesting fact: the round was unrated for plenty of div2 participants. Does anyone know what's up?
I think it's a bug, as another user pointed out people below a certain rank haven't been rated yet
Hi MikeMirzayanov, i became candidate master but the account's color still Blue And i see that no one change their color Please check it
MikeMirzayanov when will the bug be fixed of colour change?
There are some people in Div2 who didn't get their delta. Is it a bug?
Can somebody tell me the testcase at which my submission 159494268 for div2F fails?
Take a look at the 8-th test case in Ticket 10505 from CF Stress. The expected output is "NO", but your code prints "YES".
Has anyone else noticed that Div2C (the troll parity problem) and Div2E (the Kruskal's problem) are both rated 1700, but Div2C got 1687 solves while Div2E got only 261 solves? I suspect that Div2E's low rating is caused by the overwhelming majority of Div1 getting it. In that case, wouldn't Div2C still have a lower rating than Div2E?
Can somebody explain how Div2E is done? I looked into a couple of solutions. I understood until the part they found the length of each track and sorted the tracks. After doing so, they iterated on tracks (shortest track first) and at each iteration, greedily checked whether the track belongs to the same forest as the shortest track. They always returned the 'value' of the forest with shortest track. This looks clearly wrong because a forest containing shortest track need not have a the least 'value'. I am definitely missing something. Any help will be appreciated.
They are returning maximum value and not minimum. And if we iterate the sorted edges then you will find that if we add any edge at a particular instance, then if value is not equal to previous edges cost + current edge==> clearly implies that this has replaced a smaller edge for same connected forest.(hence we discard these edges). NOTE: jury is returning maximum value.
I am a newbie and I had secured a score of 726 but my ratings haven't been updated yet. Even that contest is not showing on my profile. Both of my codes were accepted and are still there on my submission page. Can anybody help?
The Ranking change is still 8501 and there is no news now.
My ratings are still not updated does anyone knows why this is happening? And whom should I contact regarding this.
Your rating is updated but with no change
But I solved 3 question what about them.
OKK So this means that for my 2700 rank the net change in my rating was 0.
My rating hasn't changed yet. What to do about it?
It must have changed by now as I can see that everyone's rating and division is now correctly put up by codeforces.
ужасно переведены тохо сказки к условиям(((( ещё и пачули сделали предметом, а юкари стала мужиком... :despair: и прикольные эпиграфы убрали(((((
Why you don't like the problem C in div2? It is not difficult at all!
stO hzr Orz