### maroonrk's blog

By maroonrk, history, 3 weeks ago, We will hold AtCoder Regular Contest 147.

The point values will be 300-500-600-700-800-1100.

We are looking forward to your participation! Comments (46)
 » As one of the Writers, I hope all participants enjoy the contest. Good luck!
 » As one of the writers, good luck and have fun!
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   I tried first time at Atcoder , i realised that problems level is higher than codeforces. is it?
•  » » » It wasn't this time
 » But there might be a small problem of time,becase COMPFEST 14 — Preliminary Online Mirror will begin at 21:35(UTC+8 for me)
 » Does anyone see the tasks? •  » » Yes, I see it.
»
3 weeks ago, # |
Rev. 3
Spoiler
•  » » Cheater?
 » Is problem E a famous problem ? djq_fpc solved it in 10min ...
•  » » It's a simple greedy
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   E is an enhanced version of this problem https://www.51nod.com/Challenge/Problem.html#problemId=1328
 » I've catched logic but i've not solved A because of my low in programming language.So sad...
 » great problems
•  » » can we see tags of Problem at Atcoder ,someone please?
 » Idk why but problems A and B felt very familiar to me. I even thought I opened some old contest by mistake.
 » Would anyone like to share more details about problem C? I think I have reached the step that the distance between the leftmost point and rightmost point should be as small as possible, but could not figure out how to handle the other n-2 points.
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   Do your process recursively to minimize $(N-1)(x_N-x_1)+(N-3)(x_{N-1}-x_2)+(N-5)(x_{N-2}-x_3)\cdots$.
•  » » » Can you please elaborate?
•  » » » » When $x_1\le x_2\le \cdots \le x_N$, the answer is: $(x_2-x_1)+(x_3-x_1)+(x_4-x_1)+\cdots+(x_N-x_1)+\\ (x_3-x_2)+(x_4-x_2)+\cdots+(x_N-x_2)+\\ \vdots \\ (x_N-x_{N-1})$You just need to organize this well. Each row $i$ means $\displaystyle \sum^N_{j=i+1}|x_j-x_i|$.Sorry for my bad english.
 » I put two wrong submissions submission1 and submission2 together and got an accepted submission. Can someone provide a hack and put it in the after_contest_tests? Thanks a lot.
 » 3 weeks ago, # | ← Rev. 2 →   O((2N + Nlog₂N) ∙ 2log₂1e7) solution for C using a weird kind of Binary Search.submission
•  » » I think it's possible because the graph is convex. I considered about it at first, but I didn't dare to succeed with binary search, so I chose a different way.
•  » » » i notice someone use a ternary search, so maybe it does have something to do with convex
•  » » » » Really strange. My ternary search get WA.
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   If I change that code and use l=0,r=1e7 instead of l=min{L},r=min{R}, it can't even pass the sample.
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   For the first test case, if you use l=0 and r=1e7 as the bounary of ternar search, you will get lmid=3333334 and rmid=6666667, and the function you check will get the same anwser (which is 6), it won't help you to choose which part will be removed.
•  » » » » » » Yes. But can l=min{L},r=min{R} work forever(for any testcases)? Are the testdatas too weak?
•  » » » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   Some kind of ternarysearch could be hacked, if they calc the total distances in ternarysearch. Because the function of total distances could have a platform in searching before geting the minimum region.Below test case should return 493, but the passed code return 496. 6 1 3 3 4 5 6 5 6 5 6 101 108 
•  » » » » » » » » To handle this problem, we should carefully choose the proper function in ternarysearch.My code here could be work.
•  » » » » » » » » » Orz
•  » » Can you please explain your approach?
•  » » » Since the dissatisfaction level is related to every pair of people, the optimal solution will be to let everyone stand as close to a single point as possible.After experimenting around with the points, we can see that as we increase our chosen point, the total score will decrease to a trough, then increase again.Therefore, we can implement a modified binary search that compares neighboring values (or a ternary search) to find the point that minimizes the value of this upward-concave curve, which will be the minimum dissatisfaction value.
 » In editorial of C, how to recursively calculate C?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   let i be the index for which minimum of R exist and j be the index for which maximum of L exists. If we do not consider those two then i and j will be not in the optimal solution. let A[i] = R[i] = minimum of all R and B[j] = L[j] = maximum of all L. assuming A[i] < B[j], all other k where k != i and k != j we can do x[k] — A[i] + B[j] — x[k] = B[j]-A[i]. so the cost = B[j] — A[i] + (N-2)*(B[j]-A[i]) + C = (N-1)*(B[j]-A[i]) + CExplanation of C: Now waht we need do is solve the same problem for all others except i and j that is to find the minimum of R and maximum of L for the indices k where k != i and k != j. This is C as far as i understood.
 » looking forward to some alternative solution to C. the one in editorial is elegant but hard to come up with (
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   You can use the fact that the answer is minimized when there is some $p$, all $x$ is placed as close to $p$ as possible. This can be proved by contradiction. To calculate the answer, consider rewrite the answer as $\sum\limits_{i=-\infty}^{\infty} ((\sum\limits_{j=1}^n[x_j\leq i])\cdot (\sum\limits_{j=1}^n[x_j>i]))$, then we can iterate over all possible $p$ and calculate the answer. You can also find that the answer is optimized when $p=L_i$ or $p=R_i$ or $p=R_i+1$ for some $i$, then the solution is $O(n\log n)$.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   thanks for sharing. i agree with your general idea, but i still don't understand the specific solution. especially your formula that i tried several ways to understand but none of them seems reasonable, it's a little strange for me(the square bracket is one reason and does $\cdot$ really mean multiply here?). also why we need to consider $R_i + 1$ ? what about others ?(maybe L-1?,etc)sorry that the question I ask might seem kind of stupid, hope for reply
•  » » » » Consider the $x_i$ are coordinates on the number line. Then the original formula means the distance between all pairs of points. We consider all segments of length $1$ on the number line, say $[i,i+1]$, then the contribution of it to the original formula is the number of points to the left of $i$ multiplies the number of points to the right of $i+1$, which is the formula above.Actually I'm not sure what are the key values that $p$ will choose. During the contest I just implemented a solution run in $O(10^7)$, and I implemented the $O(n\log n)$ solution later. I picked keypoints based on changes in variables, so maybe some of $p=L_i, p=R_i,p=R_i+1$ are not necessary, but these must be sufficient.
•  » » » » » got it, thanks a lot
 » I came up with a ternary search algorithm in $O(n\log n\log \max{R_i})$ time after the contest, but I can't prove that. Can anyone explain why this works? submission
 » how to solve task B?
•  » » please help anyone _ /\ _ , i really dont understand editorial of task b.
•  » » You can put the numbers with odd indexes into array $P_1$ and the others into array $P_2$.For example,$P={5,3,1,2,4}$,the initial state:$P_1={5,1,4},P_2={3,2}$the final state:$P_1={1,3,5},P_2={2,4}$Doing operation A can swap elements $a,b$ ($a\in P_1,b\in P_2$),and doing operation B can swap elements $c,d$ ($c,d\in P_1$ or $c,d \in P_2$).Note that some elements are not in the correct array.If $a\in P_1,b\in P_2$ in the initial state and $a\in P_2,b\in P_1$ in the final state,do operation A to swap $a,b$.Then we make the number of operation A the minimum.And now you can use operation B to sort $P_1,P_2$.
•  » » » got it thanks (:
 » Does anyone get why the reverse works in problem F editorial ? I tried calculating some cases and it works but it seems there is some intuitive explanation that cannot be found by the formulas.