You are not logged in. Please login at www.codechef.com to post your questions!

×

Dp codeforces div2

1
1

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

asked 30 Nov '17, 17:08

manaranjanfav's gravatar image

4★manaranjanfav
235
accept rate: 0%

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.

(30 Nov '17, 17:18) underdog_eagle5★

same thing

(30 Nov '17, 17:32) manaranjanfav4★

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!

link

answered 01 Dec '17, 08:31

meooow's gravatar image

6★meooow ♦
6.5k517
accept rate: 49%

edited 01 Dec '17, 09:06

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,754
×220
×8
×4

question asked: 30 Nov '17, 17:08

question was seen: 818 times

last updated: 01 Dec '17, 09:06