noobboyyyy's blog

USACO PROBLEM DP Knapsack with Number Theory
By noobboyyyy, history, 4 years ago, In English

Problem Link :http://www.usaco.org/index.php?page=viewproblem2&cpid=1043 My approach was let we will store the K in vector for Each i [1...N] now let say n+1 can be represented as sum of x+y i:e n+1= x+y so answer will be set[n]=Lcm of (Set[x],Set[y]) for every unique pair of x,y but this solution is not working can anyone give correct solution

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The way I solved it: You can divide the permutation in cycles, and the LCM of the cycle lengths of a certain permutation will be a valid K. It can be shown that all K that can be achieved for N cows, can be made of only cycles of length $$$p^k$$$ where p is a prime number, and cycles of length 1. With this observation you can make a DP state of

$$$DP[n][q] = $$$ sum of all valid K's of all permutations of length n where you only used cycles of 1, and $$$p^k$$$ for all primes $$$p \leq q$$$.

The recurrence will then be: $$$DP[n][q] = DP[n][p] + \sum DP[n-q^k][p] \cdot q^k$$$, where p is the previous prime number.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Didnt understood this line : 

     can be made of only cycles of length pk where p is a prime number, and cycles of length 1

    as for Ex n =5 how is LCM 6 is achieved

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      If you have cycles of $$$2^1$$$ and $$$3^1$$$, then you get that the LCM of the lengths of cycles is 6, and the sum of cycles is n=5. Also for the DP, to account for cycles of length 1, you set $$$DP[j][1] = 1$$$ for all $$$0 \leq j \leq n$$$.

      → Reply