CF Problems: 2020 Mar. ~ Apr.

Problems are sorted from most recent to least recent

FFT, String Matching: 1334G
When we want to matching two string with more flexible criterion, we can try to come up with some formula $f$ for comparing two character where $f(u, v) = 0$ only when $u = v$. In this case, $(s – t)^2 (s’ – t)^2$ can be a good choice. After expanding the equation, we only need 3 FFTs to get the answer.

Bitmask, SOS DP, Brute Force: 1326F2

There are several techniques that we could use in this kind of problems: DP over subset/superset. Usually we can solve the “superset” version of a problem easier than itself. Like in this case, if we only care about the string location that must be 1, we only need to care about each component.

Then we can realize the split of the component (i.e. the partition of the sequence) can be at most as $P(18) = 385$ (recall NAC20J, which uses P(30) = 5040), and each split, no matter how ordered, has the same number ways to achieve. Then we can solve for each configuration and merge them together.

To merge them, we can use subset transformation (subset transform is for “OR”, superset transform is for “AND”) to make it easier to unite different component in a partition. When we get the answer, we can transform the result back from “superset” version.

One side note on the easier subtask is that it used the fact that $\sum_{k = 0}^{n} {{n}\choose{k}} 2^k = 3^k$ by binomial theorem. so we can do bitmask DP using two dimensional DP (one on the submask of permutation and another on the submask of string), which is $O(3^k k /2)$.

Leave a Reply

Your email address will not be published. Required fields are marked *