Hello Codeforces, and the legends of across $$$999$$$ and more rounds!
wuhudsm, Yugandhar_Master, and I are beyond excited to invite you to Codeforces Round 1000 (Div. 2) at Jan/22/2025 15:05 (Moscow time). Please note the unusual time of the round ($$$\color{red}{2.5}$$$ hours before the usual time)!
The contest contains $$$6$$$ carefully crafted tasks, one of them divided into two subtasks, to be solved in $$$2$$$ hours. You will solve tasks themed around Little John and his shenanigans aimed towards getting his own dream home (featuring, probably, galvanized square steel).
This round could not exist without the thankful help of these so many people:
- FairyWinx for
rejecting more tasks than are used in the final problemset,coordinating the round and translating the problems; - rewhile for some very important "technical assistance";
- the testers of Codeforces Round 960 (Div. 2), who had tested a non-empty subset of the problemset;
- antontrygubO_o for nutella testing;
- Dominater069, _istil, Error_Yuan, Monogon, awesomeguy856 for red testing;
- defnotmee, Proof_by_QED, -firefly-, Intellegent, efishel, priyanshu.p, amoeba4, evenvalue, cry, LMeyling, temporary1 for yellow testing;
- Wxssim, HusseinFarhat, Mukundan314, turska, rewhile, redheadphone for purple testing;
- Dragokj03, VladiG, b00s, SirPh, mathtsai, hashman, redpanda, larush, satyam343, antares2262, ismailfateen for blue testing;
- Valenz, shuniko for cyan testing;
- Dominater069 for identifying as green;
- tibinyte2006 for legendary-fake-lying-face grey testing;
- a few people who were invited to test but forgot/didn't have time for it;
- a few people who tested $$$\mathcal{O}(1)$$$ tasks individually but not the entire problemset;
- MikeMirzayanov for great platforms Codeforces and Polygon;
- and last but not least, You for participating! Thank you for writing legends in real-time for across $$$999$$$ and more rounds!
The score distribution is as follows.
Before finishing the announcement, I would like to spoil you a little of how the round's story ends.
Little John worked hard, honest and diligent for years, and finally got a home of his dream.
In that sense, I want You to be like Little John in this round.
Hard, honest and diligent will give you the rewards you deserve.
Anyways, that's all for the announcement; Good luck, and have fun!
UPD1: The score distribution has been announced.
UPD2: The editorial is posted here. Also we have good news that I will post as a separate report blog soon...
UPD3: Congratulations to the winners!
All participants:
- sunjia (oops, the user is gone now)
- Golovanov399
- maspy
- jiangbowen
- A_G
- fnoihzhyan
Rated only:
- sunjia (oops, the user is gone now)
- fnoihzhyan
- RGB_ICPC9
- wangzirui123
- Network_Error
- BSpioneer
UPD4: Anti-LLM Evaluation Report is published — the first of its kind for Div.2! Please kindly take a look if you have some free time or are just interested.
As a tester, I tested the 1000th round.
orz (I was paid to do this)
orz (I was paid to do this as well)
I am not paid to participate, but motivated to attend 1000th contest
Win mindset
haha. They mean they are paid to said 'orz' just for joke.
As a tester, little did I know that I tested a historical round
TheForces orz
Codeforces Round 277.5 (Div. 2) grinds
As a tester, this round was certainly one of the rounds of all time.
The 1000th round is not just a number, but proof that legends live here!
As a tester, this is indeed a historical round!
As a tester, I didn't really test.
As a tester,
As a tester, I can confirm that $$$10^2=1000$$$
But I thought 10²=100..Am I dumb?
perhaps
As a non-tester, I commented before SirPh.
orz
did you just steal my tester contribution
someone had to take it
letssssss gooooooooooo 1000th round!!! Sad I can't participate bc I have final exam :(
1e3 Nice
c5
Nf3
D5
b3
ignore my stupid comment
Bg4
h3
Bh5
g4 Bg6 Ne5
isn't this cheating to make 3 moves in a row ?
not if you don't get caught
Kxh5#
e6
Qi9#
1e3
Van't Kruijs
it's a chess opening
e5
Nc6
As a tester,I was expert when I tested.
as a tester, we needed more testers
as a tester, we needed more testers
as a tester, we needed more testers
as a tester, we needed more testers
as a tester, we needed more testers
as a participant, we needed more testers
as a participant, we needed more participants
as chillisauce, we need more snacks
as a taster, I eat snacks
as a participant, we need more tasters to eat testers.
as a tester, we needed more testers
as a tester, we needed more testers
as a tester,
As a tester, this was my first contest for testing.
As a non-tester we need more testers
Am I the only one who subconsciously thought "Yay, contest 8 in binary!" instead of "Yay, contest 1000!" after reading this? (Yes, that was my actual first thought)
As a tester, this is my first "As a tester" comment
As a tester the chain is an elaborate plot to farm contribution (and this one too)
Unfortunately, I have downvoted you in the hopes of foiling your elaborate plot.
Wait wait wait no no this wasn't in the agreement
Its alright, as a fellow tester, I've got your back!
:D
that sounds like the 8th contest in other words
As a tester of Codeforces Round 960 (Div. 2), hope the round will be interesting for you, or learn new knowledge, or get good delta.
Wow so very excited to attend the 1000th contest on codeforces !
As a tester, I can confirm that firefly is my waifu.
A millennium of brilliance! Congratulations, CodeForces! #CF1000
Is this a hint that the contest is HARD. Scared but will participate anyways.
As a first time tester, it is cool that my first time is in such a special round.
Sadly I'd be missing out this round, good luck to all the participants.
hope for many bitset problems
Quite Excited for the 1000th round :)
Why unusual time in 1000th round :(
To have it more unique and memorable?
It finally happened
As a tester, I am so happy to have tested the 1000th round. Fun fact: 1000 is the smallest composite number after 999.
There are so many fun facts about 1000, for example it has exactly 2 times more prime divisors than 1024.
Finally, someone has not forgotten about grey testing. Wait...
Wow. 1000 contests. Whatever you have, school, work, whether it is night or early in the morning we must all participate. Let's make the 1000th contest the best ever.
As a tester, I FORGOT TO COMMENT
I hope you get your fair share of contribution :)
Thank you for setting the Round 1000 on the first day of my winter vacation, instead of during the final exam.
probably the strongggest tester-lineup ever. orz!
First round I tested :)
can we know what are the points for every question please :)
galvanized steel mentioned!!!!
The 1000th contest is at 4AM for me but I'll probably still participate.
Seems like no interactives. Saaaad (|;/
Why shizuo senpai,why!!
I love destroying interactive tasks!
The Round 1000 with unusual time! A good time for Chinese
As an author, I can confirm that gcd of the score distribution is 250, excuse me if it changes to 500.
As an author, it is certain that it is a multiple of 250 anyways
As a participant, I can confirm that the contest has 1000 — 1 problems if we see F1 and F2 as 10 problems.
it's minus not horizontal bar
As someone who knows nothing about the round, I hope that:
At least one problem has $$$n \leq 1000$$$.
Every problem has $$$t \leq 1000$$$.
There is a *1000 rated problem (luck based).
Bold Score distribution ??? , chromate00 is cooking.
I was here !!!
i was here too !!!
Hell yeah baby!!!! excited
Why is the monumental codeforces round 1000 at 7am in the definitively best timezone on a weekday??? (did I just piss off a good part of the world? yes and I'm not sorry)
I really wanted to learn about Little John and his galvanized square steel, screws he borrowed from his aunt, and eco-friendly wood veneers
Sadly I guess I wont be able to.
GLHF to those participating, may bitset waifu bless you.
why not the usual time :(
do i consider trying F after C
As a tester, this cunning dogo encourages you all to participates in this round.
who are you :angery:
As a yellow tester, I was able to be promoted to red tester before the contest.
as a scker
As a participant, i will try to solve 10^C Problems :)
As a non-tester, I would like to become a tester for any of the rounds. :)
Let's go We are in the new era
Wow — Just 24 to go until a big round-number milestone!
but I don't think we can see the next milestone after 1024......
It took 10 years to get to 1000 and we'll probably leave CP by then, but anyways, gl on round 1000.
Will this contest use mod = 1e9 + 9 ?
The 1000th round of codeforces, also the 1st round in the jiangly era
～(∠・ω< )⌒★
I think the D will be difficult, so I will do the D first. If I can't do it, I will give up the contest without any submissions. :(
So I can keep my rating.
Man it's starting earlier than usual, sad. would have to miss the 1000th round due to my labs at that time :(
as a participant, it is my 100th contest
as someone who missed 999, i will not miss 1000 round.
I'm really excited to take this significant round at 6am on a weekday. Good luck to everyone else participating!
I mean, I just have to leave something here to prove I will be in such a historical contest
I have moved to a country which is exactly 2.5 hours ahead of my home. Good luck for me that this contest happens to fall at my "usual" time at home. I have to participate for old times sake.
Glad to be here for a big milestone.
As a tester, I tested the 1000th round.
this contest's time make me can't participate, so sad!
Participating 1000th round before Ronaldo hits 1000 goals
Let's Go!!
Hopefully I can become an expert through this contest.Good luck.
Waiting
As a Chinese student, I think 20:05 UTC+8 is a great time to be tested by a contest.
VERY GREAT
As a non-tester, I believe that this context will be something more than just a context, this is a mark of 1000, we can say that this is a very memorable mark in codeforces itself, for which I very much congratulate them
From this round, I’m restarting my journey of giving contests on Codeforces! Best of luck to everyone participating in this contest!
It would be great if i could solve 3 problems in 45 mins and 4th one by end of the contest
Why our problem rating graphs lowkey same???
damn they actually do, but you have solved more problems of almost each rating than me lol
do you work in tcs? (just curious)
No i don't, but i wanted to :)
nvm
As a participant, I'm gonna participant in a historically legendary round!
I wish success to everyone who is participating and thanks to everyone who tested, problemsetted and overall contributed to this round!
<3
It's the time
qp
ROUND 1000!
WISHING EVERYONE +Δ ON THIS LEGENDARY ROUND!
as a newbie, We need more rounds
As a participant i hope to reach cyan
Thank goodness the time has changed to 20:05(UTC+8)!
Or I'm not able to participate again......
1000 less go!!
Congratulations to Codeforces for allowing a confirmed cheater to host and write an announcement post for their thousand-th round, which is criticized by a confirmed sub-account (lol)
So did he test the contest as green or is this him coming out? lol
Round 1000! Great!
I was here too.
Codeforces Round 1000, I'll definitely participate the contest!
Really excited to give the 1000th contest of CF.I beginner in CP ,anyone who can advise me how to do CP as a beginner.
I started with Round 320 and now at 1000 today! The excitement is still the same. What a ride it's been. Here's to many more!
I will give this round from my office :)
It's wonderful to be able to participate in such a historical round.
I wonder if there will be such day where i would solve div 2 D
Came to register for contest and found that contest is almost over. Totally didn't missed to notice the unusual timing.
What's up with C? Why is removing the highest degree node, updating degrees, and then removing the highest degree node again wrong?
there may be multiple nodes with the highest degree, meaning arbitrarily choosing one of them may not be optimal.
Counter example please.
The program should pick non-adjacent nodes if possible. If you pick adjacent nodes, you will have one less connected component than you expect, because the removal of the edge connecting the adjacent nodes does not lead to a new connected component (as there is nothing in between the two nodes — they are adjacent).
In case there is only one node with the highest degree (for each removal), the idea works; but otherwise, you might pick adjacent nodes (even though you can do the opposite), which leads to the situation described above.
In case there are two nodes for the highest degree it still works because picking a non-maximal node would at best yield the same result than picking two maximal adjacent nodes, so the latter is optimal. But cases where there are three or more such nodes should be handled in a separate manner.
three max degree vertices in a line.
2 cases => one of the two choosen is middle one.
other case when middle one not choosen.(more connected parts then above case)
One test case:
1
11
1 2
2 3
2 4
5 6
5 7
5 8
8 9
8 10
8 11
I tried all the highest degree nodes, doing it naively in O(n^2) and got TLE on test 9 (don't know what I was expecting). Waiting for the editorial to find out how to do it correctly.
i also tried all highest degree node but optimally
It's a dp type idea: we solve it for each subtree. For a root of a subtree, i, there are 2 cases: (1) remove i and some descendant, or (2) remove 2 descendants. To do this properly, we have to precalculate mxdeg[v] for all vertices v, denoting the max node degree in v's subtree, excluding v. Just look at my code for further detail.
I don't think I can see your submissions, but the editorial solution seems to suggest bruteforcing the maximum degree vertex and then finding the maximum degree vertex among the resulting subtrees using a priority queue or a multiset. A shame I didn't see that.
the main idea is if there exists a pair of highest degree nodes that are not neighbourhood, one's removal will not affect another one.
hence if there are 2 highest degree nodes, check if they are neighbourhood. if there are 3 or more, there must exists such pair since it is a tree.
edit: typo
ans is highest degree + next_highest_degree-1 , and now u have to choose such a node for highest degree that removing it maximize next_highest_degree , cause removal of some node can lead to decreasing it
lets say if u remove highest degree node then degree of surrounding nodes will decrease by one
1 2 / 1 3 / 2 4 / 4 5
you can consider the case where node 2 is chosen first.
u need to consider two cases, one where the selected nodes are adjacent and another where they are not
D kills me.
It's ok! It's the idea to do greedy but remembering past choices so you can undo them when needed!
Help me out please why is my DP solution for C giving WA on test 2?
Edit: Nvm I got it. I missed the case where we take 2 descendants.
this contest want to make me kill my self
real
me too
i hate myself
nothing can save us, but reborn as gifted Chinese kid next life. there is no way around this is OVER! I'm done with CP
guess i'll go back to leetcode :,(
Wow opened codeforces the moment contest ended and missing the 1000th contest because of missing the time . Yayy Luck :)
I think this contest is perfect! Problems have no mistakes and their qualities are high. I have a nice experience through this contest!
forgot to remove my debugging prints on my last submit lol
Wasn't able to implement it but here is what i think the solution for F2 is, let use assume that we are trying to find the answer for the first $$$i$$$ segments, we define the score of any segment $$$j$$$ as the number of points inside the segment $$$j$$$, for which $$$j$$$ is the minimal segment i.e. for any point $$$i$$$ and segment $$$(l,r)$$$, this segment is minimal, if $$$l \le i \le r$$$ and there doesn't exist any other segment $$$(l1,r1)$$$ such that $$$l1 \le i \le r1$$$ and $$$r1-l1+1 \lt r-l+1$$$. Now, the answer is the product of the catalan numbers for each segment's score by 2.
To handle addition of segment $$$(l_i,r_i)$$$ efficiently, you just need to find the minimal segment $$$(l,r)$$$ for any point inside $$$(l2,r2)$$$ and change the score of this segment and update the answer. This is a standard problem that can be done in $$$O(logn)$$$.
Why am I getting wa on pretest 3 for C? Code In first dfs I tried deleting 2 nodes from subtree of a node. In second I tried deleting current node and one node from its subtree. I kept a check if difference in height of max children node and current node is 1 to subtract 1 for the empty middle portion.
Second Question was quite confusing .....
My screencast (in Rust). Should be available when video is uploaded.
your screencast are always boring that's why noone watch them
Why my code for C failed at pretest 4, My Code 1. I tried removing highest degree node,then recalculating degrees and then again removing highest degree node
Removing the highest degree node greedily won't always work. Suppose:
Tree: 1-3-2-4-5.
Here nodes 2,3 & 4 have degree 2. But here we have to remove node 3 & 4 to get the maximum.
I also solved q3 thinking of same example
Yess got it! Thanks:)
thankfully, data structures made round 1000 go terrible!
C was quite typical for me I knew i have to remove the two nodes with maximum adjacent nodes I m implementing it wrong ig :(
Can anyone explain to me like a 5 year old
try looking at the case where you have 5 nodes: 1-2-3-4-5.
all in a straight line so 1 connected to 2 and 2 connected to 3 so forth so on.
;( what was ur approach regarding this
i don't like my approach a lot tbh I think editorial might have a better way. the way I did it was you count how many nodes have highest number of adj nodes (so number of nodes with highest degree). If the number of nodes with highest degree is >= 3 then you know you can basically split it like this twice. ex: if you have 3 nodes with degree 4 you know that 2 of them aren't connected so you can remove them both. else if there are only 2 or 1 nodes with highest degree the algorithm you are doing will work. I just added one if for testing if number of nodes with highest degree is >= 3 and brute forced that answer. I think editorial might have a better way tho :D
damnnn imma look at editorial later will try to upsolve it thanks bro
ChatGPT BTFO XD
but at what cost..?
which one
idk that's what author claimed
i am never using accumulate again in my life
You missed the question because of overflow when using accumulate with start value 0?
yeah
i lost about an hour trying the find the bug it was an overflow due to the 0 being int not long long
This cloudfare stoped me from submitting my correct code to E。
It stucked me for about 3 minute。 Do I look like a robot？
I can't be CM now。
Yes, it thinks you do.
Can anyone please tell me why my code for problem $$$D$$$ got WA on test 6 ?
my idea was to take the highest value between $$$a.back() - a.front()$$$ and $$$b.back() - b.front()$$$ if I can
and if this will result in reducing the number of ways to take the last triangles, I will output the answer and then remove the highest value and take the smallest one
what is wrong with this idea ?
Consider that all of a's have huge space between them and b's are close. You will always pick 2 a's and 1 b until there are few a's (say 1 or 2 depending on how you coded the last cases). Then you will be forced to pick 1 a for the last cases and you will be left with a bunch of b's and no a's. You could have picked more b's in the start to keep the process going for longer. Your solution is correct with regards to optimizing the first cases, but from a point onwards your process will halt prematurely (your
k_maxwill be less than the answer).I know it because I did the same mistake too:
https://codeforces.net/contest/2063/submission/302438325 -> exactly same idea as yours
https://codeforces.net/contest/2063/submission/302461122 -> solution allowing going backwards to keep the process going for longer
Thank you a lot to explain it
I tried it and got AC, nice idea!
your first code is very similar to mine xD (using pbds ordered set and removing the edges and the middle of the other one)
Can D be solved using ternary search? By the time I finished implementation the contest just got over. My code is passing samples, will have to wait for system tests to finish to see if it works.
I am fortunately that I didn't participate in this contest, if I do, i will become a Specialist.
1000th round and I messed it all up
true
So what's the meaning of F1 :thinking:
????
It could have been a better idea to be extra careful when organizing a special round like this one. It's not just numbers; "the 1000th round" feels like a very inspiring round to attend. This was the first round I attended in 7 months. My rustiness alone doesn't explain my terrible performance. Ending my break with a contest like this was not nice, and I think many of you have similar feelings.
Missed F1 by 1 second :(
I thick E is much easier than D.
Problem C really tricked me into doing a casework DP :(
I first thought to apply DP on trees but figured out that greedy selection of nodes with maximum net degree would work !!
chromate00 Can you fix the problem ?
I tried rejudging it, but it still doesn't get to system testing. I will ask the coordinator and KAN about it.
It is Accepted now. Thanks to everyone who participated in the making of this nice contest!
Is this round rated or not? I solved 1 problem and expected my rating to rise.
Wait !! It takes some time to calculate the ratings. It is rated as of now.. You will get a rating soon !!
As far as I know, there is some initial boost given to you for your first few rounds. See this.
(Edit: Wait, I might have misinterpreted your comment as your rating being predicted to increase. Sorry if that is the case.)
I'made a mistake,I took the round way too casually.
a historical moment XD
Happy 1000 everyone!!
This was such a beautiful contest thanks !!
Do something to cheaters Youtube channel This youtube channel is providing solutions in live stream.
Can somebody give me some solid edge test cases for C problem, I don't know why my code is failing?
5
1 2
2 3
3 4
4 5
I am getting 3 for this, need a better test case.
10
8 9
4 3
4 2
10 9
1 9
2 10
2 5
6 10
5 7
For C, is this a valid testcase? Answer should be 5 but one of my code gives 4 but it got accepted.
1
12
1 2
1 3
2 4
2 5
3 6
3 7
1 8
4 9
5 10
6 11
7 12
As a tester, this is indeed a historical round!
every time i see miku in comments i remember De3b0o
me too
For problem D , after fixing $$$[l, r]$$$ for a fixed $$$k$$$ , how do we calculate the maximum value of $$$f(k) = \max_x g(x, k - x)$$$
read editorial
...you could ternary search or binary search
could u plz elaborate the binary search solution This submission by Golovanov399 has an elegant binary search solution but i cant get it through 302391355
ternary search on value <-> binary search on slope, and you have the slope given by $$$a$$$ and $$$b$$$ sorted. rest of proving what is necessary for bsearch is explained in editorial
I made a video tutorial, https://youtu.be/v4Dt37mBIBA
what happened to sunjia?
Good
Is it just me or other people also thinks that the problems D, E and F1 have similar difficulty?
gg
A,B,C,D,E Video Solutions here: https://www.youtube.com/watch?v=v4Dt37mBIBA
Contest is awesome
I received a message saying that my submission matches with another user, in this matter i would say that the problem was very simple and had a straight answer, also since the variables were already mentioned in the question, we i didn't bother to change them. Also our time stamps of submission are very different. Please look into the matter.
As a tester, I have a proof that upvoting this comment will lead to positive delta. But the proof is too long to fit the margin.
as a tester,