Codeforces Round 895 (Div. 3) Editorial

sevlll777's blog

Codeforces Round 895 (Div. 3) Editorial

• 5 months ago, # ^ | 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.

• 5 months 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 = 5 Now 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 c I hope you understood it

• 5 months ago, # ^ | because if there is any fraction then this fraction alone needs one pour to be transferred

• 5 months ago, # ^ | becouse we use the (a+b)/2 + 1 . That is equl ceil(a+b)/2

• 5 months ago, # ^ | I wonder, too.

• 5 months ago, # ^ | This is my submission using lazy segment tree.222476225

• 5 months ago, # ^ | This is my submission using segment tree.222537194

• 5 months ago, # ^ | This might help 222282535.

• 5 months ago, # ^ | 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 .

  • 5 months ago, # ^ | he didn't ask it tho

  • 5 months ago, # ^ | Yes, I know, I decided that during the contest, but it’s interesting to know another solution.

• 5 months 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.

  • 5 months ago, # ^ | It works, indeed! Thank you!

• 5 months ago, # ^ | It is because what we do is: we take d/2 from the greater one and add d/2 to the lesser one.

  • 5 months ago, # ^ | 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

• 5 months ago, # ^ |

• 5 months ago, # ^ | same here, but tried and failed

• 5 months ago, # ^ | Common!! can't be silly while ruling the official standings.

• 5 months ago, # ^ | same here :(

• 5 months ago, # ^ | Fixed

• 5 months ago, # ^ | https://cses.fi/problemset/ may be a good place to practice basic problems.

• 5 months ago, # ^ | 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

  • 5 months 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.

    • 5 months ago, # ^ | What do you mean by "doesn't work"? What did you change? What is the verdict?

    • 5 months ago, # ^ | Oh I think you meant to have 107107 instead of 106106 as the maximum size, since that's the maximum constraint. So you need to change what I mentioned earlier and the size. AC: 222452376

      • 5 months ago, # ^ | dang, i didnt know vectors can be that big, thank you for the help!

      • 5 months ago, # ^ | 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

• 5 months ago, # ^ | because that is given by rating predictor extension i believe which is not super accurate especially for div3 and div4 contests.

• 5 months ago, # ^ | your solution doesn't deserve to be intended/official , it's a overkill

• 5 months ago, # ^ | nice solution

• 5 months ago, # ^ | Clever solution. Thank You!! Here is my code which is readable with a 1 line explanation.

• 5 months ago, # ^ | ← Rev. 2 →   0 We want a=ba=b, then let's say a<ba<b. So a+x=b−xa+x=b−x (take xx from bigger one to small one). 2x=b−a→x=b−a22x=b−a→x=b−a2. Ok, in one operation you can only add cc to xx, then answer is ⌈xc⌉⌈xc⌉. xx may not be an integer, so use this trick: ⌈xy⌉=⌈k⋅xk⋅y⌉⌈xy⌉=⌈k⋅xk⋅y⌉, answer is ⌈2x2c⌉⌈2x2c⌉ or ⌈4x4c⌉⌈4x4c⌉ or ⌈2n⋅x2n⋅c⌉⌈2n⋅x2n⋅c⌉.

• 5 months 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;

• 5 months ago, # ^ | 1e9 is biggest needed but even the cases pass upto 4e5

• 4 months ago, # ^ | It would pass if you sieve upto only 1e4 .

• 5 months ago, # ^ | 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

• 5 months ago, # ^ | ← Rev. 2 →   0 1 is afraid of 2 2 is afraid of 1 3, 4, 5 are afraid of 1 Maximum cost will be 31: For 4, cost will be 2*1 = 2 -> because 1 is still not sold For 5, cost will be 2*1 = 2 -> because 1 is still not sold For 1, cost will be 2*9 = 18 -> because 2 is still not sold For 2, cost will be 1*8 = 8 -> because now 1 is sold and 2 is not afraid of any animal For 3, cost will be 1*1 = 1 -> because now 1 is sold and 3 is not afraid of any animal Total = 2 + 2 + 18 + 8 + 1 = 31

  • 5 months ago, # ^ | Thanks, i read the statement wrong

• 4 months ago, # ^ | See my comment below