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

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

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.)

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

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

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

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

How to solve D?

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

    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.

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

      Nice solution, thanks!

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

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

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

        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.

        → Ответить
        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
          ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

          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?

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

How to solve C?

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

    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.

    → Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +16 Проголосовать: не нравится

    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.

    → Ответить