rng_58's blog

ExaWizards 2019
By rng_58, history, 6 years ago, In English

ExaWizards 2019 will be held on Saturday (time). The writers are semiexp and camypaper.

Contest Announcement

Contest duration: 120 minutes

Rated range: <2800

The point values will be 100 — 200 — 500 — 600 — 700 — 1200.

Let's discuss problems after the contest.

(Note: we noticed that it overlaps with SRM, but this is a sponsored contest and at this moment it's difficult to move it. Sorry about that.)

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

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

Does a special name indicate something? Or is it just an ARC?

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

    For non-Japanese, this is just a sponsored ARC.

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

How to solve D?

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

    1) sort the sequence S

    2) dp[i][A] which means the answer to the original problem for the prefix 1...i of S if the start number is X=A the transition is:

    dp[i][A] = dp[i-1][A%s[i]] + dp[i-1][A]*i

    the first summand is when s[i] goes first; the second summand is when it doesn't go first. In the latter case, the answer remains unchanged, because doing %s[i] on number <s[i] does nothing.

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

      Nice solution, thanks!

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

      Why the second part of the sum is multiplied with i?

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

        When you have some permutation of s[0],s[1],...,s[i-1]. You can insert s[i] before the first element, or at one of the i remaining spots.

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

          So, A remains unaffected if s[i] is inserted on any i positions other than first position.

          A changes to A%s[i] only when it is inserted before first position.

          Is this the correct interpretation?

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

How to solve C?

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

    Consider the operation backwards, maintain the positions that the golems would disappear, which is some prefix plus some suffix. Time complexity is $$$O(N+Q)$$$ since each upate takes $$$O(1)$$$ time.

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

    Observations:

    • If $$$i<j$$$ and $$$j$$$ is to fall off from left, then $$$i$$$ will also fall off from left.
    • If $$$i<j$$$ and $$$i$$$ is to fall off from right, then $$$j$$$ will too.

    So we can divide the sequence into 3 parts: $$$[1,L],[L+1,R-1],[R,N]$$$.

    • The left part will fall off from left.
    • The right part will fall off from right.
    • The middle part will remain.

    We can compute $$$L,~R$$$ using binary search.

    → Reply