Mikemirzyanov1's blog

By Mikemirzyanov1, history, 4 years ago, In English

I submitted this solution using memoisation but it gave memory limit exceeded. Can someone please help me how to do this problem using recurison??

My submission 77834554

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

| Write comment?
»
4 years ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

hi, the thing is that your states are not exactly okay. First you have a dp(pos, string you are creating) that means that for every position [1,N] you will have a 2^7 possible strings and you are storing them all. Also in this dp you do not really know how many k's you have left since you are not storing that anywhere. Try to see this problem as subset sum problem, being dp[pos][k] = true if there is a way to get a valid number using this k sticks. Now your dp will only give true or false and you can then only try to recover the possible string and always taking the biggest number that gives you a valid answer. For example if you call helper(0,k) and this gives true then there is at least one valid number and you can reconstruct it like this:

Spoiler

I modified some parts of your code to make it clear https://ideone.com/vKMsot , i submited it in cf but the judge is down now so i do not know if it gave ac or no, but i guess it will. You can also look at my code which is basically the same idea: https://codeforces.com/contest/1341/submission/77894917

edit: cf is up now and it got accepted https://codeforces.com/contest/1341/submission/77908699

hope it helps :)