Knapsack DP Help

Правка en3, от ProgrammerAlex, 2024-08-05 14:13:48

Hello, I am currently doing this question: https://mirror.codeforces.com/contest/837/problem/D

And I need some help. I came up with a good dp algorithm myself:

dp[i][j][k] means the maximum exponent of prime factor 2 we can achieve when we:

  1. choose from the first i integers in a

  2. choose a subset of length j from the first i integers

  3. the exponent of 5 is at most k

then, dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k-cur_exp5] + cur_exp2)

note dp[0][0][0] = 0 (don't have to initialize anything)

And implemented this algorithm in Python:

274520784

However, this code WAs for test case 8, with my answer of 11 being higher than the expected answer of 9. I have read the editorial for this question, and I believe the DP formula in the editorial is the same as my DP formula mentioned above (please correct me if I am wrong). Therefore, because I believe I have the DP formula correct, I am really confused on why this code still WAs. I know asking people to debug a code is sometimes annoying but I really tried everything and could not figure out why this code is not working, and I would really appreciate it if anyone could tell me why.

Thank you so much!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский ProgrammerAlex 2024-08-05 14:13:48 903
en2 Английский ProgrammerAlex 2024-08-05 14:11:57 12
en1 Английский ProgrammerAlex 2024-08-05 14:11:31 2112 Initial revision (published)