Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### sevlll777's blog

By sevlll777, history, 8 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 Tutorial of Codeforces Round 860 (Div. 2) Comments (96)
 » Shows me , posted 5 days ago, fastest editorial ??
•  » » It shows time when blog was created as a draft, not when it was published
•  » » » Great contest, thanks :)
•  » » » thanks i was confused
 » Oh, a tutorial with Python code, how avant garde
 » 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
•  » » 8 months ago, # ^ | ← Rev. 2 →   This case can hack it.11000001 49999 1 1 1 1 ...... 49999 1
 » Really great round, problems till D felt pretty solvable. Although managed to solve only 2 but had fun.
 » Fastest Editorial but I wanna unsolve first...
 » 8 months ago, # | ← Rev. 3 →   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
•  » » The sum of the array needs to be 0
•  » » a1 + a2 + a3 + ... + an = 0 this does not hold in your case.
 » WoW! The editorial dropped faster than my rating :)
 » WOW! Lightning fast editorial
•  » » WOW! Lightning fast editorial
 » 8 months ago, # | ← Rev. 6 →   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); } 
•  » » can you provide B code in c++
•  » » » check this submission 199295933.
 » 8 months ago, # | ← Rev. 2 →   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
•  » » 8 months ago, # ^ | ← Rev. 3 →   Can you tell me What I am doing wrong 199314288? Doing something the same.
•  » » » Take a look at Ticket 16782 from CF Stress for a counter example.
 » Did you not include a pretest with n=3e5 in D on purpose?
•  » » Also he did not include a pretest with n=2e5 in C on purpose.So my C and D are all hacked haha.
•  » » » Also no pretest with 50000 on B, causing my rank to drop from 2700 to 7000.
•  » » Can you tell me what I'm doing wrong submission? It failed in test case 10 of problem D.
 » 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
 » 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
•  » » 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.
•  » » » 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
•  » » » niceee, good to know people with 1600 rating are also HOPING for solutions to cover all cases , not just me
 » Please explain C someone ???
 » 8 months ago, # | ← Rev. 2 →   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
 » 8 months ago, # | ← Rev. 4 →   Problem D was easier than Problem C... Is it?
•  » » Yes, I also felt it. I regretted solving C before D.
 » 8 months ago, # | ← Rev. 2 →   (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.
•  » » 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?
•  » » » Yes, because it assumes a-b is relatively prime with p when a != b
•  » » » » Oh, I got it. Thanks.
 » In C, I really thought as long as the biggest bi (i.e max(b1,b2...bn) could divide the GCD, it should be fine. It took me like an hour after the contest ended to figure out why this wouldn't work.Love it when my brain turns off when I need it.
 » 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.
 » 8 months ago, # | ← Rev. 3 →   My Solution for problem C Codeint32_t main() { speed() int t; cin>>t; while(t--){ int n; cin>>n; vector>v(n); for(int i=0;i>a>>b; v[i]={a,b}; } int cnt=n; int curr=-1; int curr_mini=0,curr_maxi=0; for(int i=0;i
 » Like these hints.Thanks.
 » easy and cool up to problem D. However, can't solve problem E. I hope I will see a color change.
 » anyone provide me problem B c++ code
•  » »
•  » » » are you on discord
•  » » » » no
•  » »
 » 8 months ago, # | ← Rev. 2 →   another opportunity to feel ashamed....!!![ ]
 » 8 months ago, # | ← Rev. 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 ...
 » Thanks for the problems! Pretty interesting and balanced set.By the way, it seems we can't view the reference solutions.
•  » » 8 months ago, # ^ | ← Rev. 2 →   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.
 » How would you do D, if the sum wasn't 0?
•  » » 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).
 » 8 months ago, # | ← Rev. 2 →   <0000000000000000000>
 » 8 months ago, # | ← Rev. 2 →   how to solve the problem C if the types can be shuffled?
 » Appreciate that the solution has hints. Helps with upsolving problems beyond our range!
 » About the D Problem.max1≤l≤r≤n|al+al+1+…+ar|Is there a way to minimize this formula?
 » Would there be any efficient algorithm for Problem C when also allow reordering of the packs? Like for  20 3 6 2 14 5 20 7 21 2  we would still need 2 tags but we cannot use the prefix argument.
 » For B, you can choose the elements that appear the least later on in the future and it also works.
 » The solution link in the problem F is not working. Hope it will be fixed soon.
 » 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.
•  » » 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.
 » gcd(a1⋅b1,…,an⋅bn) is divided by lcm(b1,…,bn) can someone prove this?
•  » » Let $x$ be $lcm(b1,…,bn)$. Now let's try to price each type of candy with $x$. For each $i$, if cost of one pack is $x$ and one candy costs $b_i$, one pack will contain $x/b_i$ candies. So $a_i$ must be divisible by $x/b_i$. If we reorder that, $a_i⋅b_i$ must be divisible by $x$. Since $gcd(a1⋅b1,…,an⋅bn)$ is divisible by $x$, Each $a_i⋅b_i$ contains $x$ as a divisor.
 » 8 months ago, # | ← Rev. 2 →   why is my submission on problem c showing tle in test case 4. its a O(n) solution https://codeforces.com/contest/1798/submission/199363574edit: i found my mistake in worst case it was going upto n^2 . thank you
 » Really great round
 » 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
 » 8 months ago, # | ← Rev. 3 →   #include #include using namespace std; #include #include #include int arr; int main() { // your code goes here int t; cin>>t; while(t--){ int n; cin>>n; long long int a[n+1],b[n+1]; for(int i=1;i<=n;i++){ cin>>a[i]>>b[i]; } int count=1;long long int prev=a*b; long long int prev_fac=a; for(int i=2;i<=n;i++){ long long int p1=(a[i]*b[i])/(__gcd(a[i]*b[i],prev)); long long int p2=(prev)/(__gcd(a[i]*b[i],prev)); if(a[i]%p1==0 && prev_fac%p2==0 ){ prev=__gcd(prev,a[i]*b[i]); prev_fac=__gcd(prev_fac,a[i]); } else{ count+=1; prev=a[i]*b[i]; prev_fac=a[i]; } } cout<
 » 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?
•  » » 8 months ago, # ^ | ← Rev. 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.
•  » » $200^3$ is just $8*10^6$ which is super fast for 1 second on Codeforces' servers.
•  » » » 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
 » E is a beautiful problem
 » 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.
•  » » 8 months ago, # ^ | ← Rev. 2 →   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)$.
•  » » » 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.
•  » » » Nice explanation.
•  » » » 8 months ago, # ^ | ← Rev. 2 →   Is there any proof for these statements or material for reading:- 1. Thus, All Bi must divide C which means lcm(B1,B2,...,Bn) must divide C. 2. Thus, C must divide gcd(B1×A1,B2×A2,...,Bn×An). Please tell me, I am really confused. 
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   [LCM and GCD Universal Property](https://www.cut-the-knot.org/arithmetic/GcdLcmProperties.shtml#:~:text=For%20two%20(positive)%20integers%20N,N)%20%3D%20M%20%C3%97%20N.)
 » My contest went bad. But the overall quality of the problems are really good. I really appreciate the tutorial format too :)
 » 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.
 » 8 months ago, # | ← Rev. 2 →   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!
•  » » Is there any basic proof for why greedy works in C? Still can really believe it or prove it myself
•  » » » 8 months ago, # ^ | ← Rev. 4 →   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).
•  » » » » Ok, it makes sense, idk why didn't I see it during contest.
•  » » 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?
 » 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.
•  » » 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.
•  » » » Can you please explain why in your initial question "Is one price tag enough", just checking LCM(b1,b2,b3,...bn) as the cost of each bag was working?
 » 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?
•  » » 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. •  » » » Oh ok I think I understand now. Thank you for the clarification.
 » I didn't understand that C should be greedy. Anyone to explain?
 » @sevlll777In C The word 'cost' is the sum of all costs or the cost of an individual packet.