Darshann's blog

By Darshann, history, 3 years ago, In English

https://codeforces.com/contest/118/problem/D

My code: https://pastebin.com/XbyR6Das

I am getting the correct answer for almost all test cases but it's failing for larger test cases. Can someone explain why this is happening? Also, there is some weird behaviour I'm noticing when I run this code on my machine in sublime text. For larger testcases (when n1==100 or n2==100), the output is changing if I increase the size of dp array from dp[101][2][11][101] to dp[101][3][11][101]. Is this because I am using excess memory or is there some other reason?

Full text and comments »

  • Vote: I like it
  • -2
  • Vote: I do not like it

By Darshann, history, 3 years ago, In English

1389B - Array Walk

I have recently started learning dp so I am only practicing writing memoized solutions rather than bottom-up dp. I had written a recursive solution for this problem but was not able to figure out the states for memoization as too many variables were changing k, z, etc. But after looking at some other submissions, I found out it was only enough to take the state to be curr_ind, z. I believed the state should include variables which are changing in transitions but here it's not the case and I am very confused.

Can someone please explain it to me how can we decide these states? TIA.

My submission: 117537731

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it