helloworld1102's blog

Is my approach of 1512F (Education) using DP correct?(Does it make sense) if not why ?
By helloworld1102, history, 3 years ago, In English

Hello,there I know it's a irrelevant question to some of you .But, I want to ask as I have spent a long time and have a feeling that this DP approach could be correct(I think so) . But , yeah it could also be wrong and I want to ask why it can be wrong? So, yeah here it goes -->

Let dp(i,pos) = Min no of days to get money i and in getting money i optimally you reached the position pos.

And here will be the transitions according to me

dp(i,pos)--> dp(i + a[pos],pos) OR --> dp(i-b[pos],pos+1)

WHERE a and b are the arrays given in the question and the answer will be the DP[c][x] ( c is the total cost of new computer and x lies in range from position 1 to N in the array and we will take minimum dp of that.)

This is what I have thought of this question after spending some time . And I think time complexity will be in N^2 but I am interested whether this approach will lead to right answer. If not I really want to know the reason why it will fail?

I know some people can think it is rude to write a whole blog on it you can just ask in the comments but this round happened months ago so I will not get answer quickly.So I asked here.

Thank you everyone

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem Link

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I believe this can be an approach to solve this problem, but is not feasible to do so. The Time complexity will be O(c*n) not O(n*n). Which will get TLE.

Memory I think can be reduced from O(c*n) to O(c),but even after that we will get MLE.

→ Reply