Sort 31 Discussions, By:
Please Login in order to post a comment
My first DP problem. Enjoyed solving it. For people who are stuck with solving this. Please refer the below video and you'll be able to write logic in DP by yourself.
first solve on projecteular , then forum will provide different ways to tackle problem.
k = int(input())
for i in range (k):
l = int(input())
ways = *100001
ways = 1
for x in [1,2,5,10,20,50,100,200]:
for i in range(x, 100001):
ways[i] += ways[i-x]
I am getting correct answers for testcases 0 1 and 3, but everything is timeout. How can I optimize this? Thanks.
Initially, I didn't read "N is given as p and not £". I thought holy sh*t.
I made my program so optimised that it precalc. values upto £10^5 = 10^7p in 232ms on my machine. Later, while submitting I found that it's p. lol
Hint: Use memoization coinvalue-wise. And don't use Modulus opertor for adding. Check for overflow, if it overflow then subtract by modulus value. Modulus operator is costlier than branch followed by subtract.
at last solved in java.
BigInteger helps me a lot.
first solve for all 100000 possibilities and then only print answer directly.