Hello Codeforces!

I am happy to invite you to Codeforces Round 860 (Div. 2), which will be held on Mar/26/2023 17:35 (Moscow time).

This round will be **rated for participants with rating lower than 2100**. Participants with a higher rating are invited to participate in the round unofficially.

You will be given **6 problems** and **120 minutes** to solve them. All problems were authored and prepared by me.

The traditional thanks-list to everyone who took part in the creation of the round:

🤴 DishonoredRighteous for coordinating the round

🐞 gyh20 for black-red testing of the round

😈 feecIe6418, iakovlev.zakhar, Dart-Xeyter, Adam_GS, felys, golikovnik, Gary2005 for red testing of the round

🐫 NemanjaSo2005, Alexdat2000, Kon567889, tem_shett for orange testing of the round

👾 SlavicG, Psychotic_D for purple testing of the round

🐳 C2A, Masha237, ayhan23, Dhru008, Brahma_tet for blue testing of the round

👽 Lord_David for green testing of the round

🦄 mejiamejia for help with testers for the round

🤡 sevlll777 for the problem, without which the round would be unbalanced, and the problems that were not included in the final problemset

🎅 MikeMirzayanov for the amazing **Codeforces** and **Polygon** platforms

ㅤㅤㅤㅤ

**Personal recommendations**

I sincerely hope that you will find the problems interesting and you will enjoy solving them. Good luck!

Score Distribution:

**500 — 750 — 1250 — 1750 — 2250 — 3000**

**UPD**: Editorial

**UPD2**: Congrats CHAMPIONS!

Unofficially:

Officially:

First AC:

A: nifek

B: happy.potato

C: happy.potato

D: aryan12

E: aibark

F: zihouzhong

As a tester, I recommend you try every problem.

PS: sevlll777 tried a lot to make a good round for you guys.

Score distributing looks interesting, I'll target 4 problems then if we r lucky enough to get math problem on D kekw :)

Can you explain what the score distributing means? Thank you

Read Codeforces Contests rules

Thank you!

As a participant, I want to thank you for the contest!

It isn't at the main page after 7 hours, wow...

As a tester, I'm a little surprised :)

Cyan tester?

Error 404 not foundI honestly think these emojis are annoying and make the announcement hard to read.

Sounds like a bad round in advance.

After my own participation in this contest, I found your statement wrong.

1750 problems are rather rare these days.

Kudos to authors for having them

You know what it means right !!!!!!. It's now time to solve four questions this time. Hahaha

interesting, i've personally never paid attention to the score distribution, looks like it's time to change that.

Red round

I have one rating point left to raise to Specialist, I sincerely hope that I will raise it this round.

I was at that once. You can do it!

Do not think about it during contest. I repeat don't. Just solve problems with accuracy. It's ez.

Been there done that :)

If you solve first 2 question as fast as possible, u wont get negative delta for sure even if u sit idle during rest of the time. All the best for Specialist buddy :)

Since this round is rated for only participants below

2100, I don't see why legendary grandmasters are required for testing.Legendary grandmasters have more experience than anyone else. They will probably be much better at pointing out things like if a problem has appeared before, if there exists a stupid data structure brute force, if the authors' intended greedy is incorrect and the problem is actually unsolvable, etc.

orz writers!

Hopefully my CM contest

I followed the author long time ago because his codes are brilliant and clean so I'm expecting some great problems tomorrow < 3

orz

This amount of emojis makes me die inside

Emoji round

How can one become a tester?

By testing Problems !

Why didn't I think of that!

I am eagerly waiting for this contest...I think I will reach PUPIL by this contest....Let's Hope for the best....I will definitely never give up even I cant make my name green....

That's the spirit dude

Thank You Bro.....CP is one sitting for contest before 30 minutes....

Congrats on the green!

Thank you so much bro

Best of luck everyone!

Early Score Distribution!

Sir you graph is so inspiring.

so glad that it inspired someone <3

As a blue tester, best contest I have ever seen!

not untrue

On the behalf of the specialist community i would like to say this time D is 1750. And you lot know what it means right!!

Transition to Expert Round? o.O

springroll

As this is my first testing round, I'd like to thank sevlll777 for giving me this opportunity. It was a lot of fun for me.

In

div2contest!me BEFORE CONTESTme AFTER CONTEST is over!emojis <3

Wishing all the best to everyone,

Participants with a higher rating are invited to participate in the round unofficialy.

Should be:

Participants with a higher rating are invited to participate in the round

unofficially.Update:Fixed.

⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⣀⣀⣀⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⣴⣞⠉⠉⠀⠀⠀⠀⠀⠀⠀⠈⠉⢑⣶⣤⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣶⣾⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⣿⣿⣿⣿⣿⣶⣤⣀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢀⣤⣴⣤⣤⣤⣤⣤⣤⣤⣤⣤⣴⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣥⣤⣤⣤⣤⣤⣤⣤⣤⣤⣤⣽⣿⣿⣿⣿⣿⣿⣿⣿⣷⣦⣤⣤⣤⣤⣤⣤⣤⣤⣤⣤⣤⣤⣄ ⠈⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋ ⠀⠀⠀⢹⣿⣿⣿⠛⠛⠛⠛⠛⠛⠛⢛⣛⣻⣟⣛⠛⠛⠛⠛⠛⠛⠛⢻⣿⣿⣿⣿⡟⠛⠛⠛⠛⠛⠛⠛⢛⣛⣿⣛⣛⠛⠛⠛⠛⠛⠛⠛⠛⣿⣿⣿⡏⠀⠀ ⠀⠀⠀⢘⣿⣿⣿⡀⠀⣠⠋⠉⣣⠾⣿⣿⣿⣿⣿⡟⠢⡀⠀⠀⠀⠀⣼⣿⣿⣿⣿⣿⠀⠀⠀⢠⠊⡩⢿⣿⣿⡀⠀⠀⠙⢦⡀⠀⠂⠀⠀⢸⣿⣿⣿⠀⠀⠀ ⠀⠀⠀⠀⢿⣿⣿⡇⠀⣇⠀⢰⣹⢁⣿⣿⣿⣿⣿⣿⣀⢹⠀⠀⠀⢠⣿⣿⣿⣿⣿⣿⣇⠀⠀⣇⡼⠁⣸⣿⣿⣷⣥⣀⠀⠀⢱⠀⠀⠀⠀⣾⣿⣿⡇⠀⠀⠀ ⠀⠀⠀⠀⢸⣿⣿⣷⠀⠈⠒⢺⣧⣼⣿⣿⣿⣿⣿⣿⣿⣿⠇⠀⠀⣼⣿⣿⣿⣿⣿⣿⣿⡀⠀⠈⣷⣿⣿⣿⣿⣿⣿⣿⣆⠀⢸⠀⠀⠀⢀⣿⣿⣿⠆⠀⠀⠀ ⠀⠀⠀⠀⠈⣿⣿⣿⣔⠀⠀⠘⢿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠀⠀⢠⣿⣿⣿⣿⣿⣿⣿⣿⣧⠀⠀⠙⣿⣿⣿⣿⣿⣿⣿⣿⣧⠏⠀⠀⠀⣼⣿⣿⡿⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⢹⣿⣿⣿⣦⡠⠀⠀⠛⢿⣿⣿⣿⣿⡿⠋⠀⠀⣠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡀⠁⠘⢿⣿⣿⣿⣿⣿⠟⠁⠀⠀⢀⣼⣿⣿⡿⠃⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠙⣿⣿⣿⣿⣶⣤⣤⣤⣬⣽⣽⣁⣠⣦⣴⣾⣿⣿⣿⣿⣏⢉⣭⣽⣿⣿⣿⣿⣿⣶⣤⣤⣈⣩⣭⣭⣥⣤⣤⣴⣾⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⡏⠙⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣼⡏⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢿⠇⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⢇⠀⠀⠀⣭⡙⠛⠛⠛⠛⠛⠛⠛⠛⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⠛⠛⠛⠛⠛⠛⢛⣟⠛⠉⠁⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⢸⡀⠀⠀⠙⠁⠀⠀⠀⠸⣿⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣶⠀⠀⡸⠿⠀⠀⠀⠀⡏⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⢧⠀⠀⠀⣤⡀⠀⠀⠀⠈⠀⠀⠀⢀⣴⣦⣤⠤⠤⠤⠤⠤⠤⠤⢤⣤⣶⣤⡀⠀⠀⠘⠋⠀⠀⠀⠀⠀⠀⠀⣸⠁⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠈⢇⠀⠐⠙⠃⠀⠀⠀⠀⠀⠀⠀⢻⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⢹⣿⣿⡧⠀⠀⠀⠀⠀⠀⢠⡄⠀⠀⣰⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠙⣇⠀⠀⠀⠀⠀⠀⠀⠀⣼⠋⠉⠀⠀⠀⠀⠀⠀⠀⠉⠀⠀⣰⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠋⠳⠶⠶⠶⠖⠒⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡜⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠳⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⠔⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠲⢤⣠⣀⣀⡀⠀⠀⣀⣠⡀⠀⡀⢀⡀⢀⣀⣦⣤⡾⠟⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣾⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡖⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠛⠻⠿⠿⠿⣿⣿⣿⣿⣿⣿⣿⠿⠿⠿⠛⠋⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀

Hope to earn some positive delta!

Hope to solve A & B.

Good luck Everyone!Hope I'll turn CM soon :(

Thank you for creating this amazing contest for us. I hope that my rating will improve, because I'm awful at coding. Apart from that, good luck everyone!

Leetcode went down today during the Weekly Contest. All in on codeforces now

As a tester. This is an actually good round. Try every problem.

Would it be an AI themed contest? sevlll777

Like Codeforces Round 770 (Div. 2)

No, this contest has no theme

Specialist day, I hope

hope rating++

NEW ICONS!!! Oh, wait....

When I am trying to login via my main account it says user is disabled by administrator? What does it mean? Is it a ban and if yes for how long or is it a bug? Like my main account wasn't being plagiarized too in recent rounds? Please do help.

Please someone do help .I even registered from that account around 20 hours ago .Please help

Please do look into the matter please MikeMirzayanov I have also sent you a personal message regarding this matter please do give it a read please

What's your main @?

I think, C problem 3rd test case output is wrong. pack 1 and pack 5 can have same price tag.

Yeah I also initially misunderstood the question wrong so that you can change the order of the candy types. Fortunately they then clarified.

Price tags can only cover adjacent equal values. 1 and 5 are not adjacent.

Even in the example the values reached are [4,4,2,4,4] and the answer is 3 not 2

Swap(C,D)

I literally took 3mins to solve D after reading it , & couldn't solve C , lol.

Opposite, couldn't solve D but got the idea for C fairly quickly

We should form a team. xD

does this things common for you like you are habitutaed with this kinda problem and implementation which helps you to solve it within 3 min?

D<<<C

yesss!!

Who else facepalmed when they saw the announcement reminding the condition that the price tags have to be continuous?

Yeah I read it 10 minutes before the end of the contest :|

i saw it after the contest end :(

will read all the samples from now.

Ok, I obviously don't get it:)

What so obvious easy was about C and D?

c is just gcd and lcm on continous segments. D is kadanes

My brute force solution passed the pretest of E. Weak pretest. Hope it will get FST.

Update: My solution passed system test. Weak system test. I'll uphack my solution later.

Mine too, but it's passed

Anyone else thought that you can change the order of types of candies on the shelf? I wasted too much time on that :(

yeah, I initially thought so too, but I reread and they specifically had [4, 4, 2, 4, 4] example.

Should've read the example tests carefully.

Yes and the given constraints made the problem impossible to solve if you can change the order.

Yes, I thought so too, but then the announcement help me to understand!

same here,but I didn't read announcement or examples :)

So how to solve problem D?

Construction is so hard. :(

Just greedy in a somewhat stupid way. It is easy to find this way but it is not instantly obvious why it works.

It is my greedy... But wrong at pretest 2...

Sorry, I did not read your code but my solution was:

First, split array to

`pos`

and`neg`

. Also calculate number of zeros.Then this greedy

Input can be all zeros.

oh yes, sorry, also check if is there any non-zero elements first. But I think if you don't do it you will get WA on the sample.

Take a look at Ticket 16779 from

CF Stressfor a counter example.Pretty sure it was something about Kadane's algorithm but I got too cought up in c too much

So what is Kadane's algorithm?

Basically a greedy algorithm that lets you find the maximum sum subarray when negative numbers are present. You keep a current score and iterate through the full array while also keeping the max score somewhere. If a number is positive, you take it and add it cause it makes score better. If there is a negative number you have 2 cases. Case one is if the score would be negative then you simply set score to 0 (because taking the number would be worse than having nothing) case 2 is if the score after adding the number would be more than zero, in that case you just add it to the score because it might be worth it later

It gives the maximum sum among all of the subarray from an array.

If every element is equal to zero -> no answer.

Otherwise, group elements in two vectors: positive+zero and negative.

You build the final array as follows: Keep a variable

`sum`

denoting the sum of all elements used up to this point.`if sum > 0`

you append the next negative value to the final array`if sum =< 0`

you append the next positive or zero to the final arrayLargest absolute value of a subarray sum is the largest absolute difference between any two prefix sums. Let

`max`

equal the largest value and let`min`

equal the smallest value of the array. You can notice that if currently`sum > 0`

, the next prefix sum will satisfy`sum > min`

and if currently`sum <= 0`

, the next prefix sum will satisfy`sum <= max`

. This means that all prefix sums satisfy`min < sum <= max`

. The largest possible prefix sum is thus`max`

and the smallest possible is`min + 1`

. The absolute difference of these is less than`max - min`

which satisfies the problem statement.Can u tell what's wrong in my approach: What I am doing is just instead of 0, I am storing max(A) — min(A) into a variable r, then whenever abs(sum of elements + new_element) > r, then start storing elements of opposite sign and so on

The maximum value of prefix sum in your case is going to be r — 1 while the minimum value of prefix sum will be -r + 1.

The difference between both will be greater than r, which means there might be some subarray that will exceed the allowed sum r.

I don't know how you implement it but yeah seems like this will definitely fail.

Thanks all above :)

Was there any specific tricky case in E? I think I had an almost correct solution (with precalculation of how many correct tests we will have starting from position

iusing dp with memoization and maximums on suffix on result of this dp) but I have always got WA 3 :(Take a look at Ticket 16778 from

CF Stressfor a counter example."Shocking Arrangement" is the title of problem D. Yes, indeed.

Did anyone else FST B on test 6?

No.

bruh you took an array of 50,000 elements instead of 50,001. Also it is not advisable to create that big of an array for each test case, instead use maps.

Thanks for pointing out my mistake... that is so embarrassing

Can anyone explain how they quickly proved D? I thought about the correct greedy solution but couldn't prove it.

Copied fom my previous comment:

If every element is equal to zero -> no answer (trivial to prove).

Otherwise, group elements in two vectors: positive+zero and negative.

You build the final array as follows: Keep a variable

`sum`

denoting the sum of all elements used up to this point.`if sum > 0`

you append the next negative value to the final array`if sum =< 0`

you append the next positive or zero to the final arrayLargest absolute value of a subarray sum is the largest absolute difference between any two prefix sums. Let

`max`

equal the largest value and let`min`

equal the smallest value of the array. You can notice that if currently`sum > 0`

, the next prefix sum will satisfy`sum > min`

and if currently`sum <= 0`

, the next prefix sum will satisfy`sum <= max`

. This means that all prefix sums satisfy`min < sum <= max`

. The largest possible prefix sum is thus`max`

and the smallest possible is`min + 1`

. The absolute difference of these is less than`max - min`

which satisfies the problem statement."

if sum > 0 you append the next negative value to the final array"What if next negative value is not available? And then only positive values are there? The sum might cross mx-mn

It is guranteed that the sum of the whole array is 0.

If currently

`sum > 0`

, we know that for the remaining elements`sum < 0`

. This means that theremustbe at least one negative element left.I didn't lol. It just kinda made sense :/

I am not sure if this is the solution for F (didn't implement on time) but it rests on this key claim which I cant really prove or disprove: If I have a class of size k and I have at least 2*k-1 bags, I can always find a knapsack of size k divisible by k.

Suppose this is true, then its always possible and I can just take knapsack from small to big. Can anyone prove or disprove the claim?

This is the Erdos-Ginzburg-Ziv Theorem.

My solution on C 199304839 gets TL7. I have no idea how to speed up it (without writing more optimal solution).

You don't need factorization at all.

I know, but I want to submit this solution.

I think that it's pretty much impossible because the solution would be n*sqrt(1000000000) worst case (each ai is close to 1000000000) and since you have to do modulo it's not possible to push it that far with dirty tricks

Factorization works in

`O(n ^ (1 / 3) * log n)`

Oh, that's my bad for some reason I was thinking about getting the divisors rather than factorization. But, correct me if I'm wrong, let's say you have a perfect square of a prime number isn't the factorization just sqrt(n) then

In my solution I get all divisors. Number of them is

`O(n^(1/3))`

and`log`

from sortingHave to admit, your code is a bit confusing cause I have never seen recusrive factorization before. How exactly does recursive factorization avoid an sqrt(n) worst case?

Wiki

If you are interested, I have solved this problem with factorization + dynamic programming during the contest.

My fresh 1762 ms submission after the contest

My 2074 ms submission during the contest

Key ideasNice idea, thanks!

Anyone knows why my submission for E is wrong?

https://codeforces.com/contest/1798/submission/199302004

My algorithm:

SpoilerDivide the "multitest" into the "declaration" part of the first number, and the "tests" part from the second number onwards.

Create an array "natural" which for each element, natural[i] = -1 if the subarray from i to n cannot be the "tests" part of a multitest; otherwise, natural[i] = k, where k is the number of tests if the subarray from i to n is the "tests" part of a multitest. This can be calculated in O(n).

Create an array "adapt", which adapt[i] = 1 if the maximum of "natural" array from i + 1 to n is -1; else, adapt[i] = max of the "natural" array from i + 1 to n.

Then, ans[i] = 0 if a[i] = nat[i + 1] ; ans[i] = 1 if nat[i + 1] != -1 or a[i] <= adapt[i]; else ans[i] = 2.

ExplanationThe "natural" array calculates whether a "tests" part of the multitest could start at this location, and if it could, how many tests will the multitest have.

The "adapt" array relies on the assumption that the first element of the first test of the multitest could always cover a specific amount of elements, with the rest of the elements being the "tests" part of the multitest itself. Since adapt[i] can always land on any step from i to n, adapt[i] could range from 1 to max(natural[i] to natural[n]) + 1.

Therefore:

If a[i] is exactly equal to nat[i + 1], a[i] is the start of the multitest already, and we dont need to change anything.

If nat[i + 1] is not -1, we just need to change a[i] to nat[i + 1], and the array is sufficient

If adapt[i + 1] is greater or equal to a[i], we could always redirect a[i + 1] to a position in which the "tests" part contains a[i] test.

If none of the conditions hold, put a[i] to 1 and a[i + 1] to the remaining number of elements will use 2 changes.

Take a look at Ticket 16777 from

CF Stressfor a counter example.Thank you! I missed an edge case.

So big gaps between B and C...

very hard problems

Amazing round! Really cool problems.

Screencast with commentary

what was the proof for problem D ..

depend on your algorithm :)

for "sort pos & |neg|, take pos and when possible take neg such that sum >= 0" consider situation when sum become too big, easy to see that it is impossible, because prev sum is at least (cur_sum — max) which is greater than |min|, therefore we could use min instead of some pos number now

Thanks got it

Why is D in this position?

Problems were really hard. D was easier than C and C was hell of a hard problem (I understand that C was lcm and gcd, but you still had to think how to fit this operations into problem, which was not an easy task).

I did solved C within 30 minutes, D costed me entire time though :(

Exactly totally waste time on thinking on C :<

Great contest, but I personally found D easier than C. Anyone share the same thought?

Yes same here but i waste all of my time thinking about problem C.

A: For 1<=i<=n-1 check for every pair of (a[i], b[i]) if one of the following is true: (a[i]<=a[n] && b[i]<=b[n]) or (b[i]<=a[n] && a[i]<=b[n]), which is equivalent to min(a[i], b[i])<=min(a[n], b[n]) && max(a[i], b[i])<=max(a[n], b[n]).

B: Check participants reversely. We need to maintain a set of participants in the future, and from today's participants we need to find a participant which is not in the set.

C: The equivalent condition of "we can use same price tag for [L, R]" is gcd(a[L]*b[L], a[L+1]*b[L+1], ..., a[R]*b[R]) % lcm(b[L], b[L+1], ..., b[R])==0. Thus we can solve by dp: let i be the minimum index that we can use same price tag for [i, j], we let dp[j]=dp[i-1]+1. We can find such i by binary search, and we need to process range query by some data structures like sparse table.

D: If all of a[i] is zero, there's no solution. Otherwise, we can ignore zeros (since they don't contribute to sum of subarrays and can be placed everywhere) and maintain the current prefix-sum. If sum<=0 we append a positive number to the array, otherwise we append a negative number until we used all numbers. Because the total sum is zero, we always have unused number with the sign we want, and every prefix-sum of the array we build is in the range [-min+1, max].

C can be done with greedy. Just greedily include the next candy in the same group if gcd of all ai*bi is a multiple of lcm of all bi. This can be proven.

I proof by AC-d problem D lol

One of the best contest !

In Problem C, One fine observation can convert Binary Search Solution to Linear Solution.

Hello, may I ask why my D get punished while submitting again after AC

That is how codeforces rules work. The following is taken from here:

If a contestant submits several times a problem's solution that passes all pretests, then the last solution is considered as the contestant's verified solution for this problem. All other solutions will be considered as unsuccessful attempts.

Pain of getting the working solution right after the contest remains constant

Same with me bro . I also devote a lot of time to Problem C but does not able to do so But when I see problem D hardly four to five min remain and I coded the problem but the time was over After the contest when I submit it .It got AC

Why does the pretset data of D not have 3e5 so I got fst?

Why it must?

I think it is necessary to set extreme data on borderline cases in pretest, especially oj with hack mechanism like codeforces

Can someone please help explain why my code doesn't work for C? I spent over an hour debugging but it still doesn't pass the first test case.

https://codeforces.com/contest/1798/submission/199296745

Try dry running your program on this testcase. It's smaller than the sample, and should help you realize what's wrong.

You literally have everything correct except for redefining R inside the loop once again...

Oh wait you're right. Bruh this pisses me off so much, if I just fixed that I could've gotten C an hour in.

D was wayyy easier than C.

I feel dumb for not taking the 2nd suggestion seriously TwTeven after taking this i cant solve

D got FST(RE) because of the weak pretest:(

It is not "weak pretest" if you write #define MAXN 200010, but n can be 300000 :)

I've read the guide for problem setting on CodeForces, and it said every problem should have a pretest with maximum input size.

it is my fault but I would have been corrected if the pretest had contained the boundary case

Problem D has weak pretest (no testcase with maximum input size)

Problem E has weak system test (allow brute force solutions)

How did they tested this contest

B also doesn't have a pretest containing $$$50000$$$.

Yeah, my solution was wrong because I put i<50000 and I didn't catch it because the pretests didn't include 50000. A shitty way to not get AC since it was my only mistake...

Your bruteforce solution of E is non-obvious at all (to come up with). Of course it is my fault and I apologize for this, but it is really unpredictable what kind of solution human brain can come up with.

For D there is no excuse for me, I thought I had it in pretests and not double-checked it, sorry.

satyam343 Orz.

satyam343 Orz

satyam343 Orz

satyam343 Orz

Congratulations for becoming Candidate Master.

Thanks sir :)

satyam343 orz

When should I expect a rating?

Anyone knows why my solution to B is giving TLE?

https://codeforces.com/contest/1798/submission/199298313

From a very quick checkup — you initialize array

`finalAppearence`

of size 50001 for each test case (there might be 50000 of them)I changed something, and now its just improved to TLE in test 4, from previous TLE in test 2.

Submission: https://codeforces.com/contest/1798/submission/199321397

Your time complexity is $$$O(finalAppearence.size)$$$ per test case. finalAppearence has size $$$50000$$$ and there are $$$50000$$$ test cases, so it is giving TLE.

Use map instead. 199258547

Thanks!

I came up with a nlogn solution for D but unfortunately could not prove it. Can anybody please take a look? Feel free to hack if it is wrong. I just want to know whether it is correct.

https://codeforces.com/contest/1798/submission/199291200

How to solve Problem C?? And What could be the rating of Problem D

In Problem B I got AC in contest but now it is showing WA on test case 12

Why?

https://codeforces.com/contest/1798/submission/199291886

it seems to be fine for me

oh so Now I got AC so basically have to used long long sum instead of int sum

but why they didnt show me WA in contest time if this was the issue

my rating now will be highly affected by this

You didn't get WA during contest because your code is only ran on pretests during a contest. This doesn't include all tests that your solution will be run on after contest, so you can only assume that your solution is probably correct.

Why 199309430 this got AC (after the contest) and 199271425 this got TLE(at contest). The difference I made between those two submission is declearing adgacency list of size 2e5(TLE) and 5e4(AC). Then assuming more memory cause TLE instead of MLE??

I solved C with three segment tree and didn't solve D. These turn out that I don't have brain.

what was your approach for C?

First, consider when $$$c_l=c_{l+1}=\cdots = c_{r}$$$. The optimal $$$d$$$ is $$$d_i = \dfrac{\text{lcm}(b_l,b_{l+1},\cdots,b_r)}{b_i}$$$(according to the definition of $$$\text{lcm}$$$). Then if $$$\forall l \le i \le r ,d_i | a_i$$$, it meets the condition. Let $$$l=\text{lcm}(b_l,b_{l+1},\cdots,b_r)$$$. $$$\forall l \le i \le r ,\dfrac{\text{lcm}(b_l,b_{l+1},\cdots,b_r)}{b_i} | a_i \iff \forall l \le i \le r ,\dfrac{l}{b_i} | a_i \iff \forall l \le i \le r ,l | a_i \cdot b_i \iff l | \gcd(a_l \cdot b_l,a_{l+1} \cdot b_{l+1}, \cdots , a_r \cdot b_r)$$$. So we can use two segment trees maintain $$$\text{lcm}(b_l,b_{l+1},\cdots,b_r)$$$ and $$$\gcd(a_l \cdot b_l,a_{l+1} \cdot b_{l+1}, \cdots , a_r \cdot b_r)$$$.

Second, consider how to get the answer. Let $$$dp_i$$$ means the answer of $$$[1,i]$$$. We can use binary search to get the minimum $$$j$$$ that $$$c_j = c_{j+1} = \cdots = c_i$$$. Then $$$dp_i = \min\limits_{k=j}^i dp_{k-1}+1$$$. We can use another segment tree to maintain the minimum $$$dp_i$$$ in a range.

Finally, $$$dp_n$$$ is the answer. (Sorry to my poor English and expression)

This is my code of the solution.

Though C is too hard for it's position, CD are great and E is very beautiful! Thanks for the problemset!

.

✅ Maximize your enjoyment of the contest, not your rating after it

Agree, 100% (delta=-100), absolutely loved C! I guess problems C and D could have been swapped. Although that probably would've given away the solution to the current D, if it were C.

Thanks again for the amazing contest!

https://codeforces.com/contest/1798/submission/199317662

Can someone explain why this solution of c got a runtime error?

i can equal n, array out

satyam343 orz comment. Satyam is a legendary grandmaster in disguise.

He is the women's pet, men's regret and if you bet against him, it is a bad bet.

Good contest! Finally reached specialist

Well at least i solved C alone, although it was after round ended.

Can anyone tell me why in Problem D they said that the sum of all elements is $$$0$$$? The way I proved my solution didn't use this fact at all.

could you please share your idea? I didn't gave much attention to the first line during contest so i failed to come up with a construction, I only know(not sure if true though) that a construction will always exist if abs(sum(all elements)) < max. — min.

https://codeforces.com/blog/entry/114317?#comment-1016677 This is how I solved it

It does rely on the fact that the sum is 0.

If the sum wasn't 0, you could run out of negative elements before positive elements and you would be forced to make the prefix sum

`> max`

where`max`

is the maximum value of the array, which could violate the problem statement.Consider this test case:

But you can just say the answer doesn't exist in that case.

See: 199281458

A great contest,problems are interesting and educational!

it was a great round!

greetings to everyone who worked on this round <3

Finally became specialist... Codeforces Round 860 (Div. 2) was great overall

Great job! Congratulations on your achievement. It's inspiring to see cute and talented individuals excel in competitive programming

Can anyone explain problem C for beginners like me?

Today I got a message of code copying with someone named VRSancheti. I even don't know him/her and our code is also different to a great extent and only logic is same. I had just copied boilerplate from Internet which may have resulted in same code(as he/she might have copied the same boilerplate from Internet). Yet my all questions have been made wrong. I honestly wrote my code on VScode and submitted it. Please look into this matter and take necessary action.

Today I got message

Your solution 199291360 for the problem 1798B significantly coincides with solutions oggy_841/199268655, vaibhav841/199291360. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked. I don't know who he is. It was the simple problem. why would i take code from someone who is newbie knowing I am specialist. I swaer I didn't cheat

My solution of 1798B significantly coincides with other solutions and my ratings of this contest has been reverted back, this was an easy problem and any resemblance to the problem is purely coincidental, I have been using the same boiler plate for long time, Please look into the matter and take necessary action.

I am writing this blog for clarification of this round rating changes.as, my both submission got wrong but, if it matches with any solution, It may be due to same basic concept because in some basic question there is same logic. please check it.

Attention!

Your solution 199293271 for problem 1798B significantly coincides with solutions vanya_07/199293271, SashaBraus/199296381.

according to this message I have submitted earlier. This is surely a coincidence.please look into this matter.

Why my solution is skipped? Not wrong nor right?

If matched then, It should be unrated? then why has been my rating decreased?

Your solution 199301914 for the problem 1798C significantly coincides with solutions Ultraspeedforces2/199298118, madhurgupta185/199301914. My ratings of this contest have been reverted back. It was a simple problem. Why would I take code from someone who is a newbie.I have been using the same template for a long time. Please look into the matter and take necessary action. Please do look into the matter MikeMirzayanov