ProgrammerAlex's blog

By ProgrammerAlex, history, 5 weeks ago,

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!

• 0

 » 5 weeks ago, # |   0 Auto comment: topic has been updated by ProgrammerAlex (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by ProgrammerAlex (previous revision, new revision, compare).