maroonrk's blog

AtCoder Regular Contest 147 Announcement
By maroonrk, history, 2 years 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

Comments Comments (39)
| Write comment?
»
2 years 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!

→ Reply
»
2 years ago, # |
  Vote: I like it +109 Vote: I do not like it

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

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I tried first time at Atcoder , i realised that problems level is higher than codeforces. is it?

    → Reply
»
2 years 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)

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Does anyone see the tasks?

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it -164 Vote: I do not like it
Spoiler
→ Reply
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it

great problems

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

    can we see tags of Problem at Atcoder ,someone please?

    → Reply
»
2 years 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.

→ Reply
»
2 years 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.

→ Reply
  • »
    »
    2 years 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$$$.

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

      Can you please elaborate?

      → Reply
      • »
        »
        »
        »
        2 years 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.

        → Reply
»
2 years 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.

→ Reply
»
2 years 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

→ Reply
  • »
    »
    2 years 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.

    → Reply
    • »
      »
      »
      2 years 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

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

        Really strange. My ternary search get WA.

        → Reply
      • »
        »
        »
        »
        2 years 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.

        → Reply
        • »
          »
          »
          »
          »
          2 years 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years 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?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years 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
              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                2 years 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.

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

    Can you please explain your approach?

    → Reply
    • »
      »
      »
      2 years 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.

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In editorial of C, how to recursively calculate C?

→ Reply
  • »
    »
    2 years 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.

    → Reply
»
2 years 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 (

→ Reply
  • »
    »
    2 years 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)$$$.

    → Reply
    • »
      »
      »
      2 years 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

      → Reply
      • »
        »
        »
        »
        2 years 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.

        → Reply
»
2 years 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.

→ Reply