Блог пользователя rng_58

Автор rng_58, история, 5 лет назад, По-английски

We will hold diverta 2019 Programming Contest 2.

The point values will be announced later.

We are looking forward to your participation!

By the way, now you can reach here from AtCoder:

  • Проголосовать: нравится
  • +146
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

time link is broken

»
5 лет назад, # |
  Проголосовать: нравится +146 Проголосовать: не нравится

That discuss tab/link is an amazing idea!

»
5 лет назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

I earlier thought that Atcoder came up with new discussion forum, but when i cliked the link, I was like LOL.

»
5 лет назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Practical

»
5 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Are favs bound to the device? I don't understand why do I have different fav lists on my pc and my laptop while being on the same account.

»
5 лет назад, # |
Rev. 5   Проголосовать: нравится +21 Проголосовать: не нравится

Announcement: it's 17:20 in Japan timezone, so less than 4 hours to start!

This is my first time to write one or more problems in a contest which is rated and not a Beginner Contest. I'm looking forward to your participation :)

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

So, are AtCoder Regular Contests permanently replaced by sponsored contests ?

E869120 and square1001 did a great job as usual in setting the Problem F. Although I had no idea in how to solve the problem, I immediately understood the editorial. It was such a nice Mathematical problem. Strangely, it reminded me of Tashakashi's Information (ABC088 C) and Five, Five Everywhere (ABC096D).

Both those problems had short, surprising constructive solutions. They were elegant and had the aha! factor. I believe this F Had it too.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +35 Проголосовать: не нравится

    I'm not sure if this is permanent, but at least majority of ARCs will be replaced by sponsored contests. The difficulty/quality of problems will be the same for all ~2799-rated contests, regardless of the names of the contests.

»
5 лет назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

Codeforces is Atcoder's mentor??

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Wish everyone can get a high rating:)

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve B? Any ideas?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Obviously, (p, q) should be the difference between two balls' coordinates, since otherwise we'll never be able to acquire a ball at zero cost (and our answer would be N). Iterate over every pair of balls and let (p, q) be the difference between their coordinates. Then, for each such (p, q), iterate over every ball and determine whether we can collect it at zero cost. (We can do so if and only if there exists a ball at (x-p, y-q): since there can be only one ball at each point, we know that we can collect (x, y) right after (x-p, y-q).) That lets us determine the minimum cost of collecting the balls given this pair (p, q), and our answer is the minimum of all of these values.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      For the third sample test case in problem B why is the answer 2. What are the values of p and q taken ?

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Take p=1, q=0, then collect the four points in the order #1, #3, #2, #4. #3 and #4 will then be free, so the answer is two.

        There are several more cases that work (p=0, q=1, and the order #1, #2, #3, #4, for example), but this gives a correct answer.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится -16 Проголосовать: не нравится

          but given that u r not allowed to take value 0 of any p & q !!

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

            We must have p != 0 or q != 0, so one of the two can be zero as long as they aren’t both zero.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится -16 Проголосовать: не нравится

          "We will collect all of these balls, by choosing two integers p and q such that p ≠ 0 or q ≠ 0 and then repeating the following operation:"

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I used union-find to connect balls with the same (p, q). 1. I first sort the balls first by x, then by y. 2. For all pairs of balls (i, j) where i < j, I compute (p, q) and check the cost. This gets WA on more than half the tests. Why?

      I know that it doesn't help the complexity to use only i < j pairs. But I thought that sorting would be enough to make it work.

»
5 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

What was the solution to F?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hint for C?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Here's a small hint that helped motivate my solution.

    Suppose we have three terms x, y, and z. After subtracting z from y, we get y-z, and after subtracting that from x, we get x-y+z. As you can see, the z is being added now, since it was subtracted twice. In general, subtracting a number an even number of times is equivalent to adding that number. Can we take advantage of this somehow?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will editorial come out?

»
5 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Solution for E?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Here's my solution, although the explanation may be a bit hard to follow.

    Let dp[i] be the ways to get at least one block to height i and then to order however many blocks end up on height i at some point. (We need to order them because we have to figure out the order in which we'll add blocks to these squares.) Then, dp[0] = N! since there are N! ways to arrange the blocks at point 0.

    Afterwards, dp[i] is the sum of the dp values from dp[i-1] to dp[i-D], since we can start anywhere from 1 to D blocks below, times the sum from 1! to N! (as we can bring any number from 1 to N of blocks up to height i and then we have x! ways to order their next steps).

    Then, our answer is dp[H] except at this step, we don't multiply by the factorials (as we won't be doing any future steps, so we don't need to order the blocks arriving at H).

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

After thinking C for over an hour, I find D a simple brute force.
QwQ

How to solve C?

»
5 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

Problem C(without answer reconstruction): https://codeforces.me/contest/1038/problem/D

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    I think problem in codeforces is little diffrent.I can't handle the situation of adjacent.Can somebody help me in this problem.

»
5 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I don't understand why my code passed the test cases for question B. More precisely, why does adding the following 4 lines make my code correct ?

pot.emplace(a,b);
pot.emplace(-a,b);
pot.emplace(a,-b);
pot.emplace(-a,-b);

My code

( Maybe it's because test cases are weak. )

Thanks

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I thought you could choose lines with different slopes for B, time to relearn reading.

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Oh wow, F is pretty similar to a problem that appeared in a Finnish contest recently, and I even realized that, but multiplied by $$$2^{\left\lceil log2(M)\right\rceil}$$$ instead of M at every step. Too bad, with that this would have been my best-ever performance :/

Submission during contest, Accepted submission after contest

»
5 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I dont understand statement problem D :( . But tasks were interesting thanks to the authors.

»
5 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

E869120 and square1001 wrote problem F. How was it?

My solution is in the editorial and the max length of Hamiltonian Path will be $$$96 \ 755 \ 758 \ 040$$$. If we start induction from $$$N=3$$$ with setting edge length $$$1, 2, 3$$$, we can get more 'accurate' answer which max length is $$$83 \ 907 \ 014 \ 282$$$.

However, when I saw the submissions, most people solved in different ways to writers' one. Also, I am curious how short the optimal answer is, because writers/admins could not find the solutions which score is less than $$$6\times 10^{10}$$$ :)

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    why u wrote so short editorial for F, while in japanese its too long. why partiality?

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      That's because square1001 wrote a detailed editorial of problem F, and evima, who usually translates the problem statement in AtCoder, wrote English editorial of F.

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится -43 Проголосовать: не нравится

        since evima is not so active on cf, tell him to write proper editorials from the next time. Cutting his job short is not good.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +28 Проголосовать: не нравится

          But some people even in Japan are saying that English editorial is more simple and it means better. So I think that this is just an opinion difference to evima and square1001.

          I personally think that it is good to write every steps of approach which the writer and/or editorialist used to solve the problem. That's why I wrote 5 + extra 1 step of ideas to complete the Japanese editorial.

          But some people think differently — they think that editorial is the best if they could tell "how to get AC" in the most simple way.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

    Apparently my solution produces a better one, with maximum path cost $$$49721430711 \approx 5 \cdot 10^{10}$$$:

    distances

    Edit: And the improved solution from my post below, with maximum path cost $$$45201300642 \approx 4.5 \cdot 10^{10}$$$

    distances
    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Great solution.
      How did you find this answer?

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        It seems there are two differences to the solution in the editorial:

        Firstly, I have the "optimal" (minimum maximum value) list of values for every size:

        values

        Finding them took a few seconds with a simple brute force:

        brute code

        Secondly, instead of building inductively by adding edges to all previous nodes multiplied by M, I add edges from the first node to the other ones, then from the second to later ones, and so on, each time multiplied by the product of the sum of the two longest edges for every previous node. This works by the same argument, but we end up multiplying smaller values.

        Here's the submission: code

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +10 Проголосовать: не нравится

          Why do you think that we multiplying smaller values? Your value covers all subsets of edges with no more than 2 edges from each group, while authors solution covers only interesting subsets.

          I think that it is actually worse, because I was doing the same thing, but with bad values (like in editorial), and it wasn't enough ($$$1.36 \cdot 10^{11}$$$). I had to use different values for one group, so that only sums of two are different (and all numbers different). We can do this because after decoding all other groups we know the exact number of edges we need. And that helps only if the size of group is 5, 6 or 7 (not more).

          Also I don't understand why you multiply by sum of two maximums, not sum of two maximums + 1 (and the same question for solution from editorial). You know, when we use 10-based system, we multiply by the largest digit + 1, not by the largest digit.

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

            I actually didn't even realise I wasn't adding 1. It isn't a issue here though, since if the total length is exactly some multiple of b, we know the contribution from the earlier nodes is exactly b, since it is at least 1 and not more than b, and the contribution from later nodes is divisible by b.

            Note that by doing it in this order you cannot find the maximum cost of hamiltonian path, since at each step you add edges to nodes that you have not handled yet. So I think the approximation is necessary.

            It turns out the intuition about "multiplying smaller values" doesn't really work. But by constructing the graph like this, the maximum path is pretty easy to find: It always goes $$$1 \rightarrow 3 \rightarrow 5 \rightarrow 7 \rightarrow 9 \rightarrow 10 \rightarrow 8 \rightarrow 6 \rightarrow 4 \rightarrow 2$$$, since the lengths of the edges from every node are sorted by how large of an index the edge goes to, and it is optimal to take as many edges and as heavy edges from every node as possible, we get this greedy solution. So we end up taking one edge from every group of edges we add, and the multiplier will always be the second smallest value in the list of weights for that group. Additionally, b will be determined by the product of the sum of the two largest values in the suffix of lists.

            I ran the brute force again, firstly minimising the sum of the two last numbers in every list, and secondarily minimising the second smallest number. This gave the following values:

            values

            And the graph with maximum path cost $$$45201300642 \approx 4.5 \cdot 10^{10}$$$:

            distances

            Here's the submission

            The original values but using the maximum as in the editorial gives $$$75915624051 \approx 7.5 \cdot 10^{10}$$$ for the longest hamiltonian path: submission. The modified values (even though they weren't optimized for this use) give $$$69050411635 \approx 6.9 \cdot 10^{10}$$$: submission

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I used a similar idea, but with a worse sequence: $$$1, 2, a_i = a_{i-1} + a_{i-2} + 1$$$. My thought process: Well shit, the last two edges are too big. If it's just 1 edge, I can find the lengths of all paths that don't contain it, all paths that contain it and just bruteforce the minimum length of that edge such that no two paths' lengths coincide (using 2 pointers to check if a fixed length is ok). But it's 2 edges, so I'll just guess one of them and do that for the other. Distances:

    0 878 37673475840 5381925120 448493760 22424688 679536 12584 143 1
    878 0 6 10763850240 896987520 44849376 1359072 25168 286 2
    37673475840 6 0 21527700480 1793975040 89698752 2718144 50336 572 4
    5381925120 10763850240 21527700480 0 3139456320 156972816 4756752 88088 1001 7
    448493760 896987520 1793975040 3139456320 0 269096256 8154432 151008 1716 12
    22424688 44849376 89698752 156972816 269096256 0 13590720 251680 2860 20
    679536 1359072 2718144 4756752 8154432 13590720 0 415272 4719 33
    12584 25168 50336 88088 151008 251680 415272 0 7722 54
    143 286 572 1001 1716 2860 4719 7722 0 88
    1 2 4 7 12 20 33 54 88 0
    

    (6 is the guessed length here, there are other options). The max. length is pretty short, too.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Here you go! A solution with max. cost approximately $$$9 \cdot 10^9$$$.

    0 214 95963 4008331713 448493760 22424688 679536 12584 143 1
    214 0 3 2004429048 896987520 44849376 1359072 25168 286 2
    95963 3 0 1002019965 1793975040 89698752 2718144 50336 572 4
    4008331713 2004429048 1002019965 0 3139456320 156972816 4756752 88088 1001 7
    448493760 896987520 1793975040 3139456320 0 269096256 8154432 151008 1716 12
    22424688 44849376 89698752 156972816 269096256 0 13590720 251680 2860 20
    679536 1359072 2718144 4756752 8154432 13590720 0 415272 4719 33
    12584 25168 50336 88088 151008 251680 415272 0 7722 54
    143 286 572 1001 1716 2860 4719 7722 0 88
    1 2 4 7 12 20 33 54 88 0
    
»
5 лет назад, # |
Rev. 2   Проголосовать: нравится -52 Проголосовать: не нравится

Can someone explain. The sol of C

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +46 Проголосовать: не нравится

Problem A,B,C and E were written by me. Thank you for your participation!

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For the third sample test case in problem B why is the answer 2. What are the values of p and q taken

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

yuma_ satashun square1001

The editorial mentions that problem D can be solved using knapsack dp in $$$O(M)$$$ time where $$$M$$$ is the maximum amount of acorns/weight. Can you explain that DP ?

To update any state of DP, it takes $$$O(M/g)$$$ time where $$$g=$$$ cost of exchange

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    let dp[i] be the maximum amount of acorns we can get when we start with i acorns.

    As we can exchange multiple times, we can update dp from smaller side (like dp[i] = max(i, dp[i-g_1]+g_2))

    max (dp) can be as large as N * (g_2/g_1) for the first time, and we can afford the same dp for the second time