Help Needed

1

Can this problem be solved using DP? I have an idea for this but couldn’t get an AC
#my idea
def dp(d,k):

if(d<k-1):

    if(d==0):

        print("YES")

        exit()

if d>=k:

    x=dp(d-k,k)

if d>=k-1:

    x=dp(d-(k-1),k)

if(dp(9,6)==None):

print("NO")
2

This question doesn’t exibit any DP feature i.e overlapping subproblems and optimal substructure. So, it can’t have a DP solution.

Moreover, DP is an optimization technique applied on maximization, minimization or counting problems. This question just asks whether it has a solution or not.

3

Yes this question can be treated as DP but real crux of this problem is solving each testcase in O(1).
Treating this question as Knapsack Problem this is the solution by my friend using DP: CodeChef: Practical coding for everyone .

Hope this will be helpful to you!

4

Just to save your space and typing: https://www.codechef.com/viewsolution/42887425

5

Thank you for your response. But I would like to know why my approach is not working. Can you help me with that

6

i have also did this problem with dp : CodeChef: Practical coding for everyone,
can you tell the idea to solve in O(1) time