Hellowo Codeforces o7
cry, larush, chromate00, Friedrich, Lilypad, and I are ebullient to welcome you to participate in Codeforces Round 998 (Div. 3) at 19.01.2025 17:35 (Московское время). We have cooked up $$$7$$$ problems to be solved in $$$2$$$ hours and $$$30$$$ minutes.
The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks. After open hacks all accepted solutions will be rejudged on successful hacks.
Note that the penalty for each wrong submission in this round is 10 minutes. Also, note the rule restricting AI use!!! If you are caught using AI in an unorthodox manner, you will be banished off the face of the earth (trust me).
Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:
- take part in at least five rated rounds (and solve at least one problem in each of them)
- do not have a rating of 1900 or higher at any moment in time.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you (unless you register unrated).
We would like to orz the following individuals for making the contest possible:
Vladosiya for coordinating our round.
Our army of testuwuers: [VIP] awesomeguy856, [VIP] Dominater069, omeganot, Error_Yuan, Intellegent, -firefly-, amoeba4, 18o3, efishel, Edeeva, yoru_sacri, Abhishek_Srivastava, Vladosiya, macaquedev, DivinePunishment, Filikec, reirugan, pianapolataa, ETL, and Rahuldeb5,
(MVP+++) MikeMirzayanov for developing the platform that will soon host Codeforces Round 1000.
As a tester, I cannot confirm the word ebullient comes from ef: a fairy tale of the two.
zz, i love u
wow zrnstnsr tested round again
bro,you smell so good
As a participant I cannot confirm my attendance for contest ;)
I want to attend it and make some problems!
And slove $$$5$$$ problems (in this contest) !
Already seeing one...
Learn to count please, codeforces has already hosted exactly 1950 rounds at the time this comment is written.
Maybe the author's meaning is there will be $$$1000$$$ Codeforces Round.
Should be clarified then
How many problems are geometry?
I don't think it's good to publish the kind of the problems.
0<=n<=69, where n = number of geometry problems
There are at least $$$\displaystyle{\int_{-2025}^{2025} \frac{x^{2025}}{x^{2024}+1} \mathrm{d}x}$$$ geometry problems.
Human Language : There are no geometry problems (trust me)
btw use
\displaystylenice
Human language: there are at least zero geometry problems
This is Proof by QED
for anyone wondering f(x) = -f(-x) so the integration is 0 because the limits are symmetric along the y axis too
As a tester, wishing you all positive delta! Alternatively, wishing you all positive (insert your favorite letter of the Greek alphabet, or any alphabet). Whatever floats your boat.
P.S. Would advise against getting banished off the face of the earth. Sounds unpleasant.
Wishing for positive sigma ☆〜（ゝ。∂）
We like positive sigma!
as a testuwuer, very sigma contest
hope that F is not hackable
We also hope so...
Fire in the holeee
WATER ON THE HILL
Wind from the Landscape
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣦⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣽⣻⣷⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⢾⣟⡷⣿⢿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⣟⣯⣿⣽⢯⣟⡿⣿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⡿⣟⣻⢿⣿⣟⡿⣧⣿⣿⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⣤⠀⠀⠀⠀⠀⠀⠀⢀⠀⠀⢀⣼⣿⣟⡿⡜⣭⢻⣾⡿⣽⡾⣽⢿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⣰⣿⡄⠀⠀⠀⠀⠀⢠⣿⣿⢿⡿⣟⣷⣿⣱⣛⣬⠳⡽⣿⣯⣟⣯⣿⣿⡆⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⢠⣾⣿⣿⠁⠀⠀⠀⠀⢠⣿⡿⣽⣯⢿⣻⣾⢧⢳⣜⡲⢏⡳⡽⣷⣿⡿⣷⣿⣿⡀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⡀⣿⣿⣽⠏⠀⠀⠀⠀⠀⣿⡿⣽⣷⣻⣟⣿⡱⣎⡗⢮⡵⣋⢷⣩⢿⣿⣿⣽⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⢿⣿⡿⠋⠀⠀⠀⠀⠀⣸⣿⣻⣽⡾⣷⡟⢶⣙⠶⣩⢗⡺⢭⡖⡳⣎⣿⡿⣿⣻⢾⡇⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠛⠉⢈⠀⠀⠀⠀⠀⠀⣿⡿⣽⣳⣿⡟⣼⢣⢏⡾⣱⢫⡵⢫⣜⡳⢵⣺⣿⢷⣻⣿⡇⠀⠀⠀⣀⠀⠀⠀ ⠀⠀⠀⢀⣾⠀⠀⠀⠀⠀⢰⣿⢿⡽⣷⡿⣜⡖⣫⠮⡵⣣⠯⣜⡳⣎⢽⣚⢼⣿⣻⣽⣾⣇⠀⠀⠀⣸⡄⠀⠀ ⠀⠀⣠⣿⣿⡇⠀⠀⠀⠀⢸⣿⢯⣿⣿⡱⢞⡼⣱⣋⢶⡭⢷⡹⣜⡎⣗⠮⣽⣿⢯⣷⢯⣿⢦⣀⣴⣿⣿⡄⠀ ⠀⢰⣿⣟⣾⣷⡀⠀⠀⠀⣸⣿⣻⣾⢧⣛⡭⡖⣧⡿⠋⠀⢸⡱⢮⡹⡼⣹⢾⣿⢯⣟⣯⣿⣻⣟⣯⣷⢿⣷⠀ ⠀⣿⣟⣾⢷⣻⢿⣶⣶⣾⡿⣯⣷⡿⣲⡍⣶⡽⠋⠀⠀⠀⢸⣱⢫⠵⣓⢧⣿⣿⣻⡽⣷⢯⣷⢿⣽⢾⣯⢿⡇ ⢸⣿⣻⡾⣟⣯⣿⣞⣷⢯⣿⣳⣿⡗⢧⣞⡽⠁⠀⠀⠀⠀⢸⢧⢏⡻⣜⣣⢻⡿⣷⠿⣿⢻⣿⣻⡾⣿⣽⣻⣿ ⣽⣿⣳⡿⣿⣛⣷⣿⡾⣿⣽⣿⢿⣞⡱⣾⠁⠀⠀⠀⠀⠀⢸⣏⠾⣱⢣⡝⡶⣹⢌⡳⢼⣣⣿⡿⣽⡷⣯⣷⣿ ⠸⣿⣳⡿⣿⡳⣜⢎⣟⡻⢯⣤⠟⣡⣿⡇⠀⠀⠀⠀⠀⠀⠀⣯⣏⡳⢽⡸⣵⢫⡷⣭⢳⡼⣿⡿⣽⣻⢷⣻⣾ ⠀⢿⡿⣽⣿⡷⣩⢞⣬⠳⣍⡳⢞⡽⣿⠁⠀⠀⠀⠀⡦⡀⠀⠻⣾⣽⠮⠛⢁⣾⡝⡖⣧⣿⣿⡽⣿⣽⣻⢿⠃ ⠀⠊⣿⣟⣾⣷⡹⢎⡶⣛⡼⣩⣟⢲⣿⡀⠀⠀⠀⣸⠀⢧⠀⠀⠀⠀⠀⢀⣾⣧⢻⡜⣾⢿⡷⣿⣷⡿⣽⠏⠀ ⠀⠀⠊⣿⣯⣿⣵⢫⣶⢹⡜⣷⠉⠛⠋⠁⠀⠀⢠⡇⠀⠈⡇⠀⠀⠀⠀⠘⠁⣿⠓⣾⢱⡞⣼⣿⣯⣿⠋⠀⠀ ⠀⠀⠀⠈⠻⣿⣷⡭⣲⢫⢵⣻⡀⠀⠀⠀⠀⠀⡾⠀⠀⠀⠹⣄⠀⠀⡀⠀⢸⣏⠷⣎⡳⣾⣿⣿⠞⠁⠀⠀⠀ ⠀⠀⠻⣤⣀⠈⣻⣷⣭⢳⡣⡟⣧⠀⠀⡎⠑⠚⠁⠀⠀⠀⠀⠈⠙⠉⢡⣶⡿⣜⢫⣖⣿⣿⠋⠁⣠⡀⠀⠀⠀ ⠀⠀⠀⠘⠻⣿⣿⢿⣿⣧⣳⡝⡽⣆⠀⢳⡀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣯⣿⠱⣎⣷⣿⡿⣿⢿⡿⠋⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠈⠛⢿⣾⣻⣿⣾⡳⣽⣧⡀⢳⡀⠀⠀⠀⠀⠀⠀⢠⣿⣟⣬⣿⣿⢿⣽⣻⠟⠉⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠛⠿⠿⣷⣽⣻⣦⠙⢤⡀⠀⠀⠀⣠⣿⣿⣾⣿⠿⠟⠋⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⠉⠛⠉⠁⠀⠈⠉⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
hope i will become specilist in this contest
div2s are better for becoming specialist imo if you solve 3 you gain heavy delta
Agreed.
Is expert possible without solving div2D?
If C's like 1600, then there might be a chance if you solve C under 1 hour, because then your rank will be around 1000. Otherwise I think we must solve D to reach expert.
D is a bit hard for now (for me)
Will it use modulo 998 244353?
it might
geometry dash div3 right after geometry dash div4???
As a tester army-man, uwu contest!
Hoping to reach Cyan back !! Wish me luck..
Congrat
Thanks.. Wishing you success !!
As a gd player, I can confirm this is good
I don't have chromate00's ship yet :(
GeometryDashforces
gd mentioned letsgooooooo
As a tester I can confirm the round exists.
As a round I can confirm that the tester exists.
Pupil this time?
I want to ask that a programmer with rating 1000 can solve how many problems? and also what is the penalty for 1 minute.
Typically 2 or 3 problems in div3s have difficulty <=1000. To be honest, though, I wouldn't advise you to try to predict how many problems you'll solve in a contest before it starts. (Thinking you've reached your limit and solved everything you could have solved might affect your performance, even if you still try to solve the next problem)
The penalty is the sum of minutes plus 10 for each wrong submission, so the penalty for each minute is 1.
As a gd player, contest based on Geometry Dash? :D
id 114184865
Can any omega-sweat tell me how hard this might be thank you <3 <3
i have no idea how to get past 3%
you have to double click the yellow orb
A fellow scissors ship enjoyer?? 😱😱😱😱
POV: codeforces when im trying to stop being addicted to gd
I think this intersects with MITIT.
This only intersects with round 1 of advanced. Beginner round is much later after this contest ends.
As a tester, ratio the blog by upvoting my comment
As an alien, I can confirm that this round will be from out of this world.
And You for participating! Why is this line missing from blog?
Again!! If I don't become specialist in this contest then I'll
try again in the next one
I reached that in last div2 :)
As a participant, it is going to be my first unrated div. 3 :)
I hope cry doesn't make rated participants :'(
To solve last problem I need to beet Tidal Wave?
"do not have a rating of 1900 or higher at any moment in time."
Did we change Div-3 limit to 1900 ? Proof_by_QED
UPDATE: Got confused between Trusted participants and Rated Participants
that is the limit for trusted participants. it means that anyone who had hit 1900 at least once will not be shown in trusted standings.
UPDATE: Got confused between Trusted participants and Rated Participants
Because this rule precisely exists to combat against higher rated people unduly dropping rating and "bullying" lower educational divisions in order to boast an "achievement"?
Please do read the line (already exists in announcement, copypasted for you):
I am sorry, I misread. I didn't differentiate between "Trusted participant" and "rated participants".
Thanks for clarifying.
has the difficulty increased due to ai use?
How do I register unrated? Doesn't seem to be possible.
Should be enabled now, thanks for pointing it out!
hope to expert (0^0).
Hopefully I can become an Expert through this contest.
Abhishek_Srivastava Orz
If i don't become cyan
Manchester United will win UCL this year
Best Div3 contest till now... so much to learn >>>
formula for problem F
agh, I knew there would be some formula I didn't know in order to compute this efficiently...
Can it be solved using the formula $$$1^k + 2^k + 3^k + .... n^k$$$ ?
where K = sum of power of prime divisors.
No. For x = 4 and n = 3, this formula outputs 14 but 10 is the right answer (this case is already included in the samples).
The one thousand rating question: What is wrong with my problem E?
Tried: sort, two pointers, binary search... nothing work... (*desperate*)
Or did I read the problem wrong?
Try DSU
nvm I did read the problem wrong, also I don't know what DSU is.
Very well outplayed, good time to learn something new.
nvm I got accepted with dfs only. If only I've read the problem correctly...
Is E DSU?
yes
No, I solved this problem without DSU, just a couple of DFS.
Not necessarily. At least I used dfs and dfs only. I found all the components in the second graph and deleted such edges from the first graph, that connect $$$(u, v)$$$ from different components. Then I just calculated the amount of components $$$A$$$ in the first graph and the amount of components $$$B$$$ in the second graph, adding their difference $$$A - B$$$ to the answer.
cute div 3...Thanks for the round.
Happy to be first solve on G
My competitive programiness is degrading exponentially faster contest by contest. Great problem-set though. Had fun.
best div3
I'm unsure if ChatGPT degenerated or problem setter intentionally rejecting problems solvable by ChatGPT on testing however, it solved literally 0 problem which is quite unusual. quality contest desu better than most div2 imo. well done
which version you were using?
o1-mini
Honestly, that's quite satisfying to hear :)
Although I was pretty slow, I liked the problems lol.
I was initially gonna use DSU with rollbacks for E, then realized I was being numb in the head.
could anyone solve E with frequency ? :)
what do you mean by frequency?
in problem E i took it for granted that F and G has 1 component each initially
well then the answer is $$$0$$$ in every case
no i mean F has 1 component and G has 1 component. I don't say F and G are connected
if a graph has one component then there exists a path between every possible pair of vertices
Yea but you may have some vertices missing in G which is in F or vice versa
I didn't understand the problem that way.
In both graphs there are exactly $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$.
Was F matrix exponentiation?
Nah, apparently there's a formula for summation of stars and bars over the range [0, n] containers.
was it a rated contest?
return true
[DELETED]
My code for F got accepted after contest :( 301899886
difficulty lvl (imo) — E>B>C>D>A
indeed, B was like a Div2 B.
I think for ICPC-style contests, it's reasonable to have problems shuffled randomly. I think it would be more fun that way, it's up to each contestant to identify which problem is easier.
(It's just that people are so used to Codeforces problemsets having increasing difficulty starting from A and so it's like an unspoken "rule" that it should be that way).
My solution for F.
Let $$$f(a,\ n)$$$ the number of ways to make an array with product $$$a$$$ and $$$n$$$ elements. We need to find $$$F(a,\ n) = f(a,\ 1) + f(a,\ 2) + ... + f(a,\ n)$$$ Using combinatorics arguments, $$$F(a,\ n)$$$ for the first element is some divisor $$$d$$$ of $$$a$$$, and the other elements can be choose in $$$F(a/d,\ n-1)$$$ ways. we need to consider the case when the array is {$$$a$$$}, so add 1 to the result $$$F(a,\ n) = 1 + \sum_{d|a} F(d,\ n-1)$$$
Using the definition for $$$F(a,\ n)$$$ for $$$2a$$$ and $$$n+1$$$, we have 2 equations
$$$F(2a,\ n+1) - 1 - \sum_{d|2a, d \ne a, d \ne 2a} F(d,\ n) - F(2a,\ n) = F(a,\ n)$$$
$$$F(2a,\ n+1) - F(2a,\ n) - f(2a, n+1) = 0$$$
Subtracting:
$$$F(a,\ n) = f(2a,\ n+1) -1 - \sum_{d|2a, d \ne a, d \ne 2a} F(d,\ n)$$$
Calculate $$$f(2a, n+1)$$$ is easy, we just need to find $$$2a = p_1^{a_1}\cdot p_2^{a_2} ...$$$ and multiply $$$\binom{n + a_1}{a_1} \cdot \binom{n+a_2}{a_2} ...$$$
And all divisors of $$$2a$$$ except $$$a$$$ and $$$2a$$$ are smaller than $$$a$$$, so we're done 301902082
Judging by number of submissions A=B=C=D. Rename Codeforces to Cheatforces
E >>>> B > D > C >> A
As a tester, I thought E was easier than D which was easier than C...
Most people dont know how to use DSU.
You didn't need DSU, a DFS / BFS solution works as well; with that being said, I don't personally think E was easier than D
bruh how is a DSU problem (E) easier than a frequency array problem (C)?
Because if you know what a DSU is it's immediately obvious how to solve the problem. With C I actually had to use my brain for a nonzero amount of time.
In my opinion, this isn't horribly off, B and C were similar difficulty (with B being a bit harder), and D was easier than most other div3 Ds (and even if you couldn't figure it out, the greedy solution wouldn't be too difficult to guess). Additionally, D has 10k less correct submissions than A, so I don't know where you are getting that from.
I get it from oficial standings https://prnt.sc/s0RPBkCwrqFq
My mistake, was looking at the solve count on the contest main page
I tried many hacking, and CF site says "Rate limit exceeded" ... (I saw this first time)
They recently changed the policy on viewing submissions. Now we don't have that unreasonable cool down time for each submission, and instead we get that "rate limit exceeded" after dozens of submission views in a short time, and it lasts for like an hour. It's still too harsh for people who want to hack a lot, but I guess it works for most people for now...
If you look at the first 2 submission of b you can see 2 identical submissions with comments in french that scream chatgpt, dont know where to say it so i put it here, i suppose there are more like this
I registered as rated, why it's marked as unrated now?
If you registered as rated why will it be marked unrated?
Why is the contest unrated? Wuwuwu(╥_╥)(╥_╥)
Wait for system testing
I am unrated at codeforces and wanted to get a rating so i participated in this contest, but it still shows me unrated, why?
it will get updated for div3/div4 rating update takes 1 day atleast
why my answers deleted and i dont get rating
Ratings aren't in for this contest yet, will probably be there in a couple hours
hey there , my account got banned for the using of AI, i didnt have a clue regarding the rule, ill follow it from now on, is there anyway i can get my account activated again??
the username was Moayad999