Dp codeforces div2

general
, , ,
1

http://codeforces.com/problemset/problem/895/C
Can anyone explain me the implementation of the dp

1 Like
2

I just got the first part of editorial in which we represent odd/even power(1 for odd and 0 for even) of primes in prime factorization of each integer in [1, 70] through a bitmask. After that I couldn’t understand a thing.

3

same thing

4

The dp state is f(i, j) which is, as the explanation says, the number of ways to choose some elements which are <= i from a, and their product has only those prime numbers in odd degree on whose index number j has 1 in binary representation.
Basically for f(i, j) you are given a limit i and a set of primes j. You have to calculate the number of ways in which one can choose any subset of the given a such that all the chosen numbers are \le i, and the set of primes appearing odd number of times in the product of the chosen subset is exactly j.

Let p_i be the set of primes appearing odd number of times in i. And let c_i be the number of times i occurs in a.
Now to calculate f(i, j), we can take i into a subset any number of times \le c_i, or not take it at all. Of course, if c_i = 0 then we have only one choice, not taking i. In that case f(i, j) = f(i-1, j).
But if c_i > 0, then think about how i affects the product of the subset.

  1. If we take i even number of times, then the primes appearing odd number of times in the product is unaffected by i since every prime factor of i will definitely occur even number of times. So this will contribute \text{ways to pick } i \text{ even times} \times f(i-1, j) to the total.
  2. But if we take i odd number of times, then the primes that appear odd number of times in i do have an effect, and may fill the required primes in j, or might add some primes that are not in j. This changes the set we call f(i-1, \cdots ) with from j to j \oplus p_i. So we calculate \text{ways to pick } i \text{ odd times} \times f(i-1, j \oplus p_i). If you’re wondering why xor operation is the right thing here, trying it with an example should help.

Now from combinatorics, \text{ways to pick } i \text{ even times} = \binom{c_i}{0} + \binom{c_i}{2} + \binom{c_i}{4} + ... = 2^{c_i - 1}. And \text{ways to pick } i \text{ odd times} is also 2^{c_i - 1}.

So finally,

f(i, j) = \begin{cases} 1 & \text{if } i = 0 \text{ and } j = 0 \\ 0 & \text{if } i = 0 \text{ and } j \ne 0 \\ f(i-1, j) & \text{if } c_i = 0 \\ 2^{c_i - 1} (f(i-1, j) + f(i-1, j \oplus p_i) & \text{otherwise} \end{cases}

The final answer is f(70, 0) - 1. The prime set is 0 because we don’t want any prime to appear odd number of times, and the -1 is to remove the empty subset which will always come in the answer.

Implementation here. This is different from the tutorial’s code in a few ways which I think makes it easier to understand. I have used the simple top-down approach whereas the tutorial’s code uses bottom-up dp that too in the “forward” manner. It’s a shame that the dp table in this code exceeds the small memory limit of 256 MB on Codeforces, so you will be forced to use a bottom-up solution where it is possible to optimize the memory usage by using only two rows instead of a table. It’s a nice problem combining many different ideas, so feel free to ask if any part of it is not clear!

5 Likes