Ciao, Codeforces! We're glad to invite you to take part in Codeforces Round 975 (Div. 1) and Codeforces Round 975 (Div. 2), which will start on 27.09.2024 16:35 (Московское время). You will be given 6 problems and 2 hours and 30 minutes to solve them in both divisions. Some problems will be divided into subtasks.
UPD: the time has been changed to 27.09.2024 16:35 (Московское время), which is different from the time announced before. Please note the unusual starting time.
This round is based on Italian Olympiad in Informatics (OII) 2024.
The problems were authored by lorenzoferrari, wksni and me.
We would like to thank
- KAN for his nutella coordination;
- Alexdat2000 for Russian translation;
- bortoz, collodel, dp_1, franfill, francesco, harniver, jamesbamber, Kaey, veluca93, Virv for helping with both this contest and the onsite contest preparation;
- bortoz for pictures in the statements;
- Flamire for VIP testing;
- Um_nik, EgorUlin, konred, MuUJa, bugrova, Ludissey, Nonoze, Sofapuden, Temmie, jeroenodb for testing;
- MikeMirzayanov for creating Codeforces and Polygon.
Score distribution:
- Div. 1: $$$500 - 750 - 750 - 1500 - (2250 + 750) - (1500 + 1500 + 1500)$$$
- Div. 2: $$$500 - 1000 - 1750 - 2000 - 2000 - 3000$$$
We hope you'll like the problemset!
Update 1: the editorial is here.
Update 2: congratulations to the winners!
Winners and first solves
As the first commenter.. thanks for the div1 contest.
do i wake up at 1 am to do this?
There's no option, bro. isn't it div1..
The starting time is (on purpose) similar to that of the onsite contest.
Well, you kind of forget that there does exist a certain part of the globe where they always had to wake up at 12 AM to take contests
Hopefully in the future we will have more contests for different time zones.
Now , you don't have to
I'm sure this round will be cool !
This is an odd timing tho, anyways this will be my first contest
Same here! Good luck.
no offense or anything but i never understand your round editorials so please focus on them being good this time
edit : also include proofs most recent rounds i feel like we get the solution thrown at us with no proof or anything attached last round problem D is an example
Cool, another round I won't be able to attend
ㅤ
is it possible to reschedule it to 20:05 utc+5.5 on friday, if then please do it. otherwise no problem,I will have to do it virtual, because in daytime i will be in my office for friday, or you can make it saturday the same time. It's not a problem to miss contests for unavoidable reasons but if possible, I don't want to miss it.
People who use AI, why are you doing this? Besides the fact that it is forbidden, it also kills all the interest of the competition. What is the interest of such submission if in the end they will not give anything in terms of experience, and the account will still be banned.
Why do you have to bring up this topic? AI users will not stop using AI after reading your comment.
that is 11 in the morning for me ._.
I hope the time will be changed to 22:35(UTC+8:00) as usual.
Great time for me. Hope for more.
I want to know if I can participate div.1 with the score as low as me and if I can only participate div.2 or I can participate both.
You can participate in only div2 and not div1, I think for div1 lower bound is 1900
okay, thank you for your explanation .
1:35 pm for me it will be great I am gonna skip college class that day
You can skip your college class, but for me in our country ,the contest will begin at night and it will finish until most people has been slept. So I should increase my CF score by staying up late.
finally, a contest at a good time for Americans
what an amazing time for Americans
Is the score distribution for Div1 and Div2 correct ? Since when did Div2 C become 1750 rated ? I think there's been a typo ?
so what does that mean if its set at 1750 ?
Generally Div2 C's have points of 1250-1500. More points mean the problem is likely to be more challenging.
It means it will be a speedforces round with 10k+ submissions on B and <4k on C.
why the unusual starting time ?
please downvote
read the post carefully, everything is written there. This round is based on the Italian Olympiad in Computer Science (OII) 2024.
ok thanks
Unfortunately, I have school at this time :(
Weirdest way to skip a Div1: possibly coinciding with team meeting at work...
cool time in general, but not in friday XD
oh shit. i thought it is Saturday. that means missing last 10 minutes or so ?
No need, the time got changed
he really has the last name "ferrari", impossible.
it actually is the third most common surname in Italy! :)
As a tester, I hope no one will be using AI instruments (^˵◕ω◕˵^)
As a tester, I wish all of you a good luck!
Div1 is too few. More plz :)
You are right.
Why use Ciao instead of Ciallo(✿◡‿◡)?
Oh no, it’s 16:05 in China. I am in school that time, bad luck to miss a div1 again.
Serve you right.
As a tester, I'm so happy to be able to say that!
my strategy: stare problem C for 30min if ! solvable goto bed
I'd participate if it was 6 hours or a day later. This is a big F you to students and working Americans and Europeans.
Aren't the ratings for the rounds swapped?
Read this blog
swap div1 with div2
Div. 1 and Div. 2 use different problemsets, so comparing their scores doesn't mean anything.
Waiting a month for a div1 only to get a 4am round :(
isnt the scoring distribution for div 1 usually higher
Not necessarily, and there is no reason why it has to have higher scores, as Div. 2 and Div. 1 are completely separated.
Wow, this is a very suitable match time for our Chinese compatriots, and I am looking forward to having a good performance ：)
I love U ❤️. There is a love story between us ❤️.
I love the words
I love u, can we be a friends?
Now I will give div-1 or div-2? Div- 1 looks more scorable than div-2. And div-1 rated range?
Expert and below can participate only in Div. 2. Div. 1 is for Candidate Master and above.
point values are not representative of absolute difficulties, only the relative difficulties (sometimes they too might be wrong because authors mispredicted)
it seems that d2C = d1A in this round, you want to get C as first problem?
very interesting distribution for div1.....maybe consider increasing time?
Why Flamire is the $$$\text{V}\color{red}{\text{IP}}$$$ tester but le0n isn't?/kel
$$$\text{L}\color{red}{\text{GM}}$$$ ? (bruh he's not even tester)
Nonono.. bro, $$$\color{black}{\textsf{l}}\color{red}{\textsf{e0n}}$$$ is going to be LGM very soon.
Because he didn't test.
Because I didn't test.
Every time i open CF, the score distribution changes.
UPD — They changing time now as well.
Why was the start time of the contest changed?This is not very friendly to me in China.
This is very friendly to me in China.
What was the original time in China?
Thank you for adjusting the time
Sorry for changing the starting time. I've just known that there is a OII contestant who participates online. With the previous starting time, he could access Codeforces and the submissions before the end of the official OII round.
I see, no problem. Lucky for me now, as new starting time ensured I would have finished my workday before joining... XD
i think you should make a note on the blog that the time changed, i noticed it only because of a comment, and im sure a lot of people don't go scrolling through comments
I think there is no need to do another post for it as the contest is postponed,not preponed!
A div1 after such a long time, but on a weekday afternoon, Have to wait for the next one now :((
Oh its changed, my bad, orz
jeroenodb is so orz
hope it will not have any interactive problem :)
I think so too!!!
The rare daytime div2 in China has disappeared …
Has the time been changed? What was the original time?
About 4:35 ......
D=F1<E1<F1+F2=E1+E2<F1+F2+F3
I have to say that strategy can play a huge part in this contest for IGM/LGM participants...
my CM self will be lucky to get ABC.
Looking at the gap between B-C in div 2. I have to mentally ready for hard problem this time.
Why did you move the contest to 16:35 utc+3?
See here.
Hope to reach CM :D
My local time is 21:35 (UTC+8), which is within my acceptable range. Can you tell me what time it is there?
Hi
Is it safe to assume its a typo that the div 1 score distribution is easier than the div 2?
As a tester, I tested.
As a participant, I'll participate
Ugh have to skip this due to change in time. My sleep cycle forces me to sleep at 5-6 these days. Atb everyone
speedforces!
Why Candidate Master is now div1? It was div2 last contest.
Candidate Masters are Div. 1 when it's a Div. 1/2 parallel round. They are also rated in Div. 2- only rounds, but cannot participate in Div. 2 when there is a parallel Div. 1 round.
You realize that we have had too few Div. 1/2 parallel rounds recently when you see a bunch of questions like this...
Hope tourist can come. But, can he keep the red-black name?
Is such rounds based on OII doesn't concern on advanced topics probelms?
i assume the harder problems(div2E+ or div1B+) will have similar ideas as problems on the olympiad, or might even be the same. i doubt that regular div 2 ABC could be actual olympiad problems, so that will probably only be relevant for the harder problems
unrated not allowed ?
Finally there is a competition that time allows to participate.
Good luck everyone!
ez for me
Update for Div1C,this is like the 5th time you change score distribution.COME ON!!
Wish to get some plus
great start time!
Why Flamire is vip? I'm jealous now
rainboy's 300iq strategy
rainboy solve E1 and E2 :)
Why the odd timing?Already got least contest in this month and now missed this contest too
It's based on the Italian olympiad.
So they put the online contest as close as possible to the onsite contest to avoid leaks.
Also they explicitly warned about the unusual start time in the announcement
Why start early? I lost an hour of problem-solving time!
nutella coordination means?
It's mean that an LGM did the coordination, they are red+black first letter hence the name
TheScrasse never let me down ! , Thanks for brief statement and amazing contest !
You've two ways to color
Iterate through both of these ways with getting the
, and the final answer will be :
Complexity is linear.
maintain a map $$$f$$$ such $$$f_i=\text{count of integer points that contained in exactly } i \text{ segments}$$$
This can be claimed by
Now gaps between any consecutive points represents how many integer points lie strictly between the two points ($$$g=x_i-x_{i-1}-1$$$) , if the gap is non-zero then each of these points is counted as being in exactly $$$i$$$ segments , and update $$$f_i$$$ such
Finally print the answer per each query .
Complexity is linear.
Compute both of The total number of cards : $$$\sum_{i=1}^n a_i$$$ and The maximum number of cards of any single type $$$\max(a)$$$ .
The maximum deck size by descending iteration order i.e. $$$(n \rightarrow 1)$$$ so our goal is to compute the maximum number of distinct cards that can be included in a deck which is
There are two conditions that must be satisfied :
The total number of distinct cards required for the decks can be achieved with the current number of cards plus the cards you can buy.
you can also have enough distinct card types to fill a deck of size $$$i$$$
Once they're satisfied then print $$$i$$$.
Can you tell me why this didn't work ?
function
fcalculation is wrong (mostly that's the issue) + binary search doesn't work :(Div2E >>> Div2D
You mean to say the opposite Ig
Even after like a million submissions idk why my binary search solution on C won't work DAMNIT!
bro, binary search is clearly wrong
But why ? If you can get say deck size 'x' , you'd try higher else lower.
However, in some cases, the number of card pairs caused by the size of your deck may be less than $$$\ max a_i $$$, which is illegal.
There's probably no clue about which side of binary search you will go after you check the answer, so binary search couldn't work. Although I noticed that, I forgot to get rid of binary search at the first submission which cause me WA on test 4.
Each time of checking the answer costs you $$$O(1)$$$ so you can simply go from $$$n$$$ to $$$1$$$ to check if that is the answer.
Well, my solution was based entirely on — "If x is not possible, x+1 isn't too" Guess I was wrong ? Can't think of a testcase tho ?
That's the matter if you could prove "If x is not possible, x+1 isn't too". Here is a small test case which you should take a look to:
Input:
1
5 1
3 2 3 4 2
Output:
2
Expected output:
3
There's one more crucial issue in your implementation that I've figured out. Your check function isn't true either.
yeah I also did binary search first to solve it got wa on test 4 then got that I can do linear search as n was not that big so I did linear search with same idea and got the correct answer in last moments XD
But you can use ternary search
it wont work because its not a monotonic function
like for this case
10 8 7 4 6 6 9 3 10 2 8 7
for deck size 6 there is no possible way, but for 7 there is a possible way
trash problems I lost rating because of them
just kidding, the A-D Div.1 problems are actually nice, a bit easy for their place though :D
Why give constraints with long long without notice? I got 2 TLE because I read k with fucking int.
Div1E: The usage of the term "(sub)set" is not standard because it allows (multi)sets. I asked about this, but it is weird that no annoucement was made.
--
Div1F: Since I felt this is close to cheating, I asked "If we lock problem B, we can make hacks on B (without solving F)?" and received "Yes". After that I found out I can check submissions only from my room (right?). I think this is unfair and the settings for hacks should be checked more carefully.
I have to admit that I gave up joy to "solve" the problem alone for speeding up... By the way the problem itself was fun! (though a bit easy for its position)
I think the main part of F is a dp approach that does not appear in solution in B, so "cheating" will have little to no help in terms of solving F.
This round reminds me of Moscow Open Olympiad in Informatics rounds :)
Do you play GD btw?:)
No.
TheScrasse Your rounds are absolutely fantastic everytime man! Nice problems, thanks for the round!
D is really great！
I got cancer while debugging Div2E/1C
isn't this really just compute all distance from root
then from 0 to maximum distance, compute operations require (remove all greater, remove all lesser, adjust by cnt[k] because there will be path) to make every leaf have distance of k? then take whatever minimum.
That's basically true. The only thing left is the implementation part.
C++ on CF (maybe memory allocation?) is unwelcomely slow.
My F1 works around 6000ms in AtCoder custom test with
1 500 998244353, but the custom invocation of CF says it's TLE(>15000ms).UPD: It seems not only memory allocation, but also totally slow.
My fixed F2 said 3600ms on CF, but same case runs around 1000ms on AtCoder.
I do think CF needs to update its grading server. It is probably the only main onlinejudge that runs slower than my computer (and it's 2x slower!)
Cheating in this round started from 80' onwards. Problems 2C and 2E solved by lot of newbies from around that time.
My solution to problem C was not run on the system tests. Is it a bug?
283226196 TheScrasse I think you've to rejudge this submission on system tests ..
HCPS42 it's accepted anyways
283260736 (Your Code)
UPD : Fixed
In the standings it is shown as "-1"...
KAN
div1 F can be solved in $$$O(n)$$$. Let's fix our final segment $$$[l,r]$$$. Let's compute a dp[segment] such that the segment has $$$[l,r]$$$ inside it. We know that there is at least one of the bounds of the current segment such that it is not inside $$$[l,r]$$$ and it is at least (length of our segment+1). We can remove it, and we can make a dp in order of decreasing of a segment length. But there can be two such bounds for a segment, so we should use inclusion-exclusion. It is $$$O(n^{2})$$$ right now (dp is the same for all intervals), but we don't need to store the segment, we only need to store its length, so we can make it $$$O(n)$$$. (When we go to our segment in dp we must add some number of ways to place the numbers inside it to the answer of its length).
Now we calculate the number of segments of length $$$k$$$ lying inside the final segment, and from this we can get the number of final segments of length $$$k$$$ in $$$O(n)$$$.
Code
well I gained + 172 and successfully doing ABCD in reverse order.
what i am not pleased with is the problem E, why it is so easy?
Congrats Dominater069 for rank 56. I always wonder, how do you manage to be so so consistent in your performance, always, unlike most. Its insipiring. The rating graph is just absolute perfection. Wishing you to steadlity rise to the rank of LGM.
Thanks TheScrasse for this nice contest. First time I became CM
The first time I became an expert was also in your contest.
I hope you make another contest as soon as possible to become master.
3ash ya bro ma tb3t sheet al math aly by5lek t7l as2lto kda
حبيبي <3
I didn't use any math sheets When I see that I am struggling with some topic, I just solve more on this topic in my elo in problemset
you can try this sheet also its general. I think this will be quite good for your elo now
The sheet I started with
If you have any questions feel free to DM me
Problem Difficulties:
A2 — 800
B2 — 1000 (weirdly I found it harder, due to awkward implementation, for me it was like a 1400).
A1/C2 — 1400
B1/D2 — 1900
C1/E2 — 1900
D1/F2 — 2500
Did not try to seriously solve anything harder.:)
can anyone solve "cards partition problem"-by using binary search
No
I have a strict $$$\mathcal{O}(n)$$$ approach to the Div1 C problem, which uses long-chain partitioning to optimize dynamic programming on trees.
283907902
I was just warned about coincides solutions in problem C Div2 Round 975 with another person and below is my explanation Solution coincides but Problem C is simple enough and the chances are higher for coincidence. This happens because question C Div2 of this round is actually quite simple without using any special algorithm to solve it. Just brute force the number of each type card and you can solve it ! This leads to someone having the same idea of solving this problem as me and causing unnecessary duplication In addition, I was warned for repeating question B, but after I checked the account of the person who coincides with me .Again, I solved this problem before he solved it Please look into this matter and don't penalize me unnecessarily.THANKS A LOT!!
If the coincidence occurs due to the template I am using. Then you can check my previous submissions from the time I created my account until now, I still use it like that. And this template is also extremely popular but has two more features of mine. //++i //'\n' In this case, I really didn't mean it and I sincerely apologize for it. If possible, in the following contests, I will change my template to avoid affecting others as much as possible THANKS AGAIN!!
I want to address the notification I received about my submission for the problem 2019B - All Pairs Segments. I’d like to clarify that the formula and approach I used were developed independently by me.
While working on this problem, I drew on my understanding of the line sweep algorithm from 1000C - Covered Points Count, which I have seen before. That problem also deals with segment contributions and efficient calculations, which helped me think through my solution for "B. All Pairs Segments" and arrive at the solution.
The solution I submitted was based on my insights, and I created a new formula to calculate each segment's contribution efficiently, specifically for this problem. I made sure my solution was original and not a copy of anyone else's work.
I kindly request you to reconsider the situation associated with my submission. Thank you for your understanding.
yeah same and that formula was also used in editorial everyone has used same formula mine was skipped bcz it matches with 283209041 this solution but it isn't he has used some strings I don't know why he even use unordered map and I used map only and I used pretty famous naming conventions IDK why it got skipped I didn't cheated at all I never cheat
I have received a mail that my solution https://mirror.codeforces.com/contest/2019/submission/283247602 "coincides" with some other solutions. For example, it matches with https://mirror.codeforces.com/contest/2019/submission/283226239. If you check these links you will see that the way of writing the code is completely different. The only thing that matches is the logic for doing the problem. It is the same with all the other submissions mentioned in the mail. Now, the problem is that I did not cheat. This is a fairly simple logic to think of. If you look at my submission, you will see how simple of a logic it is. Also, the only thing matching with other solutions is the logic. When the problem is fairly simple and so is the logic of solving the problem, similarity in the code is bound to happen. Basically, anybody who has thought of this logic will be punished if such checking is done. Maybe this is because of the new AI regulations which is making the system "overstrict" and causing problems like these. Kindly look into this issue.
CP is wasting of my talent I am much smarter than CP