naveen_1729's blog

By naveen_1729, history, 5 weeks ago,

Hi Fellow Coders,

Hope you are all doing good. This is my first blog. Today I gave Hackwithinfy test. I got asked a question similar to the standard DP problem which is Count the number of ways to make the change (repetitions of coins are allowed and order does matter). I know this problem can be solved in Quadratic time

O(N * W)

W — > Required Change

N — > Number of coins

But the constraints given in the problem are huge

1 <= N <= 10^5

1 <= W <= 10^9

1 <= A[i] <= 10^2 (A[i] — > stores the value of the coin)

I was so sure this would give me a TLE. But, I couldn't come up with a better approach than the standard one. I wonder if there is a better approach that would have given me an AC.

• +1

 » 5 weeks ago, # |   0 Auto comment: topic has been updated by naveen_1729 (previous revision, new revision, compare).
 » 5 weeks ago, # |   +8 Matrix binary exponentiation can be used to get $O(A^3log(W))$ time complexity where A = 100. The original dp can be written as $dp[i] = \sum_{j = 1,100} x_{j}*dp[i-j]$ where $x_{j}$ = no. of coins with value j.
 » 5 weeks ago, # |   0 Couldn't you give the problem link? I hope it's not from any ongoing competition. repetitions of coins are allowed and order does matter It would be not bad to give some examples.
•  » » 5 weeks ago, # ^ |   0 Sorry, bro. The test happened this morning on their website. I don't have access to the problems now. BTW this is not from any ongoing competition.