Hello, Codeforces! 😇
We are glad to invite you to participate in Codeforces Round 932 (Div. 2), which will take place at Mar/05/2024 17:35 (Moscow time) 🔥 😱 🤩
The round has been fully prepared by students of the School CPM 💓 (School of the Pedagogical Skills Center): IzhtskiyTimofey, AndreyPavlov, and myself. The theme of all the problems will be our beloved school 😈
This round will be rated for participants with a rating below 2100 😊 Participants with a higher rating can take part out of competition 😋
We would like to thank 💕:
Our wonderful coordinator Artyom123 for helping prepare the problems and valuable advice! 😍
CPM students azureglow and max0000561 for proposing problems 😎
Our teacher grphil for nurturing young talents 💋
TheEvilBird and NToneE for creating wonderful contests for the superhard group 🤮
Geothermal for detailed feedback on the problems and improving the quality of the statements in English 💘
Our testers A_G, SomethingNew, induk_v_tsiane, zwezdinv, k1sara, meowcneil, antonis.white, maomao90, MOHOXPOM, qualdoom, makrav, sergeev.PRO, Kihihihi, DimonKrutoi, htetgm, tiom4eg, Mikhango, MrEssiorx, adepteXiao, YakovLya, sunsh1ne, AVdovin, Egorsa, mishgun, dasha..zhilina, marzipan, kaido, jgjgjjg, mkshh, Makarchik_228, Nikitun for suggestions to improve the problems 😘
MikeMirzayanov and the entire Codeforces team for creating the wonderful platforms Codeforces and Polygon 💖 💙 💚 💛
You will be offered 6 problems and 2 hours to solve them! We tried to make interesting, beautiful, NP-complete problems with strong pretests 😁
Score distribution: $$$500 - 1000 - 1500 - 1750 - 2500 - 3000$$$ ✨
We wish everyone good luck in the round, and we would also like to wish good luck to the participants of the upcoming Open Olympiad in Informatics and ROI! 🥇
UPD: Editorial
UPD 2: Congratulations to the winners!
Div. 2:
Div. 1:
We apologize for the disbalance in our problemset. However, we hope these problem fun and interesting!
Another Div2 !! YAY!
So many emoji faces, but no author faces? 😢
I am struggling to get better in even DIV3 :(
As a tester, I can assure you that all tasks are interesting and worth trying to solve.
Also GL to all participants :)
hey how do i become a tester for a cf round?
i wish you the best in your testing career!
It seems to me that the author of the round should know you and trust you, that should be enough.
As a school cpm student i recommend you to participate >.<
Is CPM some sort of online school ?
there are both online and offline classes
i study offline
As a top -1 contributor and tester of this round, I recommend you to participate in this round!
Bro posted only one blog and got the worst downwote damn! X_X
Another red flag
I feel it is gonna be negative delta day :'(
downvoted rounds are always fun
Yeah you will certainly learn something! Rounds are definitely fun irrespective of Delta, but check the link in red flag, you'll get ma point
In my opinion, the round is high-quality and has pleasant tasks.
Good luck to all participants!
Thank you
As a tester I highly recommend you writing this round!
As a tester, I have enjoyed solving problems, and I hope the participants will enjoy it too!
GL HF!!! (◕ω◕)
Can I call out your name if I run into trouble during the round?
No problem
don't trust these guys
hhhh
yo
.
As a tester, I think everyone should write this quality round
Hoping for the best Div.2 round!
Will the contest have interactive problems??
Hope Um_nik can solve problem C.
What's the joke?
This is the joke.
https://codeforces.net/blog/entry/126461
How does this relate to 'problem C'?
In previous round made by two of this round's authors problem C was NP-complete.
And what's the issue with problem C being NP-complete? Just solve P=NP problem first and then come to solve problem C.
whats the meaning of NP?
Not Possible
Or probably because problem C in last 2 contests were harder than usual and also interactive.
Codeforces Round 931 (Div. 2) and Codeforces Round 930 (Div. 2)
Maybe this — Link
Why is this not on the home page yet? This post would definitely decorate the home page with all these cute emojis!
I think it takes some time for the announcement posts to be added to home page
Hope to solve A and B in this round
Good Luck for every parcipicant!
Omg! So many emojis!
Dahm the post is so wholesome
One of the most beautiful announcement ever!
Hopefully i will back my Specialist rank
emojiforces
[deleted]
What is NP complete problems
Easiest class of problems that can be solved by simple bruteforce
I also love penguins UwU.
orz penguin round!!!
Another Div2 !! YAY!
emojis;)
Hope to see myself cyan!!
Hoop to see myself purple:)
Seems like SpeedForces looking at the score distribution
Emojis spoiled a very good blog :(
yeah, I think there was a bit too much of them.
as always hope for interesting and SHORT STATEMENT problems!
Excited for a thematic twist! With problems inspired by your school, this round promises to be both nostalgic and challenging.
As best pop singer in Russia, i recommend you to visit my concerts (and ofc participate in this round)
this post so cutee XD
Why the announcement looks like copy pasta of instagram's comment section
bro used all his recently "used" emojis from his phone
Legends say you'll turn gay after this round :v
this guys are cool i know
need to see authors' faces to know if this contest is reputable
no interactive?
Can you make it a dating contest(blog has some lovey dovey emojis ) aviralarpan3301 any suggestions?
Yes, one suggestion is to give abcsumits -400 rating points so that he can be pupil again :)
go do some problems weakling
Please upvote, thanks.
Don't use emojis again , please.
Hoping to improve Problem solving skills.
Synaptic_Savant orz
I hope to retrieve my rate :(
I wish the authors made us some easy C problems this time
I hope everyone gains some rating this round! (even if its impossible)
is it just me or have Div2 contests become harder ;-;
just u bru.. just u
could be lmao
I wish the problem-setters specified that messages can be sent in any order in problem C.
It took me an hour and 3 WAs to realize that I was solving a much more difficult version of the problem.
How to solve C is it dp
C and D should be swapped
I am sorry that C was harder than D. From testers' feedback the problem was even too easy for C, my apologizes
Maybe include more lower rated testers next time
i guess implementation was easy but but grasping the underlying logic may be challenging.
Problem c seems like binary search..
any hints?
The editorial was published
D <<< C
Thanks!
C>D for me..
Is c a dp problem
C was greedy with heap. You can simplify the summation into sum(api) + max(bpi) — min(bpi) and brute force all pairs of bp, adding the smallest apis in the range of [min(bpi), max(bpi)] until you can't add anymore without going over l. It can be done with a max heap.
There is a fairly straightforward greedy solution.
Re-order the messages so the values of $$$b$$$ are sorted in ascending order.
Then if you want to pick $$$k$$$ messages in the range $$$[i, j]$$$, the minimum cost is just $$$|b_j - b_i|$$$ + the $$$k$$$ smallest values of $$$a$$$ in the range. Note that for a fixed $$$i$$$, this cost increases as $$$j$$$ increases.
So we can start from each $$$i$$$ and iterate on $$$j$$$ and putting the values of $$$a_j$$$ in a multiset $$$S$$$. Then just remove the largest values from the set as long as $$$\sum_{x \in S}{x} + |b_j - b_i| \leq l$$$ and your answer is just the maximum number of values remaining in the set for any $$$[i, j]$$$.
Why are we not subtracting b when deducting a. Why not take k smallest b along with a in that range
How to do B ?
My idea was looking for first element which is less than two occurence in the array.
If occurence is 1 then answer -1,
If occurence is 0,then construct two part from 0 to this element first then another portion after that,if possible answer is yes or no.
what i did :
find mex of complete array = mex_complete now find the first index, say ind from left till which the mex is equal to mex_complete now you have two arrays from index 1 to ind and ind+1 to n; check if the second array's mex is equal to mex_complete. if no then -1 else print the indexes of above two arrays.
Though I wasn't able to solve the same during the contest as I couldn't implement it well :(
D is basically math where you can solve in O(1) memory limit.
The key equation is: (c+1)(c+2)/2 — each pair that will kill a number + pairs that kill two numbers.
To calculate each pair that will kill a number, you find the pairs you can put to its left + the difference between that number and c.
x-y and x+y will be either both even or both odds, so to find the number of pairs that kill two numbers, record the number of even and odd numbers and the calculate the pair combinations of each: ans+=(ll)((even-1)*(even)/2); ans+=(ll)((odd-1)*(odd)/2);
The overall math would be this ten line code 249815852
Can C be solved with greedy?
This may sound like an excuse, but I spent much time trying to login to facebook
me2 lol
Damn I got pranked hard by C xd
Can someone explain why n^2logn solution fails for C for the given submission? https://codeforces.net/contest/1935/submission/249797192
C > D
D is some high school mathematics and I worked it out within 10min after a lengthy, failed debugging session on C. Yes, I did read C and D at the same time. The reason why I didn't try D earlier was that I got an idea for C that works in O(n^2) but is very implementation-heavy, and eventually I did not get C.
EDIT: Just realised that the pi's are not necessarily in increasing order :|
Also I'm posting my WA2 submission for C here. I'll appreciate it if anyone would read through my code and give me a simple counter case:
249821298
Idea: sort messages by a (in a[n]) and b (in b[n]). Iterate over the lower bound of b(b[i]): { Iterate over the higher bound of b(b[j]). Add the bounding elements to sum and greedily choose elements with the lowest a (a[k]) which is within the bounds. If vis[x]=1, a[x] is not strictly inside the bounds; if sel[x]=1, a[x] has been selected. K is not reset because the choices will remain optimal for each j. } Finally check if the answer is 1 or 0.
I think this should work within O(n^2) and should be optimal.
From the statement: "Note that the time to read a set of messages consisting of one message with number $$$p_1$$$ is equal to $$$a_{p_1}$$$."
if(a[i].val.first < l)
→if(a[i].val.first <= l)
WHAT A STUPID MISTAKEhigh school??? kindergarten mathematics.
kindergarten??? my newborn cousin solved it with ease.
In problem F, how do you create a valid set of edges in the $$$cost = (degree - 1)$$$ case?
The $$$cost = degree$$$ case seems much easier since for each [min_node, max_node] subtree range you can just sort the ranges in increasing order of min and then for each range except the first add an edge from [min_node — 1, min_node] ([min_node — 2, min_node] for the edge over $$$v$$$) to produce a valid tree.
I manage to solve these cases with $$$O(n)$$$ constructive method.
The case with no subtree ranges $$$[min_{node}, max_{node}]$$$ that $$$min_{node} < v < max_{node}$$$ is simple, otherwise denote the maximum value of $$$max_{node}$$$ from such ranges by $$$MAX_{node}$$$.
Then for each rage $$$[min_{node}, max_{node}]$$$ with $$$min_{node} < v$$$, add the edge $$$(min_{node} -1, min_{node})$$$ if possible. And for each range with $$$min_{node} > v$$$, add the edge $$$(max_{node}, max_{node}+1)$$$ if possible or otherwise add the edge $$$(MAX_{node}, MAX_{node}+1)$$$.
The correctness can by roughly explained. The ranges with $$$min_{node} < v$$$ except for the leftmost one connect to a left one. The ranges with $$$min_{node} > v$$$ connect to a right one, or connect to a range that pass through $$$v$$$. Thus all the ranges head to the leftmost one and the result graph forms a tree.
You can check my submission for more details.
Problem C was harder than D. Spent most of the time in C.(T_T)
Super Fast Editorial!!
D >>> C (°0°)
In C, did we have to find total time needed to read all messages optimally and then remove messages which take maximum time until time is >= l? or is this approach incorrect?
I had trouble solving B even after getting the correct logic.
I thought the array can be divided in 2 parts always if there was an answer. I calculated the MEX of the whole array. Now I divided the array in two parts of size i(left array) and n-i(right array), where 1<i<n . I updated the MEX of the left and right array in each loop and if they were equal printed the indices. Here is my code, can someone help :
I got it. I was wrongly updating my mex value of left array. Thanks :)
nvm idk how to prove shit
You need to try add edges $$$(r, r + 1)$$$ too.
I can't think of a case where my construction would fail. The only place where it would add an edge of the form $$$(r, r + 1)$$$ would be when $$$x$$$ is rightbound for some segment. Could you give me a counter example if you have any offhand, my brain is fried from sleep deprivation atp QAQ
You can read editorial, in which proves why it enough to add $$$(l, l - 1)$$$ and $$$(r, r + 1)$$$ edges
Too hard for C. I get stuck for more than half an hour, then I just solved it using two segment trees.
Update: no need for segment trees, because when you calculate the range from i to j, you only need to take k-st minimum value, no requirement it must contain the ends. (Since if it does not contains the end, all of them will also appear in the smallest range)
I was stuck for 1 hr and solved D in less time.
How did you solved it using segment trees?
I did 2d dp with a lazy segment tree where dp[i][j] = minimum score to take i values and taking index j. I used segtree to query for the min value of dp[i-1][k] where k < j to get the best for dp[i][j]. I needed to update ranges to account for the differences in b values.
I think you should have swapped D and C. Nevertheless, tasks were very interesting
I think latest trend is difficulty of D is less than C in div2. And System testing just after contest. :)
is Div2 start getting harder ?
Div2 stopped being speedforces. Previous few contests were awesome.
Thanks for fast editoral!
Thanks for the contest, enjoyed all the problems.
Me after solving B:
Common in recent contests :
difficulty of D is less than C.
By By Expert
I think D is easier than C problem.
[Deleted]
smh even appeal copied from ChatGPT
Why go to such great lengths to try to convince people you're not a cheater when you clearly are one? Literally, if you put as much effort into practicing and studying as you put into cheating you could actually become good.
"Please look into this matter". I did and lo and behold, you've actually already plagiarized from the same person once before in round 930. This is their solution for problem B: 248943799, and this is yours: 248959942. That time around it was way more obvious as you had the same variable names, and same syntax throughout the code. Are we to believe that this time now it was just a coincidence? lol
his solutions got skipped in 2 contests
why is this round listed as unrated in my profile even though this post says rated? do i need a rating before this contest?
Before delta rating is updated , it always shows unrated in your profile. In fact , it is a real rated round.
You just need to wait for some hours for rating changing this round.
Terrible luck with C and didn't even care to read D which was apparently easier today somehow :( Good Bye positive delta.
strong pretests? lmao. my second question passed on the 5 pretests and i got wrong answer on test 6
very very strong pretests! thanku very much
Good round overall, but problem C was a bit harder than usual (both the idea and implementation)
Great contest! Thank you.
My only comments are
C is harder than D, but the score of C is lower than D.
Maybe I will never become a Candidate Master. :(
It was a great contest. Problem D was a bit easier than C (even had more accepts) which was great because it teaches us to not get stuck on a problem and always remember to read the next ones. (and yes I made that mistake too) Thanks for the effort to make this great contest!
I just made a mislook at D as C and solve it in 10mins lol.
Can anyone please elaborate the solution to Problem:C by using Dynamic Programming ..
DP[i][j] — Minimum time required to choose any subsequences of Messages in [0...i] such that the corresponding length is 'j'..
At the end , the final answer is to find the Maximum length (LEN) for which there exists atleast one 'i' such that it satisfies the inequality : DP[i][LEN] <=l .
At first we sort messages by $$$b$$$ in increasing order.
Let's denote $$$dp[i][j]$$$ — minimum time needed to see $$$j$$$ messages and the last message was $$$i$$$. It can be calculated as $$$dp[i][j] = a[i] + b[i] + min_{p<i}dp[p][j - 1] - b[p]$$$, if $$$j > 1$$$, and $$$dp[i][j] = a[i]$$$ if $$$j = 1$$$. The $$$min_{p<i}dp[p][j - 1]$$$ can be precalculated for each new $$$j$$$ using prefix minimum array.
my submission: https://codeforces.net/contest/1935/submission/249854472
No more contests lined up after this, what am I supposed to do now lol? I knew there were an awful lot of contests in February, March is going to be dry.
I will try to touch some grass this month, and maybe go on a hike.
Great contest though, I had 2 wa's in A because I was using n instead of s.length() in for loop, a force of habit lol.
Great problems. Enjoyed E the most.
people found C harder than D, but I found D much harder.
No upcoming rated contests :-(
If it is kept swapping problem C with problem D, it will eventually increase the ability to solve problems with D difficulty during contest. Thanks for doing that.
Any idea why the problem ratings have not been updated in so long? I still have no idea if the problems I failed to solve were genuinely hard or I am just a noob.
CLIST
Wow damn all i failed to solve were 1700+. Feeling much better now :)
..
I was able to solve only 2 questions and 2nd one being at the end, but i will surely do the 3rd also in the coming contests.
Hello, can someone please identify what is the mistake with my implementation in Problem C? Any help is appreciated.
https://codeforces.net/contest/1935/submission/250036154
You too? Hahaha, it can be easily done by swapping two variables