Getting MLE on optimal game strategy -II

#1

here is my sol https://pastebin.com/TRZwe5cd

just curious what is memory limit for this problem?

#2

You cannot make an array of size 10^4*10^4 which is equal to 10^8 in coding competitions.
The total memory given by most of the Coding sites have a memory limit of 256MB .
HERE you are making an integer array of size 4bytes per integer *10^8= 400MB.
SO you can try to use map as an array as all the possibility will reduce quickly and your solution will be calculated in the memory constraints. It is a very good technique to optimize memory constraints.

#3

thanks for details. here is after using unordered_map https://pastebin.com/tvKLxjxu i am still getting TLE on last 3 subtasks.

#4

@amankumarkeshu, @knakul853,
My bottom up code works fine with O(n^2) vectors. Link.

#5

Yeah the allocation in be vectors and arrays is different. Also you are not making recursive calls so it also reduces space.

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.