maroonrk's blog

We will hold "Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020".
By maroonrk, history, 5 years ago, In English

We will hold "Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020".

The point values will be 100 — 200 — 600 — 800 — 900 — 1100. We are looking forward to your participation!

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

»
5 years ago, # |
  Vote: I like it +44 Vote: I do not like it

Thanks for your participation!

I'll finish English editorial in some 30 mins.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +58 Vote: I do not like it

    English editorial is now available.

    Sorry for the delay, I had a lot of trouble with compiling tex templates.

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

D is very cool problem! How to solve E?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Obviously we can switch from sums to XOR of corners of a square. I wrote a bruteforce for any dimensions, not just powers of 2, and noticed that the answer seems reached when we equally distribute the 1s and 0s in the grid. I don't know how to prove it. The construction of that for a square is simple: the value in each cell is the parity of popcount(r AND c). For a rectangle, it's enough to repeat the square. This holds for 2D prefix sums, so we need to calculate the unsummed grid, of course.

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

Too much unbalance from B to C.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Well it did match the point distribution (you might know that the number of points a question is for is very closely related to its difficulty on atcoder, unlike codeforces)

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

Editorial Translation for C:

C: The negative condition is "pi;" pj divided by 3, so that both are 1, or pi; The pj is divided by 3, so that it is 2." The goal of this problem is to create a series of integers that are divided by 3 and are 1, and integers that are divided by 3 and are 2, so that they are not separated by 3 on the tree. First, paint red at vertices that are odd distance from vertex 1, and blue at points that are even. Then, because the given graph is a tree, the pairs of vertices with a distance of 3 are always red on one side and blue on the other. If both red and blue vertices are greater than N3, then assign one extra integer to the red vertices by 3, and then assign two extra integers by 3 to the blue vertices, then assign the remaining vertices a multiple of 3. Then, the condition is satisfied, so that the number divided by 3 is not equal to 1, and the number divided by 3 is not equal to 3. If the red vertices are N3 or fewer, assign a multiple of 3 to the red vertices in order, then divide the remaining 3 multiple by 3, and assign 1; more than two integers to the blue vertices. In this case, the condition is not satisfied, for example, if you divide by 3 and then divide by 3 and then divide by 3 by 2. If the blue vertices are N3 or fewer, assign a multiple of 3 to the blue vertices in order, then divide the remaining 3 multiple by 3 to assign 1; more than two integers to the red vertices. In this case, the condition is not satisfied, for example, if you divide by 3 and then divide by 3 and then divide by 3 by 2. Now you can configure a sequence that meets the criteria for all cases.

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

I had some hunch regarding D, where we used standard CHT but with some modification, that is, when we consider a line as visited then we could remove the line by overlapping the just next and previous lines in place of that line. Anybody can confirm?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    D is a exchange arguments problem, I don't think it has anything to do with CHT.

    You can solve it by sorting stores in decreasing order of $$$\frac{a_i}{b_i + 1}$$$, then looping over shops with $$$a_i > 0$$$, and calculating $$$DP[k]$$$: the minimum time to shop at $$$k$$$ stores. We may visit at most $$$\log T$$$ stores with $$$a_i > 0$$$, so this can be done in $$$\mathcal{O}(n \log T)$$$. Then loop ways to take some prefix of stores with $$$a_i = 0$$$ and some amount of stores with $$$a_i > 0$$$.

    Code

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

      Oh got it! Thanks!

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

      I arrived at exchange arguments too, but I got decreasing order of $$$ \dfrac{a_i}{b_i} $$$. What am I doing wrong? ( UPD: Read the editorial and figured this out )

      Also, I could only think of $$$O(N^2)$$$ dp, for each $$$i$$$ calculating best using $$$j \le i$$$. Can you give some more idea about the solution? my solution ( Ofcourse it TLE's, but I don't understand why it gives WA on some cases ).

      UPD: Didn't see your code before. I understand now, thanks.

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

C is one of the most interesting problems of tree colouring that I have seen.

→ Reply