Help with this problem

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

Post Reply
andrepcg
New poster
Posts: 1
Joined: Mon Mar 02, 2015 3:03 am

Help with this problem

Post by andrepcg » Mon Mar 02, 2015 3:08 am

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!

Post Reply

Return to “Other words”