### rng_58's blog

By rng_58, history, 12 months ago, ,

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

 » 12 months ago, # |   +11 Does a special name indicate something? Or is it just an ARC?
•  » » 12 months ago, # ^ |   +36 For non-Japanese, this is just a sponsored ARC.
 » 12 months ago, # |   +13 How to solve D?
•  » » 12 months ago, # ^ |   +34 1) sort the sequence S2) 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]*ithe 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 
•  » » » 12 months ago, # ^ |   +8 Nice solution, thanks!
•  » » » 12 months ago, # ^ |   0 Why the second part of the sum is multiplied with i?
•  » » » » 12 months ago, # ^ |   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.
•  » » » » » 12 months ago, # ^ | ← 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?
 » 12 months ago, # | ← Rev. 2 →   +8 How to solve C?
•  » » 12 months ago, # ^ | ← 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.
•  » » 12 months ago, # ^ | ← Rev. 3 →   +16 Observations: If \$i