cschill's blog

765 Div. 2, Solved #C. with simple idea but need help
By cschill, history, 3 years ago, In English

Hello, so I tried to solve the problem C, with an idea similar to 01 Knapsack. I realized that the memory limit may exceed since its 505 * 505 * 505 which is greater than 1e8, but then I understood my solution and cutoff the unnecessary space. However, I am still getting a MLE. can anyone please help me.

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

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

In the worst case, size of your vector will still be 500*500*500.

Instead convert this code to iterative dp and then you can reduce the space ( since in transition for n you are only going to n+1, so for state n only previous States are required)

Here is the recursive solution similar to yours https://mirror.codeforces.com/contest/1625/submission/142496055

After that I converted this to iterative dp but still using all 3 states https://mirror.codeforces.com/contest/1625/submission/142510147

Here is my accepted solution using the idea described above ( removing redundant space for state n) https://mirror.codeforces.com/contest/1625/submission/142512319

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

During contest I also did with the exactly same approach and got MLE. But after removing last variable and using a loop instead of that I got accepted using recursion + memoization. Here is my code 142546595. Hope this would help. You can ask if you feel any difficulty in understanding :)

→ Reply