Editorial of Codeforces Round 860 (Div. 2)

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

1798A - Showstopper

1798B - Three Sevens

1798C - Candy Store

1798D - Shocking Arrangement

1798E - Multitest Generator

1798F - Gifts from Grandfather Ahmed

• 2 days ago, # ^ | It shows time when blog was created as a draft, not when it was published

  • 2 days ago, # ^ | Great contest, thanks :)

  • 10 hours ago, # ^ | thanks i was confused

• 2 days ago, # ^ | ← Rev. 2 →   +3 This case can hack it. 100000 1 49999 1 1 1 1 ...... 49999 1

• 2 days ago, # ^ | The sum of the array needs to be 0

• 2 days ago, # ^ | a1 + a2 + a3 + ... + an = 0 this does not hold in your case.

• 42 hours ago, # ^ | WOW! Lightning fast editorial

• 2 days ago, # ^ | can you provide B code in c++

  • 2 days ago, # ^ | check this submission 199295933.

• 2 days ago, # ^ | ← Rev. 3 →   0 Can you tell me What I am doing wrong 199314288? Doing something the same.

  • 2 days ago, # ^ | Take a look at Ticket 16782 from CF Stress for a counter example.

• 45 hours ago, # ^ | Also he did not include a pretest with n=2e5 in C on purpose.So my C and D are all hacked haha.

  • 42 hours ago, # ^ | Also no pretest with 50000 on B, causing my rank to drop from 2700 to 7000.

• 2 days ago, # ^ | 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.

  • 2 days ago, # ^ | 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

  • 31 hour(s) ago, # ^ | niceee, good to know people with 1600 rating are also HOPING for solutions to cover all cases , not just me

• 35 hours ago, # ^ | Yes, I also felt it. I regretted solving C before D.

• 10 hours ago, # ^ | Why that proof need to reduce the original problem to the case when n = prime? Does any step using the property that is a prime?

  • 8 hours ago, # ^ | Yes, because it assumes a-b is relatively prime with p when a != b

    • 33 minutes ago, # ^ | Oh, I got it. Thanks.

• 2 days 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.

• 46 hours ago, # ^ | 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).

• 42 hours ago, # ^ | 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.

  • 41 hour(s) ago, # ^ | Thanks. I should learn more.

• 42 hours ago, # ^ | Let be . Now let's try to price each type of candy with . For each , if cost of one pack is and one candy costs , one pack will contain candies. So must be divisible by . If we reorder that, must be divisible by . Since is divisible by , Each contains as a divisor.

• 37 hours 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 (it can be even improved to , where , with bitset), a lot of solutions fits into 50ms, and also there is Python solution that fits under 200ms.

• 34 hours ago, # ^ | is just which is super fast for 1 second on Codeforces' servers.

  • 33 hours ago, # ^ | I didn't notice that the sum of is no greater than 200. I thought for each there is a O() dp and the total complexity will reach O()... can be done in 1s is pretty fast though

• 30 hours ago, # ^ | ← Rev. 2 →   +10 let the cost of each pack of candies be . So, it must satisfy that for each . Thus, All must divide which means must divide . Now, is a divisor of . let, . for each . for each . must be an integer which means must divide . Thus, must divide .

  • 10 hours ago, # ^ | 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.

  • 8 hours ago, # ^ | Nice explanation.

  • 6 hours ago, # ^ | ← Rev. 2 →   0 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.