maroonrk's blog

By maroonrk, history, 3 weeks ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +77
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +114 Vote: I do not like it

As one of the Writers, I hope all participants enjoy the contest. Good luck!

»
3 weeks ago, # |
  Vote: I like it +109 Vote: I do not like it

As one of the writers, good luck and have fun!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

But there might be a small problem of time,becase COMPFEST 14 — Preliminary Online Mirror will begin at 21:35(UTC+8 for me)

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Does anyone see the tasks?

»
3 weeks ago, # |
Rev. 3   Vote: I like it -164 Vote: I do not like it
Spoiler
»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Is problem E a famous problem ? djq_fpc solved it in 10min ...

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I've catched logic but i've not solved A because of my low in programming language.So sad...

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

great problems

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Idk why but problems A and B felt very familiar to me. I even thought I opened some old contest by mistake.

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    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$$$.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please elaborate?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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   Vote: I like it +1 Vote: I do not like it

O((2N + Nlog₂N) ∙ 2log₂1e7) solution for C using a weird kind of Binary Search.

submission

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i notice someone use a ternary search, so maybe it does have something to do with convex

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Really strange. My ternary search get WA.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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   Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes. But can l=min{L},r=min{R} work forever(for any testcases)? Are the testdatas too weak?

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
              Rev. 2   Vote: I like it +6 Vote: I do not like it

              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
              
              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks ago, # ^ |
                  Vote: I like it +6 Vote: I do not like it

                To handle this problem, we should carefully choose the proper function in ternarysearch.

                My code here could be work.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain your approach?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In editorial of C, how to recursively calculate C?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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]) + C

    Explanation 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it +22 Vote: I do not like it

    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   Vote: I like it +6 Vote: I do not like it

      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

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve task B?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    please help anyone _ /\ _ , i really dont understand editorial of task b.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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$$$.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone get why the reverse works in problem F editorial [2]? I tried calculating some cases and it works but it seems there is some intuitive explanation that cannot be found by the formulas.