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, tyr0Whiz, awesomeguy856, 18o3, Sokol080808, Phi-001, milind0110, NovusStellachan, vgoofficial, carnation13, SashaT9, 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 lmaoBribed to promote CodeChef D:

loved the minimise inversions question.

Congrats on doing a problemset for every division!!!

Your contests are great :)

I completely agree with you brother!!!

Solid problemset as a tester

:3

As a tester, satyam343 tyr0Whiz :orz:

Hopefully pupil this time!

samee, good luck!

Same. Just need +2

good luck!

Congrats sum & cry for becoming cf grandwriters ! ( wrote rounds for all divisions)

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

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

CM soon sir...Vipin Orz

I have small question, can we give more rated contest to people below 1899 ?

`Div-2`

is rated for 0 to 2099`div-3`

is rated for 0 to 1599`div-4`

is 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.

GOOOOOOOOOOOOOOOOOOOOOOD LUUUUUUUUUUUUUUUUCK GYUS

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?

cry sum!

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 :)

this time my target 50 plus delta

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.

Cry orz always the best contests.

can you explain why?

All the best!!! -Beijing·China

FINALLY. DIV 3.

GL evbdy !

bro, is the queue infinite?

slow judge

in queue

queueforces

queueforces :(

my d submission is in queue for 17mins now :(

It's my honor to play the main role in problem A! Tks the problem setters!

Counting is Elation!

based

What happened to submission?

Please fix it, as a newbie i can't move to problem D,E without confirmation whether my C is AC/WA. Longer delay will lead to more penalty if get WA.

Should i move to next problem or wait for WA :(

My post contest discussion stream discussing all problems

Love references to Honkai Star Rail LMAOOO.

Dude the D problem is so tough, the constraint is so tough to deal with

E,F,G all had HSR references wow

countforces!

E was FUN!!!!!

But D was ####

opposite for me lol

Cheater top 30

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.

spent an hour to fix it

take 18 minutes to solve "B".

I spent so much time to realize that I forgot to take modulo on E

womp womp

Guys what was it??? a nightmare for me.same here.

Fucking python, my $$$O(n \log n)$$$ with segtree for G fails by TL.

F is an excellent problem, kudos to authors

F feel like an average leetcode problem

Hints for F : Bomb

Solve the problem for $$$k \leq 10^6$$$. You'll realize that the

greedystrategy 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 $$$> 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 $$$< 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

`== mid`

might have some pesky corner cases).truly fascinating

I think Many of them didn't );

SpoilerIn problem D , can we apply binary search on all three dimensions simultaneously ??

What do you mean

I was thinking the search space in a 3D matrix, where dimensions represents value of a,b,c. matrix[i][j][k] represents (i*j + j*k + k*i <= N && i + j + k <= X), And onto this matrix I try to apply BS from all three dimensions to calculate answer.

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.

did it using Binary search you can view my ugly code in submissions

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.com/contest/1996/submission/272741233 Here's fixed version, but I lost 10 minutes because of the slow queue — https://codeforces.com/contest/1996/submission/272756934

Also I tried that for C and it worked — https://codeforces.com/contest/1996/submission/272781207

Same man.

272749737 New line between output for each test case.

WA272764930 Without new line between output for each test case.

ACWHY ???

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

I don't mean to say that I did this extra new line because of the statement. I mean to ask did the output format

requireno new line between outputs and I should have paid attention to that ?edit: Oh okay no penalty is better and nobody can do anything about the queue. Thanks for quick response, orz.

Was e based on a prefix array with maps and time complexity O(n)?

How to E?

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) > \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

I got it, Basically, i was modifying my map for case where L != 1 which were affecting my other queries. I created new vector for that case and it worked. Thanks for the help

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.

is this the solution for Question E

https://pastebin.com/CYYQNq7h

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

upsolving this one is gonna me mad, one of the best contests i stumbled across

Top $$$5$$$ in the official standings are all Vietnamese LOL.

2nd place has 4 skipped contests out of 24 participated. 4th place has 5 skipped contests out of 9 participated. I'm sure it's legit kek.

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

That cost me entire contest.

Losing rating continuously. Should I take brake or any tips

dont take break more than 1 week or less than 3 months.

codeforce was hanging , i solve problem E and i cannot submit it :(:(

I really liked the short statements.

I never do good in this man's contests

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

the problems are very easy

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 :(

Good contest I learn a lot about math and binary search .

can anyone help me findout why it's giving TLE in test 6??272771836

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

Hello, you told me in a private message that the F question is highly overlapping with other people, but because the idea of this question is the same as the skill upgrade question in the 13th Blue Bridge Cup C++ Group C, and I wrote this question, plus I learned someone else's code at the time, it is very likely that the code will overlap significantly. I hope you'll be able to keep my code from being skipped. Here's the address of the topic:https://www.acwing.com/problem/content/description/4659/ Wait for your message！

I guess these people need to rework on their website

It taking too long to test my solutions

My questions were in queue literally for 2.5hrs

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

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