Page 1 of 1

Help with this problem

Posted: Mon Mar 02, 2015 3:08 am
by andrepcg
I have the following problem to solve: https://dl.dropboxusercontent.com/u/1197681/balls.html

I already solved with by storing the visited states in a map so I do not have to visit a particular state if I already visited it before, i fetch the value from the map and just add up. I don't know if my approach is the most correct and wanted your input.

More details about my implementation:
- Recursive
- The new recursive call receives a copy of the previous state but with the ball clusters already burst
- For any given state (eg: [1,2,2,1,3]), I hash the array and store the hash and the maximum points I can get with this state in the map so I can retrieve the calculated points if the same state (hash) is already in the map
- I can comment out the map code really easily and doing this makes it reach every possible branch giving me TLE so I must not visit states I already visited before

I wanted to solve this without the map but I knew I had to save the visited states but just didn't know how to it without the map. For example, if I have the state [1,2,2,1,3] how can i save that I already visited this particular state because it can contain up to 50 balls. For example, with the Fibonacci it's easy to see that I can store fib(20) in a simple array, i just store fib[20] = something , but for this problem I have up to 50 numbers and their order is important

I want to know how you would solve this problem. Thank you and I'm sorry if this is in a wrong section, new guy here!