rng_58's blog

AtCoder Grand Contest 026
By rng_58, history, 6 years ago, In English

AtCoder Grand Contest 026 will be held on Saturday (time). The writer is sugim48 and yosupo. This contest counts for GP30 scores.

Contest Link

Contest Announcement

Contest duration: TBD (about 2 hours)

The point values will be announced later.

Let's discuss problems after the contest.

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

»
6 years ago, # |
  Vote: I like it +31 Vote: I do not like it

The round starts in 2 hours.
Duration: 150 minutes
Point values: 200 — 600 — 600 — 1100 — 1600 — 2000

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

Is there a near-linear solution of E? Considering the solution is just substring construction: pick the last (number of 'b'-s minus number of 'a'-s) 'b'-s in some prefix, then while there's a 'b' before the last 'a' picked with 'b' so far, pick that 'b' too", then DP over substrings constructed this way, it feels like there could be a faster solution than O(N2) DP. For example, if we could decide which prefix to start with in O(1), that gives a linear solution instantly. And the prefix to start with is the one with maximum (number of 'b'-s minus number of 'a'-s), so the only ambiguity appears when there are more of them.

Also, my solution of B is funny: deal with obvious cases until there are no more obvious cases, guess that the answer's always "yes" or always "no" at that point, check the samples for which answer it should be.

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

    Yes, we describe O(N) solution in the editorial.

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

Are there English editorials for B and C?

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

    C: Meet in the middle. Generate all pairs of strings in the first half and in the reversed second half of the string for all 2N colourings in each case. For a valid colouring, it has to be the same pair — let's say that we have a pair (s1r, s1c) in the first half and (s2r, s2c) in the reversed second half; then |s1r| + |s2r| = |s1r| + |s1c| = N gives |s2r| = |s1c| and if ( means reversed string), then equal lengths mean s1r = s2c and equivalently s2r = s1c. Sort the pairs in each half and just compute the number of common pairs (of pairs). O(2NN2).

    B: it just works

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

    B: If A < B we lose immediately. If D < B, then each day the number of cans decreases, so we will lose some day for sure. Let's assume A, D ≥ B. If C ≥ B - 1, each night there are either more than C cans left, which is enough for Snuke to buy on the next day, or not more than C cans left, in which case we add D cans and Snuke can buy B cans on the next day. If C < B - 1, then the process looks like this: we take A modulo B, if it's greater than C, we lose, otherwise we add D and take the new value modulo B, check if it's greater than C again, and so on. In other words, we need to check if . To do that, replace D with . Then is the biggest value of which is less than B.

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

      Can you please explain the last part a bit, where we need to find maximum((A + kD) mod B)?
      Thank you

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

        That's just some basic properties of arithmetic progressions modulo n. Progression has different values and they have the form , where . Also, these values are "monotone" in the sense that they start with , increase until is greater than B, then they "overflow" and continue increasing, until we reach again. The maximum is achieved right before this "overflow" happens. So we need to find maximal k such that . We can solve this linear inequality and get that . We need maximal integer k that satisfies this inequality, so .

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

          I thought the same thing in contest timing but was stuck at the step where we have to find the maximum value of (A + k*D)%B ....

          I guess what I lacked was knowledge.. , was unaware of these "basic properties" as you call them..

          Can you give me some source where I can look some basic properties related to number theory like this one? Or some source where this is given?!

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

            In Russia this stuff is taught at schools, that's why I called it basic. I guess you could try googling "extended euclidian algorithm" or "linear diophantine equations in 2 variables".

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

              * in ~1% of schools

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

      In case anyone else was confused with case 1 :

      C>=B-1; A,D>=B

      You can view it this way, the only way the shopping could terminate is if we are left with a number which is greater than C, but smaller than B,we are stuck then. Mathematically, if there exists x, such that B>x>C, then the shopping could end .

      If we apply the condition C>=B-1, we see that there is no number which could cause the shopping to terminate. Hence then the shopping is perpetual for this case.

      Thank you aid for the amazing proof.

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

In problem D, the histogram can be abstracted as a tree of O(N) rectangles; this tree can be constructed easily in quadratic time and in a slightly more complicated way in .

Formulating the DP on the tree is quite clear: each subtree has a horizontal base, which can have alternating colours; if it does, then each row (of this rectangle) is alternating, otherwise each column is alternating. Alternating rows mean all the subtrees have alternating bases as well, alternating columns mean the subtrees can be coloured in any way. Therefore, we should compute two numbers for each rectangle/vertex/subtree: the number of colourings (of the subtree) and the number of these colourings where the base is alternating. The DP can be computed in ; see my code for the exact DP formula.

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

    How do you partition the histogram into rectangles?

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

      If you have some part of the histogram (left border, right border, base — bottom border), take the minimum of heights of columns between the left and right border; this will be the top border of the rectangle in the current node. Its subtrees are constructed recursively, for each maximum range (left border in son, right border in son) that contains only columns higher than the top border of the current rectangle.

      It's quite natural — take away the largest rectangle containing the whole bottom row, you're left with some connected components, recurse into them.

      The main advantage of this is that subtrees obviously don't affect each other and all interactions are only between a parent's and a son's horizontal edges.

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

        Aight that makes sense, thanks.

        P.S. Your code really is amazing :)

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

Can anyone explain about the solution of D-histogram coloring? I'm trying to solve this problem with two dp arrays as mentioned in the English editorial. I think this solution looks like a straightforward dp solution, but I'm having a difficulty in deriving the exact dp formula.

Thanks in advance.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it
    1. don't make fake accounts
    2. read comments before posting
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I read comments, but I'm looking for the dp solution without explicitly constructing trees. I think dp[i][j]=(number of ways to color all the grid in a histogram at column 1 to i, and j-th highest height to the highest row satisfying the given conditions) might solve this problem, but as I cannot derive the exact formula, I ask this question.

      If there's anything that I misunderstood, please let me know.

      Thank you for reading my comment.

      → Reply