Hewwo Cowodeforcers!
sum and I are overjoyed to welcome you to participate in Codeforces Round 962 (Div. 3) on Jul/26/2024 17:35 (Moscow time). This contest is the last stop on our mission to problemset for every division. We hope you've been enjoying our stuff so far!
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.
You will be given 7 problems and 2 hours and 15 minutes to solve them.
Note that the penalty for each wrong submission in this round is 10 minutes.
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 point of 1900 or higher in the rating.
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.
We would like to orz the following individuals for making the contest possible:
Vladosiya for the quality coordination.
Benq and satyam343 for overseeing the creation of this contest.
Yam, omeganot, TyroWhizz, awesomeguy856, 18o3, Sokol080808, Phi-001, milind0110, trash-can, Proof_by_QED, carnation13, JuicyGrape, Pa_sha, Qualified, Prady, ntarsis30, waidenf, Non-origination, Orange905, AceKnight7, ETL for testing the contest and providing valuable feedback.
Thank you for reading and we hope you have a fun and educational interstellar adventure :3
Heyo, for those who are reading this, I highly recommend you to participate in Codechef Starters 144. Even though I was never a big fan of CodeChef contests, I watched satyam343 pour his heart, sweat, soul and tears into the contest. Even if you don't usually do CodeChef, you should totally make an exception just this once!
My planned post contest discussion stream for CodeChef Starters 144
My planned post contest discussion stream for this contest
I watched satyam343 pour his heart, sweat, soul and tears into the contest. Thank god you didn't go any further lmao
Bribed to promote CodeChef D:
loved the minimise inversions question.
Congrats on doing a problemset for every division!!!
Your contests are great :)
Solid problemset as a tester
:3
As a tester, satyam343 TyroWhizz :orz:
Hopefully pupil this time!
samee, good luck!
Same. Just need +2
Another cry 's contest! I am glad to be a participant!
potato
hoping to have loads fun participating. The first div 3 that is not rated for me)
Wishing to become a specialist this time
Same. Let's get it
As an out-of-competition participant, I wish I was tester.
18o3 Orz.
18o3 orz
cry and sum contest are the best!!Always enjoyed their problems.
where is 74TrAkToR ?
Hoping to rise from the trauma of last div2.
lol :) wishing you BLUE.
Dil Mange More
I have small question, can we give more rated contest to people below 1899 ?
Div-2is rated for 0 to 2099div-3is rated for 0 to 1599div-4is rated for 0 to 1399technically, purple and violet can take part in same number of contest. I guess there is a small room for improvement in rated contests distributions.
What rank is violet?
Grey, Green, Cyan, Violet, Purple, Yellow, Orange, Red, Maroon.
But violet != blue, it's a shade of purple
ok you are right.
yeah, maybe they can make all contests rated for everyone such that the high rank holders don't affect the new comers that much.
so for every rating distribution there should be different division?
ok you are right.
Hoping to reach pupil this contest. Been practicing quite a few amount of hard problems for me. Hoping to not mess up like a dumb ass. Ideone f ed me up and leaked my solutions :(
As a participant, I want +ve delta :/
hope i dont bottle to get +8 :)
Hope for the best u will definitely reach specialist tomorrow all the best :)
Thanks! Same to you :)
why writers of this contest ain't listed
1"
First contest as a pupil let's go :)
Last div 2 was my first contest at pupil. I hope to become a pupil again
hope back to expert:)
This contest is the last stop on our mission to problemset for every division. Does this mean they sum and cry won't be writing more Div3s (Ó╭╮Ò)
Sorry to say that Bangladeshi can't participate due to network issue in Bangladesh.
Hehe haven't you seen Iran?
cowodeforces ?
Div 3 — crowdforces
Finally, a div 3 round :)
Why are Div 3 contests so rare?
i want to be tester
I've always wondered... Will there ever be a Div 3 round where it's not extended ICPC style? Not that I don't like the current format, but it would be very interesting...
There's one if I recall. It's a Div 3, 2, 1 done simultaneously.
Please give some easy and good questions :)
Inshallah going to be expert today
+1，I hope I can go back Expert again!!!
Same here, All the best, Edit: got some urgent work can't give today :(
As a tester, I can confirm that the problems are high quality, and this is probably one of the best Div-3s I've ever seen. I highly recommend participation.
All the best!!! -Beijing·China
FINALLY. DIV 3.
GL evbdy !
bro, is the queue infinite?
slow judge
in queue
queueforces
queueforces :(
It's my honor to play the main role in problem A! Tks the problem setters!
Counting is Elation!
based
My post contest discussion stream discussing all problems
Love references to Honkai Star Rail LMAOOO.
E,F,G all had HSR references wow
E was FUN!!!!!
But D was ####
opposite for me lol
queueforces
Is $$$O(n \sqrt n)$$$ not intended to pass in G? Or are my data structure implementation skills just trash? I had to do a ton of optimization to get it to pass.
nope
What have you wrote for $$$O(n \sqrt n)$$$ lol, why not $$$O(n \log(n))$$$
Honestly, I have no clue how to solve it with a segtree. I can't really do anything with a segtree beyond copy paste a template for standard point / range addition / assignment with point / range queries.
So I just implemented the obvious sqrt decomposition idea of dividing the array of "number of segments covering the $$$i$$$-th edge" into blocks of size $$$\sqrt{n}$$$ and store the minimum value and its count for a block.
For an update that covers an entire block, the minimum of all elements is updated by the same value, so we can store this value in a separate integer in $$$O(1)$$$ time. For the starting / ending blocks just update the specific elements recalculate the minimum. So an update takes $$$O(\sqrt n)$$$ in total.
Then you can just calculate the number of uncovered edges by adding the number of min elements for each block that has a minimum (including the block additions integer) value of $$$0$$$ in $$$O(\sqrt{N}$$$ time. Turns out this has a slower constant factor than the updates for some reason, so you can just calculate the relative effect during the update and store it in a integer which can be queried here in $$$O(1)$$$ time to squeeze it into time limit.
Mindblowing, 2200+ guy doesn't know segtree but knows sqrt decomposition.
Btw, segtree and sqrt-decomposition are basically the same structure: they're B-trees with branching factors of $$$2$$$ and $$$O(\sqrt n)$$$ respectively. So idea is the same, just different implementations.
the segtree used here to maintain query (min, frequency of min) and range add is the same as the one used to solve area of union of rectangle, which is a quite standard problem?
Well now that the round is over... This was very sad.... TLE everywhere (and one MLE)... I couldn't get C to not TLE on case 6, and F I couldn't get past test case 4... Today felt like SegmentTrees and prefix sums, but clearly I'm just trash...
if you're thinking segment tree for a div 3 C, you're too far gone brother.
try some div4 contests or "easy problems". sometimes i feel like that with many complex topics it's harder to solve easy problems because i think of complex approaches
Yeah I think you are right, I need to fill in those gaps to think of simpler approaches. The editorial made me realize how I quickly jumped to more complex solutions too quickly (though I do think my approach may have passed with c++)... Thanks for the feedback.
Anyone else had trouble taking inputs as numbers in B? Had to take each line in the matrix as a string.
I spent so much time to realize that I forgot to take modulo on E
womp womp
Fucking python, my $$$O(n \log n)$$$ with segtree for G fails by TL.
F is an excellent problem, kudos to authors
Hints for F : Bomb
Solve the problem for $$$k \leq 10^6$$$. You'll realize that the greedy strategy of picking the largest $$$a[i]$$$ is correct. However, this greedy must be applied in a simulation, because the largest element will change at each step.
Split each $$$a[i]$$$ into multiple elements, with values $$$a[i]$$$, $$$a[i] - b[i]$$$, $$$a[i] - 2b[i]$$$, etc. This is an Arithmetic Progression, so we won't store these values explicitly.
If you consider a number line as $$$[0, 10^9]$$$ (where each point denotes a term of the arithmetic progression , it's clear that you will always take a suffix). Therefore, you can do a Binary Search on Answer.
Assume that the smallest element that you picked is $$$ \gt mid$$$. Then, for each $$$a[i]$$$, you can compute how many terms will it contribute to the answer, and what is the sum that it would contribute to the answer. If the count is $$$ \lt k$$$, you update the result, and look in $$$[low, mid - 1]$$$. Else, you look in $$$[mid + 1, high]$$$. Keep in the mind that you don't necessarily need to take all terms
== mid.It's very interesting how CF ratings have evolved. When I set exactly this problem 10 years ago, a lot of purples couldn't solve it. Today 300 Div 3 guys did it and a grey guy writes an editorial.
Haha, true (although arguably my true rating is around specialist, but I don't participate in contests these days).
The binary search idea was immediately obvious to me, but didn't have the courage to implement it (I thought the values
== midmight have some pesky corner cases).truly fascinating
In problem D , can we apply binary search on all three dimensions simultaneously ??
What do you mean
I did BS on c my sol
Hey everyone, how did you approach problem 1996C - Sort? I initially had an O(nq) solution which was too slow, and ended up using prefix sums for an O(q) solution. I'm wondering what other approaches I could have taken, as my code was quite long so I wanted to know if there was an easier way of approaching the problem.
Using prefix sum is correct, nothing fancy.
are you telling me that creating prefix array for all 26 character is the right approach 272782023.
Yes, in fact that is the only way in my opinion.
I desperately submit problem D in last 5 min thought it was gonna TLE but accepted. Feels very lucky tbh
Easiest solution for E — 272838782
Liar, mine's easier:
doesn't judge ignore '\n' symbols between answers for every test in test case?
Here's my "wrong" solution for B — https://codeforces.me/contest/1996/submission/272741233 Here's fixed version, but I lost 10 minutes because of the slow queue — https://codeforces.me/contest/1996/submission/272756934
Also I tried that for C and it worked — https://codeforces.me/contest/1996/submission/272781207
Same man.
272749737 New line between output for each test case. WA
272764930 Without new line between output for each test case. AC
WHY ???
Last line of statement says : "output ... on a new line."
Is that why I get WA for this.
Will I get 10 mins of penalty plus 10 mins of waiting time in queue to get the WA in the first place for this reason which I am not sure is even a mistake ?
sum
cry
(Apologies for pinging)
it means output on a new line, not output a new line between each test case
Also it fails samples, so no penalty
Nice contest, thanks to the authors. Can't believe I couldn't AK today :\
I was unable to submit it went into a continuous loop of cloudfare verifying you as a human
How to solve problem G?
Remove one edge -> every path between two friends is unique -> add 1 for all edges in the path for every pair of friends. Maintain segtree over the resulting array for minimum and its quantity and support addition on segment. $$$O(n \log n)$$$
Supposed that we fixed a certain road. Then, between each pair of friends, there is exactly one path which does not contain that road, and say we choose that path. We shall iterate over all roads and for each road and for each pair of friends, we choose the unique path which does not contain that road, and find the total number of roads used. To find the total number of roads used, we use a range update segment tree. In each segment tree node, we keep track of the minimum value in that sub tree as well as the number of occurrences. See my solution.
For any edge between $$$a$$$ and $$$b$$$ there are exactly two possible paths:
Path $$$1$$$: $$$a \rightarrow a + 1 \rightarrow \cdots b$$$
Path $$$2$$$: $$$a \rightarrow a - 1 \rightarrow \cdots \rightarrow 1 \rightarrow n \rightarrow \cdots b$$$
Notice that deciding to delete an edge $$$i$$$ excludes exactly 1 of these paths, i.e., all edges covered by the other path cannot be deleted.
Let edge $$$i$$$ be the edge between nodes $$$i$$$ and $$$i + 1$$$ (or $$$1$$$ for $$$i = n$$$). Then the optimal path between $$$a$$$ and $$$b$$$ if edge $$$i$$$ is deleted will be:
For $$$1 \leq i \lt a$$$, the ideal path will be Path $$$1$$$
For $$$a \leq i \lt b$$$, the ideal path will be Path $$$2$$$
For $$$b \leq i \leq n$$$, the ideal path will be Path $$$1$$$
So if we iterate on the edge to delete in increasing order of $$$i$$$, the total number of edges "switches" required is only $$$2n$$$.
So if we have a data structure that can:
Perform range updates to increase or decrease the number of covering segments for a range $$$[l, r]$$$ in $$$O(x)$$$ time.
Identify the number of edges that are not covered by any segment in $$$O(y)$$$ time.
Then we can solve this problem in $$$O(n \cdot (x + y))$$$
One such way to do this is using sqrt decomposition which allows $$$x = O(\sqrt{n})$$$ and $$$y = O(\sqrt{n})$$$ / $$$O(1)$$$ depending on implementation.
It is also apparently possible to do this with a segtree in $$$x = O(\log{n})$$$ and $$$y = O(\log{n})$$$
Ough, I thought the solution is smarter than this
.
I hate when testers lie
a lot of cheating going on in D and E i believe
Hello, for problem 1996D - Fun, how did you guys manage to optimize it? I only had time to find a mathematical formulation of the problem, resulting in the following python code:
I can mathematically deduce the result of min(x-a-b, math.floor((n-a*b)/(a+b))), the issue is that if the result is the latter i don't know how to optimize summing those values.
$$$a,b,c\leq{\sqrt{n}}$$$
It is possible that $$$\max(a, b, c) \gt \sqrt{n}$$$. The minimum two of $$$a, b, c$$$ are less than $$$\sqrt{n}$$$.
Oh yeah actually thats right I am lucky I implemented correct solution.
The trick is you #print(a, b, (n-a*b)//(a+b), x-a-b) on the first brute force. Then realize (n-ab) // (a+b) >= 1. Then solve the equation
Here's my python code:
272847061
How did you calculate the range for b? Specifically the (n-a)//(a+1)+1 part
I kinda brute force the b first (run from 1 to x-a). Print the (n-a*b)//(a+b), x-a-b. And see the redundant part (when n-a*b//(a+b) = 0, the for loop should just be stopped).
Then we can assume n-a*b >= a + b. Then b+a*b <= n-a. Then b <= (n-a)/(a+1)
272848365 why my code wasn't working for problem c?
according to your code
if $$$l$$$ in the query isn't 1, then you will change the range answer
[1 ,.., R]to[L ,.., R]so then when I will ask you to get me the answer of[1 ,.., R]your code will give me the answe of[L ,.., R]which is wrongIf L is 1, then their is if block which gives answer for 1 To R
this test case
the right answer is
but your code output is
How to solve E
Don't try to count number of pairs $$$(x,y)$$$ for every $$$(l,r)$$$.
Instead, for every pair $$$(x,y)$$$ try to count the number of possible pairs $$$(l,r)$$$.
No hacking phase? edit : Oh, it just started.
please open upsolving
There seems to be one stuck submission: 272840297
This needs to be addressed before we can upsolve or start hacking.
one day the earth will be not suitable for living, because temperature is increasing and people are greedily using resources. So why people fight for short term materialistic contest?
how this is TLE on problem E
Consider test case
10101010101...01010, then your time complexity becomes quadratic because there are O(n) occurrences of the diffs 1 and 0.when the string is like this
0101010101.., then your code will have $$$O(n^2)$$$ time complexityIn queue
Top $$$5$$$ in the official standings are all Vietnamese LOL.
Countingforces
First contest in almost 3 years. And the quality of problems is as good as ever!
So many cheaters lmfao, for problem D(maybe more), I can see lots of similar 3 liner submissions !!! Doesn't Codeforces have plagiarism check?
The code for problem D is literally that simple, so solutions with the same code is expected I guess, especially with this large amount of participants (I don't deny that there are cheaters though)
please hack my solution of Problem D : )
Really liked the idea of Problem F. Kudos to the authors.
Only I tried to solve the $$$G$$$ problem randomized?(Note that if we do not take an edge $$$(x, x + 1)$$$ in the answer) then all others are recovered unambiguously. 272831028
Look at jiangly's solution.
Screencast with commentary
Problem C was nice I was dumb that carry map of map instead of vector of vector :(
Almost fall for the same trap. I feel u
codeforce was hanging , i solve problem E and i cannot submit it :(:(
I really liked the short statements.
Note that the penalty for each wrong submission in this round is 25 minutes.(15 min in queue)
hope to become green
Hey. So this was my first contest on Codeforces and I dont know how this works but I assume I am an unrated player. I thought that this round was Rated for me and I managed to solve 5 out 7 questions. Now the contest shows in my Contests section as Unrated. What is the issue? Why was it Unrated for me?
Ratings will be updated soon
Oh so till the Ratings get updated, the contest will stay in the Unrated Section? Thanks for the reply.
just went through your code. Seems like your question 5 solution is copied.Its gonna get hacked after system testing since the code you got had a bug put in there by really smart people to catch idiots like you. Next time use your own brain to solve the problem.
The fact that smart people are publishing solutions is scary
why is it scary. Its good to set traps for these rats.
That’s actually really smart though
RANT!!! Looking at the number of submissions in C, D and E, it was clearly evident that a lot of cheating took place the last contest. The endless waiting queue just made it worse. Needed just a +2 to get back to pupil... and here I am, standing terribly low at the standings!
For god's sake, it's high time that strict measures are implemented to just ban these people from the platform. Been doing CP for quite some time now, and cheating has never been this great a concern. It gets very demotivating to see your ratings going down inspite of you trying your level best to keep up :(
seriously, i got 1599.
Plag check can make it.
hope so
Good contest!
I can prove that I have encountered almost the same question as Question F before. This question is Question 9 "Skill Upgrade" of the C++ Group of the 13th Lanqiao Cup in 2022 in China, and I have seen the solution to this question before.I hope you can change your judgement of my code.Please reply to me within two days.
This is the link to that question.
https://blog.csdn.net/m0_62609939/article/details/128653128
My solution is 272848252 for the problem 1996F
Hi, in the contest "Codeforces Round 962 (Div. 3)", my solution 272814471 for the problem 1996F significantly coincides with others, but this solution was written by me in https://www.acwing.com/activity/content/code/content/7949410/ on March 5th, 2024, in other words, this is my own code, so I didn't break rules, I sincerely hope that my solutions in this contest won't be skipped.
Problem F is similar to https://www.acwing.com/problem/content/4659/
Hello,my solution has been skipped,due to the problem 1996F coincides,The problem 1996FIt is an original question from a competition called Blue Bridge Cup(lanqiao) for Chinese university students two years ago, only the data range is different.Here is the link to the original question for this question,which came from the 2022 Provincial Contest in C++ category Group C:https://www.lanqiao.cn/problems/2129/learning/?page=2&first_category_id=1&second_category_id=3&tags=2022 I have participated in this game, it is relatively high in China, I found that after I sloved this question, I just will be just the solution of this question to modify the input format and data range will be passed this question, this is the link to the solution of the problem!:https://www.acwing.com/solution/content/160566/ The date is 2023.01.06; I hope you can restore my submission and ranking
The E question is almost exactly the same as the "skill upgrade" of the 13th Provincial Competition of the 2022 Blue Bridge Cup, and I have done this question before and memorized the answers in the solution, but I said that I checked the duplicate with other codes, but I don't know those people at all
1996F - Bomb
The F question is almost exactly the same as the "skill upgrade" of the 13th Provincial Competition of the 2022 Blue Bridge Cup, and I have done this question before and memorized the answers in the solution, but I said that I checked the duplicate with other codes, but I don't know those people at all
Heyo,my F question has been skipped,but I didn't plagiarize the code.I once wrote a similar question,Here is a link to this question:https://www.acwing.com/problem/content/description/4659/ .I've learned the solutions in it so I write the F by this solutions.Here is a link to the solution:https://cdn.acwing.com/solution/content/231750/ .I hope you can re-adjudicate the verdict,thank you! 1996F - Bomb
1996F - Bomb