### sevlll777's blog

By sevlll777, history, 3 weeks ago,

Thanks for joining the contest!

Tutorial
Solution
Tutorial
Solution
Tutorial
Solution
Tutorial
Solution
Tutorial
Solution
Tutorial
Solution
Tutorial
Solution
• +77

 » 3 weeks ago, # |   0 why are we taking ceil in problem A?
•  » » 3 weeks ago, # ^ |   0 Because we need to be certain that d gets to 0. We need at most floor to make sure that d < 2 * c and then one more to be sure that d = 0.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +10 because if we take floor or don't take anything we will not be considering the residue.Residue here means , for example taking a = 5, b = 18, c = 5. Therefore after the first pour we will have a = 10, b = 13, c = 5Now the residue is 3lt but since c = 5 we cannot pour another full bucket of c thus we will be pouring the residue ( remaining 3lt with c ) thus we have to take ceil to consider this residue or rather we could say in a case where the final water transfer of quantity less than the value of cI hope you understood it
•  » » 3 weeks ago, # ^ |   0 because if there is any fraction then this fraction alone needs one pour to be transferred
•  » » 3 weeks ago, # ^ |   -19 becouse we use the (a+b)/2 + 1 . That is equl ceil(a+b)/2
 » 3 weeks ago, # |   +1 Does anyone have a solution to problem E through a segment tree?
•  » » 3 weeks ago, # ^ |   0 I wonder, too.
•  » » 3 weeks ago, # ^ |   0 I used sqrt decomposition
•  » » » 3 weeks ago, # ^ |   0 how?
•  » » » » 2 weeks ago, # ^ |   0
•  » » » » » 2 weeks ago, # ^ |   0 Excellent explanation of another solution method, thank you very much!
•  » » » » » 2 weeks ago, # ^ |   0 thanks
•  » » 3 weeks ago, # ^ |   +1 This is my submission using lazy segment tree.222476225
•  » » 3 weeks ago, # ^ |   0 you can read more about lazy segment tree here: https://codeforces.com/blog/entry/15890my solution: 222252960
•  » » 2 weeks ago, # ^ |   0 This is my submission using segment tree.222537194
•  » » 2 weeks ago, # ^ |   0 This might help 222282535.
•  » » 2 weeks ago, # ^ |   0 u can use simple prefix array method to find the xor of a segment theres no need of a segment tree here , ps u can see my solution .
•  » » » 2 weeks ago, # ^ |   0 he didn't ask it tho
•  » » » 2 weeks ago, # ^ |   0 Yes, I know, I decided that during the contest, but it’s interesting to know another solution.
 » 3 weeks ago, # |   0 Thanks for the fast Editorial.
 » 3 weeks ago, # | ← Rev. 3 →   0 222359696 I had somewhat similar thinking process in D, however, my way of calculation led to imprecise numbers where there were lots of digits. But why exactly? Test 4 failed because there were differences in the 17th tenth lol.
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +21 In Python the / operator is float division, even if your result could be an integer, even something dumb like: >>> print('{:f}'.format(100000000000000000000000/1)) 99999999999999991611392.000000 When you do int() it's already too late! replace / with //, the integer division operator, in the score calculation in your solution, it makes your solution work.
•  » » » 3 weeks ago, # ^ |   0 It works, indeed! Thank you!
 » 3 weeks ago, # |   +31 For problem G, let's say we want to find under what conditions it is optimal take the product of a subarray .Suppose we have a prefix product equal to $p$ at index $i$ and we are considering joining this product to a $>1$ element at index $j > i$ to take the product. In the worst case, we have the array $A = [p, 1, ..., 1, 2]$ with $n - 2$ ones in between the first and last element.For the product to be optimal: $2 * p > p + (n - 2) + 2 \Rightarrow p > n$, so the total product ($2 * p$) must be strictly bigger than $2n$ as mentioned in the tutorial.
 » 3 weeks ago, # | ← Rev. 2 →   0 For problem F, can someone please find the scenario where this submission is failing? 222376285
 » 3 weeks ago, # |   0 problem A ，why 2*c ？
•  » » 3 weeks ago, # ^ |   0 It is because what we do is: we take d/2 from the greater one and add d/2 to the lesser one.
•  » » » 3 weeks ago, # ^ |   0 I understand, because when we take c from the large and add c to the small, then calculating the difference again equals 2c. thank you
 » 3 weeks ago, # |   0 Good problem and fast editorial, Thanks for this contest!
•  » » 2 weeks ago, # ^ |   0 %%%
 » 3 weeks ago, # |   0 We can make the bound even better ( although not needed ) for problem G. We shall first exclude all prefix and suffix ones to get new array. If we include all elements of this new array , the answer is atleast P ( product of all elements ) — 2 * 10^5*10^9 ( here by answer I mean product(subarray(l,r)) — sum(subarray(l,r)) as we are maximizing it.). Which means it is atleast P — 2^48. Now any subarray other than this full array will have product at most P / 2. so answer for any subarray is atmost P / 2. Now , P — 2 ^ 48 >= P / 2 implies P >= 2 ^ 49. hence we can check if P >= 2 ^ 49 ( instead of 60 . )
 » 3 weeks ago, # |   +1 Alternate thought process of Problem A:WLOG assume, a
 » 3 weeks ago, # |   +1 Silly me has written a lazy segment tree for E.
•  » » 3 weeks ago, # ^ |   0 same here, but tried and failed
•  » » 3 weeks ago, # ^ |   -8 Common!! can't be silly while ruling the official standings.
•  » » 3 weeks ago, # ^ |   0 same here :(
 » 3 weeks ago, # | ← Rev. 2 →   0 .
 » 3 weeks ago, # |   +1 problems were well balanced thank you for the contest
 » 3 weeks ago, # |   0 Editorial solution for problem G TLE on test 61
•  » » 3 weeks ago, # ^ |   +1 Fixed
 » 3 weeks ago, # | ← Rev. 4 →   0 B. The Corridor or There and Back AgainAs we are supposed to return to room number 1, for the following test case the correct answer should be k=2 and not k=1test case: 1 1 1 2 correct answer is k=2, 1st second : room 1 -> room 2 2nd second : room 2 -> room 1as after 2 second the person is back to room 1, the maximum value should be k=2.
 » 3 weeks ago, # | ← Rev. 2 →   0 I'm new to CP. I used codeforces for 10 days, a few months ago, to improve my implementation skills. But the thing is, I can't solve questions like C (the gcd one). Since I'm new to cp, I wouldn't mind if I can't solve the D or above problems. I really want to learn how to solve math problems. Like it's so hard. I feel like it's totally different from my college-level math. Though they are all very basic math problems, I can't solve them on codeforces or codechef. I try to solve a math problem (div2/3 A) but when I look at the editorial, it's just only an equation. Can anyone suggest some resources to learn how to solve these gcd, prime numbers, combinatorics, kind of math problems on codeforces?? I'm gonna take cp seriously from now.Thank you!
•  » » 3 weeks ago, # ^ |   0 https://cses.fi/problemset/ may be a good place to practice basic problems.
 » 3 weeks ago, # |   0 Thanks for the tutorial.
 » 3 weeks ago, # |   0 E task is 10 XOR out of 10
 » 3 weeks ago, # |   0 In problem A, How does adding {+ 2c — 1} in the nominator calculate floor value?
 » 3 weeks ago, # |   0 Another greedy solution for F https://codeforces.com/contest/1872/submission/222276481
 » 3 weeks ago, # |   0 222445465 does anyone know why i am getting runtime error in this code?
•  » » 3 weeks ago, # ^ |   0 You are trying to access prep[1000000] but it is out of bounds of prep.prep has a size of 1000000, which means it has indices 0 to 999999
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 still doesnt work. the thing thats weird is that, from testcase 1 to 7, it works perfectly well, but when it reaches 8, it stops working. what is this wizardry.
•  » » » » 3 weeks ago, # ^ |   0 What do you mean by "doesn't work"? What did you change? What is the verdict?
•  » » » » 3 weeks ago, # ^ |   0 Oh I think you meant to have $10^7$ instead of $10^6$ as the maximum size, since that's the maximum constraint.So you need to change what I mentioned earlier and the size.AC: 222452376
•  » » » » » 3 weeks ago, # ^ |   0 dang, i didnt know vectors can be that big, thank you for the help!
•  » » » » » 2 weeks ago, # ^ |   0 Hello , please help In the tutorial for 1872C, Under point number 1 it is mentioned that we only need to calculate shortest composite number in the interval [r,l] but in the question we are asked to report two non coprime numbers that sum to a number(that turns out to be composite) in the interval [r,l] so once i have calculated the favourable composite number how to calculate the values of a and b ? thanks
 » 3 weeks ago, # |   0 For G, there probably be a roughly prof: say we have a1(>1), 1, 1, 1,... (we have x ones), P1(products of remaining numbers), so if we left a1 the result will be a1 + x + P1, otherwise it's P1 * a1. Then a1+x+P1-P1*a1=(1-a1)*P1+a1+x, because P1 is large enough, and a1>1, a1+x+P1-P1*a1 will always < 0, so a1+x+P1 < P1*a1.
 » 3 weeks ago, # |   0 Why is there inconsistency in the rating change mentioned in friends standing and the friends rating change? My rating change displayed in the last column of friends standing and in friends rating change are different.
•  » » 2 weeks ago, # ^ |   +10 because that is given by rating predictor extension i believe which is not super accurate especially for div3 and div4 contests.
 » 3 weeks ago, # |   -9 For problem F, I am quite surprised that the offical solution is not using segment tree to find the highest priority animal to be selled each time, update the sold animals to the lowest priority and update the animal which the sold animals afraid of to a higher priority to be sold. Here is my solution. Thus, I think it should be also tagged with "data structure", and I enjoyed finding an unexpected solution for this multi-solution problem within the contest period. Thank the problemsetters for making this interesting div.3 contest.
•  » » 3 weeks ago, # ^ |   +13 your solution doesn't deserve to be intended/official , it's a overkill
 » 3 weeks ago, # | ← Rev. 5 →   0 How to solve problem E if instead of finding XOR of elements we had to find sum? Calculate the value of the bitwise XOR of the numbers ai for all indices i such that si=g Here, instead of bitwise XOR, we had to calculate sum.How to solve F if an animal was afraid of more than one animal?
 » 3 weeks ago, # |   0 1599 is like a clown. Please, give me one extra point༼ つ ◕_◕ ༽つ.
 » 3 weeks ago, # |   0 Wow, problem D has been explained amazing
 » 3 weeks ago, # |   0 Problems were balanced.
 » 3 weeks ago, # |   +1 Problem F can be solved using std::multiset. My solution is here
•  » » 3 weeks ago, # ^ |   +1 nice solution
•  » » 12 days ago, # ^ |   0 Clever solution. Thank You!!Here is my code which is readable with a 1 line explanation.
 » 2 weeks ago, # |   0 In the tutorial for 1872C, Under point number 1 it is mentioned that we only need to calculate shortest composite number in the interval [r,l] but in the question we are asked to report two non coprime numbers that sum to a number(that turns out to be composite) in the interval [r,l] so once i have calculated the favourable composite number how to calculate the values of a and b ?
 » 2 weeks ago, # |   0 Is this arithmetic progression formula useful here? Sn = n/2((2 * a)+ (n — 1) * d) I got wrong answer on testcase 4 here is my submission: https://codeforces.com/contest/1872/submission/222426491
 » 2 weeks ago, # |   -6 Simple Neat and Clean code for Codeforces Round 895 (Div. 3)krishnash1355Solutions:Problem A : 1872A - Two Vessels Submission A : 222226952Problem B : 1872B - The Corridor or There and Back Again Submission B : 222235441Problem C : 1872C - Non-coprime Split Submission C : 222275700Problem D : 1872D - Plus Minus Permutation Submission D : 222260066Problem E : 1872E - Data Structures Fan Submission E : 222285746
 » 2 weeks ago, # |   0 in problem D to get the purple indices . n=n/(x*y); can't we?
 » 2 weeks ago, # |   0 I don't understand A. Why is it 2*c, why not c, 3c, 4c??
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 We want $a=b$, then let's say \$a
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Example: if(a > b) swap(a,b); ll koef = 50; ll x = (koef / 2) * (b - a); ll y = koef * c; cout << (x + y - 1) / y; 
 » 2 weeks ago, # |   +3 Lovely F :))
 » 2 weeks ago, # |   0 Really good problems, thanks authors
 » 2 weeks ago, # |   0 for problem E ,1e15 or 2^60 or 2^48 are very loose bounds .It seems to me that the solvers that passed the test cases didnot actually solve the problem.Nobody here has comeup with such bound .I actually want to understand the problem.
•  » » 2 weeks ago, # ^ |   0 1e9 is biggest needed but even the cases pass upto 4e5
 » 2 weeks ago, # |   0 There is another solution to problem F. I'm using the maximum spanning tree to find the maximum cost edges and after that, in that maximum spanning tree I use topological sorting to find which animal I can sell at first or which animal has minimal dependencies on other animals. Here is my code: 222724522
 » 2 weeks ago, # |   0 Can someone show how binary search can be used to find the solution for problem B? I'm quite new and haven't yet fully understood binary search and all its variants/applications. Many thanks in advance!
 » 2 weeks ago, # |   0 Might not be the best one, but this is my solution to problem C. Basically I sieved and found all prime numbers up to 1e7, then for each prime p try to find another integer k so p * k is in the required range. The l == r case is added later as I keep getting TLE'd on test 4. It takes longer to code up and has a longer runtime, but is intuitive (at least to me) and gives me a refresher on prime sieving.
 » 11 days ago, # |   0 whats wrong in my code for problem D ,in test case 3 it fails at one particular case . Can anyone tell whats the mistake ? https://codeforces.com/contest/1872/submission/223526983
•  » » 10 days ago, # ^ |   0 Use long long int for lcm In case both x and y are co-primes in lcm(x, y) then lcm will be x*y which can be greater than int.https://codeforces.com/contest/1872/submission/223538859
•  » » » 10 days ago, # ^ |   0 thanks
 » 9 days ago, # | ← Rev. 2 →   0 Why is sample test 3 for problem F correct? Input5 2 1 1 1 1 9 8 1 1 1  Output3 4 5 1 2With this output the money you get is 31, but if the output is: Other output4 5 1 2 3The money is 32. What?
•  » » 8 days ago, # ^ | ← Rev. 2 →   0 1 is afraid of 2 2 is afraid of 1 3, 4, 5 are afraid of 1Maximum cost will be 31:For 4, cost will be 2*1 = 2 -> because 1 is still not soldFor 5, cost will be 2*1 = 2 -> because 1 is still not soldFor 1, cost will be 2*9 = 18 -> because 2 is still not soldFor 2, cost will be 1*8 = 8 -> because now 1 is sold and 2 is not afraid of any animalFor 3, cost will be 1*1 = 1 -> because now 1 is sold and 3 is not afraid of any animalTotal = 2 + 2 + 18 + 8 + 1 = 31
•  » » » 8 days ago, # ^ |   0 Thanks, i read the statement wrong