### sevlll777's blog

By sevlll777, history, 13 months ago, translation,

Thank you all for participating, I hope you enjoyed the problems! You can rate the problems of the round in the corresponding spoilers.

Hint 1
Hint 2
Tutorial
Solution
Rate the problem
Hint 1
Hint 2
Tutorial
Solution
Rate the problem
Hint 1
Hint 1.1
Hint 1.2
Hint 2
Tutorial
Solution
Rate the problem
Hint 1
Hint 1.1
Hint 2
Tutorial
Solution
Rate the problem
Hint 1
Hint 2
Hint 2.1
Hint 3
Tutorial
Solution
Rate the problem
Hint 1
Hint 2
Hint 3
Hint 3.1
Hint 4
Tutorial
Solution
Rate the problem
• +262

| Write comment?
 » 13 months ago, # |   +8 Shows me , posted 5 days ago, fastest editorial ??
•  » » 13 months ago, # ^ |   +1 It shows time when blog was created as a draft, not when it was published
•  » » » 13 months ago, # ^ |   +15 Great contest, thanks :)
 » 13 months ago, # |   0 Oh, a tutorial with Python code, how avant garde
 » 13 months ago, # |   +14 E can be passed by brute forcing all possible positions to change. Not sure if its provable but I couldn't think of any hack cases when coding it. https://codeforces.com/contest/1798/submission/199283535
•  » » 13 months ago, # ^ | ← Rev. 2 →   +3 This case can hack it.11000001 49999 1 1 1 1 ...... 49999 1
 » 13 months ago, # | ← Rev. 3 →   +4 In Problem D:Can anyone tell me the ans of test case:151 2 3 -30 -20According to my understanding, the ans should be No, as sum of abs(-30 + -20) > max(3) — min(-30), but many of the passed solutions are outputing YesEdit: Got it, forgot to read the very first line of question
•  » » 13 months ago, # ^ |   +12 The sum of the array needs to be 0
•  » » 13 months ago, # ^ |   +12 a1 + a2 + a3 + ... + an = 0 this does not hold in your case.
 » 13 months ago, # |   +36 WoW! The editorial dropped faster than my rating :)
 » 13 months ago, # |   0 WOW! Lightning fast editorial
•  » » 13 months ago, # ^ |   0 WOW! Lightning fast editorial
 » 13 months ago, # | ← Rev. 6 →   +12 Problem B is very similar to Kahn's algorithm. codestd::map mp; std::vector> g(n); for (auto &i : g) { int m; std::cin >> m; i.resize(m); for (int j : i) std::cin >> j, mp[j] += 1; } std::vector ans; for (auto &i : g) { int x = -1; for (auto &j : i) if (!--mp[j]) x = j; ///! /// in kahn, we do if (!--deg[j]) q.push(j) if (~x) ans.push_back(x); }
 » 13 months ago, # | ← Rev. 2 →   +18 You can solve C by abusing the fact that LCM grows fast too. Greedily try to make segments of the same cost. Naive $O(n^2)$ is to check if you can make the cost for the current range equal to $lcm(a[rstart, i])$ for every $i$, but you only need to do the $O(n)$ check if the value of LCM changes between $i-1$ to $i$. If it doesn't change you already know it's possible for the range $[rstart, i-1]$. So you just need to check if you can include $i$ in the range. 199293298
•  » » 13 months ago, # ^ | ← Rev. 3 →   0 Can you tell me What I am doing wrong 199314288? Doing something the same.
 » 13 months ago, # |   +28 Did you not include a pretest with n=3e5 in D on purpose?
•  » » 13 months ago, # ^ |   +8 Also he did not include a pretest with n=2e5 in C on purpose.So my C and D are all hacked haha.
•  » » » 13 months ago, # ^ |   0 Also no pretest with 50000 on B, causing my rank to drop from 2700 to 7000.
 » 13 months ago, # |   +50 The system test of problem E is too weak. My brute force solution passed it, and it can be hacked by a very simple testcase. Please be more careful for preparing testcases.Link:199296293
 » 13 months ago, # |   +4 This was kind of a hope greedy works contest imo. In both c and d i was like "i hope this covers all cases, let's submit". I don't really like this kind of problems
•  » » 13 months ago, # ^ |   0 That's so true man I did the same with C then I could not think about the solution of D so with 5 minutes remaining just coded up whatever came to mind and it got accepted with 15 seconds remaining hehe.
•  » » » 13 months ago, # ^ |   0 True, turns out that in d you can just assign any valid value and repeat for each element of the array and it's guaranteed to find the solution
 » 13 months ago, # |   0 Please explain C someone ???
 » 13 months ago, # | ← Rev. 2 →   0 In C, according to tutorial if we solve for prefixes like:{[a1, a2, a3] [a4, a5, a6] [a7, a8, a9, a10]} have price tags {c1, c2, c3} and c1 becomes equal to c3. the solution should fail, correct me where I'm wrong.Edit: I read the question wrong
 » 13 months ago, # | ← Rev. 4 →   +33 Problem D was easier than Problem C... Is it?
 » 13 months ago, # | ← Rev. 2 →   +55 (For problem F) I had never heard of the Erdős--Ginzburg--Ziv theorem but I guessed that it had to be true by the fact that none of the samples had "-1" as an answer.For those curious, an elementary proof is in the second response here.
•  » » 13 months ago, # ^ |   0 Why that proof need to reduce the original problem to the case when n = prime?Does any step using the property that $p$ is a prime?
•  » » » 13 months ago, # ^ |   0 Yes, because it assumes a-b is relatively prime with p when a != b
•  » » » » 13 months ago, # ^ |   0 Oh, I got it. Thanks.
 » 13 months ago, # |   -42 Did not participate in this round but surely not a well set round. You expect Div2C and Div2D to have a certain difference in difficulty. The D problem surely didn't deserve to be a Div2D.
 » 13 months ago, # |   +3 Like these hints.Thanks.
 » 13 months ago, # |   -13 anyone provide me problem B c++ code
•  » » 13 months ago, # ^ |   +1
•  » » » 13 months ago, # ^ |   0 are you on discord
•  » » » » 13 months ago, # ^ |   0 no
 » 13 months ago, # | ← Rev. 2 →   +2 In C problem , wrote the code of LCM wrong. Didnt check as i was taking GCD and LCM for granted. Can't handle more negative. Wanna die :(Negative delta loading ...
 » 13 months ago, # |   +44 Thanks for the problems! Pretty interesting and balanced set.By the way, it seems we can't view the reference solutions.
•  » » 13 months ago, # ^ | ← Rev. 2 →   +8 lol, indeed, thanks for pointing it out. fun fact is that I copied template from editorial of previous round, and it is impossible to see reference solution in that editorial too, and nobody said that before. that is pretty much proves, that this references are useless, but I'll update them soon.
 » 13 months ago, # |   +7 How would you do D, if the sum wasn't 0?
•  » » 13 months ago, # ^ |   +2 Basically the same idea of considering prefix sums works except you have to be a bit more careful. If all the numbers are nonnegative or nonpositive it's clearly impossible. Now, without loss of generality assume the total sum is nonnegative. Let mx be the max element and mn be the minimum element. If the total sum is >= mx — mn, then of course the task is impossible no matter how you reorder the array, otherwise it's possible.First, place all the 0s in the array at the front. Then, it is possible to add elements so that the prefix sums are always in [0, mx — mn). Specifically, if the current sum is in [0, -mn), you add a positive element, otherwise if it is in [-mn, mx — mn), you add a negative element. This strategy ensure the prefix sum will always be in [0, mx — mn) until we run out of positive elements or negative elements. Then, since the total sum is in [0, mx — mn), adding the remaining positive or negative elements will still keep the prefix sum within [0, mx — mn).
 » 13 months ago, # |   +4 Appreciate that the solution has hints. Helps with upsolving problems beyond our range!
 » 13 months ago, # |   0 About the D Problem.max1≤l≤r≤n|al+al+1+…+ar|Is there a way to minimize this formula?
 » 13 months ago, # |   0 For B, you can choose the elements that appear the least later on in the future and it also works.
 » 13 months ago, # |   0 The solution link in the problem F is not working. Hope it will be fixed soon.
 » 13 months ago, # |   0 I think the testcases of problem B is weak ? My nearly brute force solution 199278375 passed (1387ms) ,and you can easily find a testcase to hack my code.
•  » » 13 months ago, # ^ |   0 Which part is brute force? Learn meaning of it first xD. It is greedy and since everyone can take at most one place, your solution is correct. Getting 1387 ms. because for every test case (5e4), you're clearing your arrays with size 5e5.
•  » » » 13 months ago, # ^ |   0 Thanks. I should learn more.
 » 13 months ago, # |   0 Really great round
 » 13 months ago, # |   +1 Great round and a great editorial indeed. If anyone wants a video editorial for these problems (for Problem A, Problem B, Problem C, Problem D). You can watch this here — video editorial
 » 13 months ago, # |   0 the solution for F can't be viewed.Also if the complexity for single si is n^3(8000000) and the restriction is 1s, how can this avoid getting TLE?
•  » » 13 months ago, # ^ | ← Rev. 3 →   +3 I pasted my code in editorial. For a more understandable and better written code, I recommend to look into jiangly's submissions (Top1 of this round).On practise, this is very very fast $O(n^3)$ (it can be even improved to $O(n^3/w)$, where $w = 64$, with bitset), a lot of solutions fits into 50ms, and also there is Python solution that fits under 200ms.
•  » » 13 months ago, # ^ |   +5 $200^3$ is just $8*10^6$ which is super fast for 1 second on Codeforces' servers.
•  » » » 13 months ago, # ^ |   0 I didn't notice that the sum of $s_i$ is no greater than 200. I thought for each $s_i$ there is a O($n^3$) dp and the total complexity will reach O($n^4$)...$8*10^6$ can be done in 1s is pretty fast though
 » 13 months ago, # |   +39 E is a beautiful problem
 » 13 months ago, # |   0 In Problem C I don't understand why using GCD and LCM. can anyone explain it in detail? I really appreciate any help you can provide.
•  » » 13 months ago, # ^ | ← Rev. 2 →   +10 let the cost of each pack of candies be $C$. So, it must satisfy that $C = B_i \times D_i$ for each $1 \leq i \leq n$.Thus, All $B_i$ must divide $C$ which means $lcm(B_1, B_2,..., B_n)$ must divide $C$.Now, $D_i$ is a divisor of $A_i$. let, $K_i = \frac{A_i}{D_i}$.$C = B_i \times \frac{A_i}{K_i}$ for each $1 \leq i \leq n$.$K_i = \frac{B_i \times A_i}{C}$ for each $1 \leq i \leq n$.$K_i$ must be an integer which means $C$ must divide $B_i \times A_i$.Thus, $C$ must divide $gcd(B_1 \times A_1, B_2 \times A_2,..., B_n \times A_n)$.
•  » » » 13 months ago, # ^ |   0 You are the God Sir. Believe me You explained it so clearly . My whole lifetime i will not forget this(I am not exaggerating.)I Wish every tutorial are like this. Thanks a lot sir.
 » 13 months ago, # |   +56 For Problem F, the $n^3$ DP can be instead be done in $n\log n$ after a recent preprint. See submission 199466476 (assuming I implemented it correctly). Obviously, this is completely unnecessary.
 » 13 months ago, # | ← Rev. 2 →   +46 Ok, its 2 days after round, I decided to write a little postscriptum, which can answer some questions and show some insights of problemsetting/testing.Firstly: thanks everyone who wrote comment with positive feedback about the problems, it's a big pleasure to see it, really. Second: apologize to everyone who got FST and negative delta because of it, pretests quality on problems B, C, D was poor, I'll be more careful with this next time. Why D is easier than C, is it intended? Obviously this was not intended. Problem C turned out to be harder than I thought, while problem D turned out to be easier than I thought. At most of the testing problem C was formulated as "is one price tag enough for all candies?". And many testers basically guessed solution, like: lets try $lcm(b_1, b_2, \ldots, b_n)$ as a cost, if it fits answer is Yes, otherwise No. I didnt like it at all, I wanted understanding of criteria "gcd divides lcm" from everyone who solves this problem. Thats why it was adjusted to the current version. I really didnt expect that this change will make problem that harder, so new version of C wasnt well tested. I am still shocked how many of you wrote dp + sparce_table/segment_tree instead of greedy. And problem D was the last problem added to contest (most part of testing it didnt exist), and I was ensure in its difficulty, so it was tested by only 7 testers, which is small. Moral: if you change problem please make sure it well-tested, even if you think that your change is very minor and don't trust your inner sense of the difficulty of problems too much. Overall I am happy with change of problem C, it made it more interesting, but I definitely should have swapped C and D. Story of problem A Problem A was created by statement $\to$ solution method. Originally it had legend about about a concert with two scenes, and the closing perfomances on both scenes should be the most spectacular. The only thing that left from this legend in problem — it's name: Showstopper. Story of problem B Very first version of this problem was: $n$ people playing knockout game, and its known that after round $i$ either $a_i$ and $b_i$ leave the game, determine any order of knockouts of players. It was created in 2020 for round 645 (but there were much much better Div2B). For 2 years this task was forgotten, but when making this contest I revisited all my problem ideas from past. After some time it was adjusted to current version about lottery. So this problem was created by statement $\to$ another statement $\to$ solution method. Story of problem C Also created by statement $\to$ solution, tho statement was updated from original "is one price tag enough?" to the current version. Story of problem D Problem was solely created to fill gap in this round. It took 3 months to come up with it, because its literally impossible to set good problem targeting specific difficulty range. Method of creation once again statement $\to$ solution. Story of problem E Another statement $\to$ solution problem. I was very afraid that this problem appeared somewhere before, because it sounds very natural, but it seems I was the first who come across this. Story of problem F Yeah, this is inverse: solution $\to$ statement problem. I was amazed by Erdos-Ginzburg-Ziv theorem when I hear about it first, and it seemed not well-known, so I really wanted to set problem on it. The first 2 problems I tried to set specifically on EGZ turned out to be terrible, this one was third attempt. Also this problem was created for round 770 in 2021, and was even accepted by Anton Trygub, but for some reason it didnt make it to the contest (I dont remember why). Forgive my non-prefect English, but I believe text is still understandable despite my mistakes. Thanks everyone who read that!
•  » » 13 months ago, # ^ |   0 Is there any basic proof for why greedy works in C? Still can really believe it or prove it myself
•  » » » 13 months ago, # ^ | ← Rev. 4 →   +3 Consider any possible answer and any possible price tag in it. If this price tag can be expanded to the right by 1, lets expand it. Since "If one price tag is enough for a set of candies, then if you remove any type of candy from this set, one price tag will still be enough" this action can not increase number of price tags. So starting from any possible answer we can expand any price tag to the right while we can, and number of price tag will not increase. After we do all possible expands we will achieve greedy construction (in greedy construction no price tag can be expanded to the right. and its unique construction, because there is only way to choose prefix that cannot be expanded to the right, and so on).
•  » » » » 13 months ago, # ^ |   +8 Ok, it makes sense, idk why didn't I see it during contest.
•  » » 13 months ago, # ^ |   0 Thanks for the editorial, I have a simple doubt, Can you tell me in problem C we are taking lcm(b1,b2...bn) and not lcm(b1*d1,b2*d2...bn*dn). Is that because we are trying to remove di from the picture?
 » 13 months ago, # |   0 Cost of each bag from i to j will be gcd(ai*bi, ai + 1 * bi+ 1,...., aj * bj) (provided the condition stated in tutorial for i to j is satisfied) Or I am thinking wrong? Please someone explain.Thanks, in advance.
•  » » 13 months ago, # ^ |   0 Cost can be any integer $x$ such that $gcd(a_i \cdot b_i, \ldots, a_j \cdot b_j)$ divides $x$, and $x$ divides $lcm(b_i, \ldots, b_j)$. So yeah, this gcd is one of the options of cost.
 » 12 months ago, # |   0 For problem E, why is it the case that you only need to check if the dynamics value at i+1 is greater than or equal to a_i? Why don't they need to be exactly equal? In other words, how is it possible to create any number of tests up until the maximum number of tests that can be achieved by changing one element?
•  » » 12 months ago, # ^ |   0 Yes, this is fair remark. We can see that if 1 change was made to make $x$ tests, we can redo it to make exactly $x - 1$ tests. If first element was changed ($i+1$) it is pretty clear, we just extend $go_{i+1}$ to cover one more test. And if not first element was changed, you can change previous element (see picture). So if you can achieve $x$ tests you can achieve $x-1$ and so on, recursively, you can achieve any number from $1$ to $x$. And since $a_i \geq 1$ in the problem, its enough.
 » 11 months ago, # |   0 I didn't understand that C should be greedy. Anyone to explain?
 » 6 months ago, # |   0 @sevlll777In C The word 'cost' is the sum of all costs or the cost of an individual packet.
 » 4 months ago, # |   0 thank you for writing the editorial with hints......
 » 3 months ago, # |   0 https://codeforces.com/contest/1798/submission/245358316 I mistakenly solved the harder version of $D$ where sum of the elements of the array is not necessarily 0