### KAN's blog

By KAN, 3 years ago, translation,

### 931A - Friends Meeting

At first understand the fact that friend should make their moves one be one and the friend who initially was left should move to the right and other friend should move to the left. Let len = |a - b|. Then the first friend will make cntA = len / 2 moves, and the second friend — cntB = len - len / 2 moves. So the answer is the sum of two arithmetic progressions cntA·(cntA + 1) / 2 and cntB·(cntB + 1) / 2.

The given constrains allowed to calculate this sums in linear time — simply iterate from 1 to cntA for the first sum and from 1 to cntB to the second.

Thanks GreenGrape for translation!

• +55

 » 3 years ago, # |   +5 Oh plz, where's the tutorial for div1 E?
•  » » 3 years ago, # ^ |   -6 Isn't it 944D — Game with String?
•  » » » 3 years ago, # ^ |   0 No, It's the problem "Coins Exhibition"
•  » » » 3 years ago, # ^ |   0
•  » » » 3 years ago, # ^ |   0 Or Problem 944G — Coins Exhibition
•  » » » » 3 years ago, # ^ |   -21
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I know this problem. It's Div1 B or Div2 E, not Div1 E.
 » 3 years ago, # |   0 Are there other problems similar to 944D — Game with String? It is a very interesting problem and I want to practice it more. Thanks
 » 3 years ago, # |   0 Is Div. 1 D solvable by some kind of modified convex hull algorithm?
•  » » 3 years ago, # ^ |   +5 I think the method mentioned by the tutorial, is just some kind of modified convex hull algorithm.
 » 3 years ago, # |   0 Anya should write the measurements equal to (min + 1) in the amount of (leftSum - minSum), Please explain what does it mean ? Thanks
 » 3 years ago, # |   0 Can someone explain Div.2C?
•  » » 3 years ago, # ^ | ← Rev. 6 →   0 Say you have only 0's, 1's and 2's in array.To preserve average you can either pick 0 and 2 and change both to 1 or pick two 1's and change one of them to 0 and other one to 2. Obviously, it makes no sense to take 0, 2 change it to two 1's and then change it back to 0 and 2 again, you won't gain anything.So now you pick one of the transformations 0,2 into 1,1 or 1,1 into 0,2. Pick one that gives you more numbers to change and perform transformations.Example:0 0 0 1 1 1 2 2 2 2 2Here, you can pick two 1's and get the array:0 0 0 0 1 2 2 2 2 2 2but that way you changed only 2 numbers. It's better to pick 0's and 2's, change them into 1's so you will get: 1 1 1 1 1 1 1 1 1 2 2(notice how you have to left 2's at the end since you don't have more 0's to "balance" the change in terms of average value).For the next paragraph I will use this definition: cnt(x) — number of times x is present in arrayHow many changes will you get from transforming 0's and 2's into 1's? min(cnt(0), cnt(2)) * 2How many changes will you get from transforming 1's into 0's and 2's? floor(cnt(1) / 2) * 2 (fancy way of saying cnt(1) if cnt(1) is even and cnt(1) — 1 if it's odd)Special cases:1) There are only 0's in array; there are only 0's and 1's in array — in those cases you cannot change anything (remember about the constraint that your minimal/maximal numbers have to be between minimal/maximal from original array, so you don't have any possibility for change without breaking this constraint or changing average). Obviously the same case for only 1's etc.2) There are 0's and 2's in array — that just reduces to transforming as many of them as you can into 1's.My solution:http://codeforces.com/contest/931/submission/35947027(it's not crystal clear, because of the part which actually changes the numbers in array, I guess I should have done it in different way)
•  » » » 12 months ago, # ^ |   0 Thanks for your comment ! I too was following your approach and not the editorial one and was not able to debug until I came across your post. I missed the special cases ! Here is my code and explanation
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 Find diff = 0, 1, or 2 depending on if there are 1, 2, or 3 different numbers. My solution was to look at these cases: diff <= 1 means that nothing better can be done than duplicating all results. diff == 2 means that we have numbers x1, x2, x3 ordered from smallest to largest. We can transform pairs of (x1,x3) into (x2,x2); and we can transform pairs of (x2,x2) into (x1,x3). Each transformation reduces the number of copied results by 2. Find the maximum number of transformations you can make between those two types of pairs. my solution
•  » » 2 months ago, # ^ |   0 Case1 : (xMax-xMin)<2 Because there is no way to change the numbers such that sum remains the same as before. So we can't change any number and ans will be 'n' followed by the initial given numbers in the next line. Case 2 : (xMax-xMin)==2 Suppose xMax = a+1, then xMin = a-1 and the other number whose presence is not guranteed will be 'a'. So there are two ways,Way 1 — You replace a+1 and a-1 with 2 a, because sum will remain same.Way 2 — You replace 2 a with a+1 and a-1, in this case also sum will remain same.The most optimal way to get answer will be to follow one way at all steps, because there is no sense of replacing 2 a with a+1 and a-1, and then again replacing a+1 and a-1 with a.Now you just have to check which way, either 1 or 2 is more optimal. Best of luck
 » 3 years ago, # |   +44 I'm wondering why there's still no tuturials for the problem Coins Exhibition. I got stuck on this problem and need help.....
 » 3 years ago, # |   +3 Problem A video solution: https://youtu.be/bFEmX3y8idE Problem B video solution: https://youtu.be/tzF_nagpR5AProblem C and D coming
•  » » 3 years ago, # ^ |   0 Problem C: https://youtu.be/hEsuRDgmo_8 Problem D: https://youtu.be/aqVF3vpiERE
•  » » » 2 years ago, # ^ |   0 thanks for the peculiar tree explanation . i am trying to understand this problem for a long time.
 » 3 years ago, # |   +48 so where is the solution of div1.E?`
 » 3 years ago, # |   0 Is the formula in a 944B problem for finding the number of (min + 1)s is correct? // leftSum — minSum ?
 » 3 years ago, # |   +39 "The analysis of the last problem will soon be added." KAN Excuse me, sir?
 » 3 years ago, # |   +36
 » 3 years ago, # |   0 Plz help me why the answer of test case 45 is 50here is my submission 36503648
 » 3 years ago, # |   0 Hello everyone.For the problem 944 E, my code gets WA at test case 3.This is my code- http://codeforces.com/contest/930/submission/38547479I would like to know the error in my code.For every index i, I'm taking the sum of longest non-decreasing subsequence ending at i, and the longest non-increasing subsequence starting at i, minus 1.
 » 8 months ago, # |   +1 In 931D - Peculiar apple-tree Here's how the tree looks for the second sample test case