Hello, Codeforces!
I'm pleased to invite you to Codeforces Round 901 (Div. 1) and Codeforces Round 901 (Div. 2). It starts on Sep/30/2023 17:35 (Moscow time). It also means, the National Day of China arrives during the round. Wish you a nice vacation! 🎉🎉🎉
For both divisions, you will have 3 hours to solve 7 problems.
I would like to thank:
errorgorn for his wonderful coordination.
Alexdat2000 for Russian translation and Vladosiya for helping us with Russian clarifications.
Gellyfish for providing all the problems and "a few" rejected problems.
PersistentLife and SanweiTreap for helping me prepare the problems.
Um_nik, wangziji, Sugar_fan, Kevin114514 and MagicalFlower for Legendary Grandmaster Testing.
sjcsjcsjc, He_Ren, GaryZOOD, platelet, njwrz, thenymphsofdelphi, DerekFeng, Juanzhang and ttklwxx for International Grandmaster Testing.
maomao90, juju527, zimpha, 625248, xuanquang1999, CrTsIr and EasonTAO for Grandmaster Testing.
SATSKY_2025target_LGM, lanhf, Hank2019 and Yakumo_Ran for Master Testing.
DaniraSilla and benjamin_kleyn for Candidate Master Testing.
raulandreipop, micho, alwyn, ArgintLaAnu, IssamOtoz and jakao for Expert Testing.
CLown1331 for Pupil Testing.
You for participating the round.
MikeMirzayanov for Codeforces and Polygon systems.
Especially, I would like to thank errorgorn for his great contribution to the round, njwrz for providing user solutions for all the problems, Kevin114514 for making the announcement and tutorial more readable.
Finally and most importantly, I would like to thank PersistentLife for helping me with everything patiently all the time. This round can't happen without him.
The main character of the problems will be Jellyfish, a sweet little girl. 🍏🍏🍏
Score distribution:
Div.1: $$$500$$$ − $$$1250$$$ − $$$1500$$$ − $$$2250$$$ − $$$3000$$$ − $$$4000$$$ − $$$5000$$$
Div.2: $$$500$$$ − $$$1000$$$ − $$$1000$$$ − $$$1250$$$ − $$$2000$$$ − $$$2250$$$ − $$$3000$$$
Good Luck & Have Fun! 🔥🔥🔥
UPD1: Editorial is out.
UPD2: Congratulations to the winners!
orz
Hi
hello
fun fact about Div $$$1$$$. $$$5000 + 4000 \gt 500 + 1250 + 1500 + 2250 + 3000$$$
*rainboy has entered the chat *
sadly he's div 2 :(
StO
stO
what stO means?
kneel down
As a tester, I enjoyed the round and found some very nice problems! I recommend you to participate.
sto MagicalFlower
As a tester, I have no clue how come we have seven problems for each division now.
And (based on the score distribution) only 4 problems in common between the divisions? That would make it 10 problems in total, which is insane for a 1-man-round.
And yes, so Gellyfish orz.
Gellyfish orz
Gellyfish Kevin114514 orz
Kevin114514 orz
Do Gr-app Dream of Electric Jellyfish?
Do Gr-app Dream of Electric Jellyfish?
Do Gr-app Dream of Electric Jellyfish?
Wow, the round have many tester including thenymphsofdelphi — one of the Vietnamese strongest coder. So the round must be good.
thenymphsofdelphi orz.
orz njwrz for providing user solutions for all the problems!
As a tester, I really love some of the problems in this round!
thankyou codeforces for giving java 21 support , it was launched just a week ago and is now available to submit on codeforces
As a tester,I really enjoyed the problems in this round. And div.1 G is a difficult and interesting problem, hope someone can solve it in the contest!
As a tester, I can say that the problems are very educational and I really enjoyed them! Hope you have fun practicing and good luck to all!
OMG 5000 D1G, so heavy round...
Hope to reach expert on this round. Good luck to everybody participating!
Unfortunately conflicts with ICPC North America Qualifier :(
Looks like it should be fine, NAQ only starts 25 min after the round ends :)
Exciting, it'll be hard to wait 3 days, hope to get at least +5. GL & HF
Honored to be a tester!QwQ
As a tester, I recommend the Round to upgrade your rating ^_^
As a participant, I predict that this contest will be perfect!
As a tester，I found many good problems in this round. Wish you good luck~ sto Gellyfish
As a tester, I had fun with the problems and I hope you do too!
.
This means that there are two different problems with the same score :)
.
Hope my rating can be risen!
Look at the score distribution, so weird...
omg 2 festivals round
omg 2 festivals round
omg 2 festivals round
omg 2 festivals round
Woah, a 3-hour round. I, personally, will not be able to focus for that long :sob:
Will try my best to reach the specialist.
Only one author for all problems? .... Oh, he is Gellyfish, it's okay.
Hopefully I will make optimal use of the 3 hours, but not go to problem C or D and feel hopeless
Clashing with LeetCode Biweekly Contest :(. PLease try to schedule these at some different times in future.
wdym, I think Leetcode should reschedule theirs, not the other way
LC contests are always at the same time. I will give LC contest because they arent mathforces af
But Codeforces contests are almost always held at the same time as well. I don't see any logic in your statement. Maybe you should get your priorities straight with a grain of reasoning.
I can predict when will there be a LC contest 1 year from now.
Can you do the same for CF contest? Can you tell me whether there would be a CF contest at 5th Jan 2024.
Try to get my point instead of just arguing for the sake of argument.
No, but at least I know most of them will be held at the same hour of day. I know rescheduling is a hard decision. But how does the schedule being predictable account for deciding that one contest should reschedule in favor for another? Tell me. You're saying you have a point. Tell me where your point lies.
I too prefer contests where I dont need to think and just regurgitate my data structures and algorithms knowledge.
What is LeetCode?
-- deleted because my memory sucks--
wdym, MHC R1 is literally next week
hello.
21h35 -> 00h35 in VN x_x
Yeaah！festival round! hope i can increase my rating! Orz
rated?
yup
hopefully atleast +6 this time
Oof, wish you all the best for CM
If you think that person who did pupil testing is a pupil, then you are a CLown1331
This round is very special! It has 7 problems and 3h to solve problems.
I just broke up because I declined my girlfriend's invitation to go out tonight so I could participate in Codeforces contest :D
Some fun fact: Gellyfish participated in ABC on his girlfriend's birthday 2333333 (Jellyfish: ? so love will disappear)
Are "Jellyfish" and Gellyfish's girlfriend the same person?
Can't wait to solve 4 problems in Div2 for the first time. I hope i reach specialist today. Good luck everyone.
This may be my first time to take part in div1. Hope I can be a master. QAQ
Happy the National Day of China!!!
Grandmaster when?
purslane so strong
Happy Chinese National Day:D
My first Div1.
Good luck
I'm so excited about this one,Im going to fight for C today really hard.
scary score distribution. 1250 to 2000 jump
LOL CLown1331 is actually a real clown
hope to get positive delta :)
I'm using Chrone on Mac. The digits in equations are in sans-serif font, which makes it really annoying to see some of the eqautions. Does anybody experienced this before or have an idea how to resolve it? It seems it only happens in CodeForces, and with other browsers like Safari this does not happen.
Try m1.codeforces.com (usually refresh will work when I see this (but I don't use chrome :( idk if it will also work on chrome
I want to try, but there's no way to take a look at a problem statement until the contest start...
sad :( maybe you can try to save the page before mathjax works. read the words between $s may help(?
Why are two starting letters Black in MagicalFlower handle? :O
tourist vs Benq Round
Sadly neither of them gets the first place :)
I don't have any fun in it
This is the first contest during which I went to its announcement ._.
I'll never ever take part in Chinese contests again. Ծ_Ծ
Very high wrong submissions in this round.
I think that I willn't participate in Chinese rounds after this.
It's a really good opportunity to learn something well known in china, ain't it
this comment is deleted
It is better to ask when the contest is finished
Thank you for giving me an unhappy holiday :(
How many math questions do you need?
Problem Setter: Yes
P.S: (just my opinion) Didn't enjoy much, where I could think of using algorithms for mid-rated problems rather than checking my mathematical ability :(
The DP question Div2 D was good btw
Casting an ancient Roman curse on the round author
That was indeed a llong round.
Who in their right mind would think Div2B is 1000 rated, and is the same difficulty as Div2C? Have the authors actually lost touch with lower rated contestants? There has to be more pupil and specialist testing for future contests.
How do you solve div1C? I could probably have done it if output format was modulo a prime instead of double but now I don't know
mathforces
Where is testers for specialists??:))
In problem Div1C/Div2F, in test case 2, how is the answer 0.625?
Except node 5, every other node has possibility 1 for successful mission.
If at node 1, and Asuka select v2 = 5, v1 can be 2,3,4. One of these 3 roads will get destroyed and with remaining roads we can always reach 7.
Jellyfish will not know Asuka's choice before making her choice.
I also got stuck in the same place as you, but I asked for clarification and this was the response.
I think Jellyfish picks before Asuka, so she cannot mirror her choice.
ohhh, got confused becoz of this statement
Jellyfish knows that Asuka will choose a road randomly. Now, Jellyfish wants to know, if she chooses the roads optimally, what is the maximum probability of the mission being successful.How to solve D1B?
How to do D2F? I know it is tree dp, but how to calculate the probability at each vertex?
orzdevinwang :)
Can someone who solved all problems in Div.2, explain the problems?
If I don't get FST, It will be my best performance ever.
How to solve C.
Refreshing when actual problems, for my level, start from B :) .
Thanks for the contest!
I cannot clutch B I am going to kms
What's the casework solution of D1A?
i dont think i've been this afraid of systests in years
The server was down for the last few minutes (403 Forbidden) :(
What is the intended solution for B? I did something fishy and got AC but with 1980 ms (so high chance I fail systest) I ran normal BFS and realise around 2000 states in total which should be fast enough, if not because of a map, so I did some preprocessing to reduce a b c d and m into 8 bit numbers (since bit combinations of at a particular position of (a,b,m) will give the same result of (c,d) after some operations), then I use a global array to store distances to pass.
Also if not because of the editorial of this: https://mirror.codeforces.com/contest/1866/problem/M I wont have solved D
As expected, I failed systest... (rip IGM dreams)
I do the exact same thing and it ran in ~900ms without anything special. I'd guess this is the intended solution, not sure why yours performs worse.
Could anybody give me a data to Hack my WA solution qwq. I kept getting WA for two hours!! https://mirror.codeforces.com/contest/1875/submission/226062939
I did the same and got a lot of TLE.
Than i started to memorize the solutions for the possible (a,b,c,d,m) tuples among the test cases -> pretests passsed with 670 ms xd
So there are several identical testcases in a test
I did the same thing, though I sorted the testcases in such a way, that I only run a single BFS for the same 8bit number. And then un-sorted testcases into initial order. It passed in 170ms.
I also used a vector instead of a map to keep the distances.
Awesome problem!
Is there any hopes of this contest getting unrated?
2 Hours spending on Problem E but kept getting WA!!!
I'm fool!!!
I actually think Div.1 E is too standard. It equals to asking the number of Cartesian tree with $$$n$$$ nodes and the sum of subtree size $$$\geq lim$$$. I suspect that there is an original problem for that.
Also, I think Div.1 B is too hard for its place. Observing the standings, I think it's better to swap B and C.
Div.1 A = Div.2 B but Div.1 B = Div.2 E What's this?
Fr it threw me off so much. After struggling with B and C for so much time, I open the div 2 standings to see my friends, and all of them have solved 2D, that too fast!!!
Worst contest ever. Need to practice more and more..
How to calculate the probability for transition from $$$u \rightarrow v$$$ in Div1C?
Could not submit D becuase the code length limit exceeded. When I finally minimized the code it was two minutes after the content had ended. That's my fault but. Please. Increase. Code. Length. Limit.
Although they drove me mad...
but 1B and 1C are very VERY interesting problem with fantastic trick! (for me)
Could you explain the idea of 1C?
my english is poor. so u can look at my code f[i][j] = there's i roads and you successfully chose the j-th
what a bad contest
i think u need to practice more lol
no problem i will do it more and more until i achieve my goal
what type of problem is d1b :sob:
Let's discuss the solutions.
How to solve D?
I compressed the array into pair of <value, freq> ex 0 0 2 3 5 becomes (0, 2) (2, 1) (3, 1) (5, 1) then used 1d dp.
Though there are 7 tasks, so heavy to treat D1ABC...
I guess we can have two Div1 rounds from this problemset.
div2 A,B were cool C got on my nerves it's the kind of math i don't like.
Is there any legitimate solution for D1D besides "idk ternary search should work to optimize this dp" (I dont like waiting for editorial so that is why I ask)
Write the math and you realise the answer is sum(Si/mi) * 2 — n. Si is the sum of m0.. mi Then a simple DP follows
Sir what simple dp, simplest dp requirrs m^2*n (fix mi, fix Si for each i). How do you do better than this
$$$s_i+m_i*(n-i) \leqslant m$$$
😳 😳 😳 😭 😭 😭 how could i be so blind 😭
I made a claim that mi is increasing. Then the number of transitions become mnlogm
funniest thing is I knew that but didnt think to do the $$$* (n - i) $$$ part 😭
idk divide and conquer DP should be able to optimize this.
As a participant, I didn't have fun with the problems
Div1 A to Div1 B C was such a huge difficulty jump :/
Div 1's A was Div 2's B.
Don't know why this was done, but that might contribute to the difficulty spike since it's like if a Div 2 contest went from a B to a E.
Don't know about Div2 E, but I wasn't able to solve Div2 B, rather I solved D and C. .So, for me B preceding E, rather than C or D is very correct. :_)
Questions were tricky rather than difficult.
Div1 D seems very similar to a problem from SEERC22: https://mirror.codeforces.com/gym/104114/problem/M.EDIT: the same "local improvement" approach doesn't work in the new problem, nvm
Expert, here i come
Can someone tell me how to solve "B" that is B. Jellyfish and Game?
I can't prove it, but if they play 4 times the moves will start to repeat, so I simulated 5 and if the number was even I simulated one more.
225979586
RIP
well! atleast not wa on pretest 69!
chill man
at least not FST
chill man
at least not hacked :3
It seems that problem D in div 2 can be done in $$$O(n \log n)$$$ with slope optimization or Lichao segment tree.
Where does D1C probability dp formula come from?
I have solved 4 problems for the first time in div 2 !(yeee)
congrat bro
Thanks a bunch <3
"Note that the sum of n over all test cases is not bounded." what does this mean in Div2 A problem?
In many tasks you will see statement like "sum of n over all test cases <= 200000" but here there is no guarantee (max n could be max n per test case * max test case)
Todays Contest was Awesome Thank You Gellyfish and everyone who made this round possible .
I dedicate my success in today's round to my two senpais: alinp and BarbutaRobert! Btw I hope TimDee didn't cheat today!
how the equation m×|S|−n come out in the problem Div2C? Can anyone explain this? There is no any additional comments about this in Editorial.
Let us assume that $$$\frac{m}{\text{gcd}(n, m)}$$$ is a power of $$$2$$$ . So we can say that $$$\frac{n}{m}$$$ can be finitely represented as some binary representation like $$$\sum_{i \in S} \frac{1}{2^i}$$$.Each individual people is going to get $$$\frac{n}{m}$$$ weight of apples and he will get this weight in denominations of $$$\frac{1}{2^i}$$$ . For each $$$i$$$ in $$$\sum_{i \in S} \frac{1}{2^i}$$$ we need to have exactly $$$m$$$ pieces . For an apple of weight $$$1$$$ we can get $$$2^x$$$ pieces each weighting $$$\frac{1}{2^x}$$$ and this will cost $$$2^x - 1$$$ cuts. For each $$$i$$$ in $$$\sum_{i \in S} \frac{1}{2^i}$$$ we need to have exactly $$$m$$$ pieces each weighting $$$\frac{1}{2^i}$$$ and it can be done using $$$\frac{m}{2^i}$$$ number of apples having initial weight of $$$1$$$ and for each apples it will cost $$$2^i - 1$$$ cuts . For each $$$i$$$ in $$$\sum_{i \in S} \frac{1}{2^i}$$$ we would need exactly $$$\frac{m}{2^i}(2^i - 1)$$$ cuts . Total number of cuts will be $$$\sum_{i \in S} \left(\frac{m}{2^i}(2^i - 1)\right)$$$ . We know that $$$\frac{n}{m} = \sum_{i \in S} \frac{1}{2^i}$$$, then $$$n = m \sum_{i \in S} \frac{1}{2^i}$$$.So, the expression $$$\sum_{i \in S} \left(\frac{m}{2^i}(2^i - 1)\right) = \sum_{i \in S} \left(m - \frac{m}{2^i}\right) = \sum_{i \in S} m - \sum_{i \in S} \frac{m}{2^i} = m|S| - n$$$.
Speedforces :o
Here is a Video Editorial for Div2 B/Div1 A
And Div2 A too
Странный раунд, но в принципе задачи нетипичные для дивов, было даже интересно решать)
In Div1C, How do we calculate the probability transition formula for the cases where the out degree is even. For odd it will be just $$$1/n$$$
You can see how to in the first few lines of my main function here: 226217779
Thanks to tourist, we found out that the tests in Div1D were not maximally strong.
In my dynamic programming I search for the best value only in the heuristically selected range
[previousBest - 5, previousBest + 11]. This got me OK verdict. However, there is a test, where my solution is not optimal enough!Input:
My output:
Actual answer, when heuristic is turned off:
Just wanted the researched data to be public. It appears that searching
[previousBest - 12, previousBest + 1]is almost always enough, with just a few exceptions:The listed exceptions are "(n, m — n): shift_from_previousBest"
I just tried to hack my AC solution using the test you provided here and it worked.
So I could have FSTed :O
Chinese rounds are great you have to admit, the only thing we need is getting more foreign coders to test
or like finding coders of various cp styles to test
The test in Div2 E is too weak. See this: https://mirror.codeforces.com/contest/1875/submission/226052852
Again a devastating Round!!!.. for me
I think you need to practice more
Never felt more devastated! Completed 4 ques in 1:10, hoping for a very good increase. But TLE in D system test 18. Changed just a map to unordered map and it passed :( I didn't even need an ordered map, didn't know it would have such high penalty :(
write a wrong solution to 1C and hacked by znstz2018 a good contest but not that good for a retired
bruh, div1a is div2b and div1b is div2e :skull:
Is it just me or was this div2 a lot easier than usual?
i used ideone and i didn't know about the public thing and you can clearly see that he is the one copying from me because this is the code template i use and you can find it in most of my submissions
c question was pure gold in div 1.