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

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

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

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

How to solve D?

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.Nice solution, thanks!

Why the second part of the sum is multiplied with

`i`

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

How to solve C?

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.

Observations:

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

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