Hello Codeforces!
Невероятно рад пригласить вас на Codeforces Round 860 (Div. 2), который пройдёт в 26.03.2023 17:35 (Московское время).
Раунд будет рейтинговым для всех участников, чей рейтинг ниже 2100. Участники с бóльшим рейтингом приглашены принять участие в раунде вне конкурса.
Вам будет дано 6 задач и 120 минут на их решение. Все задачи раунда придуманы и подготовлены мной.
Традиционный список благодарностей всем, кто принял участие в создании раунда:
🤴 DishonoredRighteous за координирование раунда
🐞 gyh20 за чёрно-красное тестирование раунда
😈 feecIe6418, iakovlev.zakhar, Dart-Xeyter, Adam_GS, ShuiLaoshi, golikovnik, Gary2005 за красное тестирование раунда
🐫 NemanjaSo2005, Alexdat2000, Kon567889, tem_shett за оранжевое тестирование раунда
👾 SlavicG, Psychotic_D за фиолетовое тестирование раунда
🐳 C2A, Masha237, ayhan23, Khonshu08, Brahma_tet за синее тестирование раунда
👽 Lord_David за зелёное тестирование раунда
🦄 mejiamejia за помощь с тестерами для раунда
🤡 sevlll777 за задачу, без которой раунд был бы несбалансирован, и задачи, которые не вошли в финальную версию раунда
🎅 MikeMirzayanov за потрясающие платформы Codeforces и Polygon, без которых проведение раунда было бы невозможно ㅤㅤㅤ
Я искренне надеюсь, что задачи покажутся вам интересными и вы получите удовольствие от их решения. Good luck!
Разбалловка:
500 — 750 — 1250 — 1750 — 2250 — 3000
UPD: Разбор
UPD2: Поздравляем ЧЕМПИОНОВ!
Неофициально:
Официально:
First AC:
A: nifek
B: AHappyPotato
C: AHappyPotato
D: aryan12
E: lebowski998
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 found
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
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.
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.
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
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!
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.
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 div2 contest!
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 the site will work fine.
Hope I'll turn CM soon :(
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
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
D<<<C
Who else facepalmed when they saw the announcement reminding the condition that the price tags have to be continuous?
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
posandneg. 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.
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
sumdenoting the sum of all elements used up to this point.if sum > 0you append the next negative value to the final arrayif sum =< 0you 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
maxequal the largest value and letminequal the smallest value of the array. You can notice that if currentlysum > 0, the next prefix sum will satisfysum > minand if currentlysum <= 0, the next prefix sum will satisfysum <= max. This means that all prefix sums satisfymin < sum <= max. The largest possible prefix sum is thusmaxand the smallest possible ismin + 1. The absolute difference of these is less thanmax - minwhich 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 i using 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 Stress for 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
sumdenoting the sum of all elements used up to this point.if sum > 0you append the next negative value to the final arrayif sum =< 0you 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
maxequal the largest value and letminequal the smallest value of the array. You can notice that if currentlysum > 0, the next prefix sum will satisfysum > minand if currentlysum <= 0, the next prefix sum will satisfysum <= max. This means that all prefix sums satisfymin < sum <= max. The largest possible prefix sum is thusmaxand the smallest possible ismin + 1. The absolute difference of these is less thanmax - minwhich 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 elementssum < 0. This means that there must be 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))andlogfrom 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
Nice idea, thanks!
Anyone knows why my submission for E is wrong?
https://codeforces.com/contest/1798/submission/199302004
My algorithm:
Divide 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.
The "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 Stress for a counter example.
Thank you! I missed an edge case.
very hard problemset
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?
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.
___,,___ ,d8888888888b,_ _,d889' 8888b, _,d8888' 8888888b, _,d8889' 888888888888b,_ _,d8889' 888888889'688888, /b _,d8889' 88888889' `6888d 6,_ ,d88886' _d888889' ,8d b888b, d\ ,d889'888, d8889' 8d 9888888Y ) ,d889' `88, ,d88' d8 `,88aa88 9 d889' `88, ,88' `8b )88a88'd88'
88 ,88 888b,_ d888888 d89 88, 88 d888b88_ 8888 88 88b 88 d888888 8: (6) 88') 88 8888b, 88 d888aaa8888,'Y' 88b ,888888888888d88aa88888b ,d888b ,8888688888888 d88a d8a88`8/q8b ,88'888888'"88 d8b d8888,88/ 9)_6 88 ,88"88 88p88 d88888888888bd8( Z~/ 88b 8p 88 68'88 88888888'6888898 8,88 8888888,qp' 8 8,q 8b88 88"888b q8 8b "8888888' "888 `q88b "888'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.
Why does the pretset data of D not have 3e5 so I got fst?
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
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.
even 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$$$.
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 :)
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
finalAppearenceof 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
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
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.
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/199273765
Can someone explain why this solution got runtime error on c?
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
> maxwheremaxis 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!
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
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