exawizards2019_c: Snuke the Wizard

Note that after the each operation, the relative position of golems with the same letter remains the same. This means the golems moved out will form two continous bands ends at the left and right end respectively (may overlap). So we just bsearch on each’s end points

exawizards2019_d: Modulo Operations

The only effective sequence is strictly decreasing. Therefore, we sort the set in decreasing order and do a knapsack-ish DP. Note the value is only 1e5, so it can fit into memory.

Consider the i’s step, f(x, i) = sum of results over all permutations, the permutation can be in two cases

  • s[i] is the first of the permutation, i.e., this part contributes f(x %s[i], i + 1)
  • s[i] is NOT the first of the permutation, i.e., it can be in any of the N - i - 1 positions, each of them is in effect an i + 1, case, i.e, this part contributes (N-i -1) * f(x, i+ 1)

1105D: Kilani and the Game

Just BFS on each player in turn, don’t expand if the neighbor is already colored. Also keep track to see if everyone can progress