This was a rather tricky problem listed here that would not run quickly for a standard BFS. So the name of the game was "OPTIMIZE', especially given the time constraint of 1 sec and for some solutions having no. of moves greater than 20.
The crucial thing to realize is that iterating 9 decisions(1 for each key) will not work for large depths, so we need to prove keys that are repeated more than 3 times, since using a key for 4 will bring the clock back to the same position.
After this, to represent a state of 9 clocks, we can use just 2 bits for each clock, for a total of 18 bits(which can be fit in a java int). But how can I fit in 12 0 clock in 2 bits (won't it take 4 bits)? Actually you can't but that's not a problem since the clock can only be in 4 states so representing 00 as 12'0clock, 01 as 3'0clock and so on will work. This will make your final state be 0 since all clocks are then at 12 o'clock. After this you need some bit mask magic to change the state for a clock. (This is a bit non-trivial since we're changing 2 bits, but is still pretty very doable). If you're unfamiliar with bitmasks, check out bmerry's article at topcoder here.
We also need to add memoization to our BFS to make sure repeated states are not processed. Again, we can use an int to to represent a state of clocks similar to what we just saw.
I also discovered that using an ArrayDeque instead of a LinkedList for my Queue implementation speeded up things by about 20%, even though both are supposed to work in O(1). I believe this is because ArrayDeque does not resize it's elements as often as LinkedList, but I haven't confirmed this. Everything else is just straightforward BFS. Here's the code:
The crucial thing to realize is that iterating 9 decisions(1 for each key) will not work for large depths, so we need to prove keys that are repeated more than 3 times, since using a key for 4 will bring the clock back to the same position.
After this, to represent a state of 9 clocks, we can use just 2 bits for each clock, for a total of 18 bits(which can be fit in a java int). But how can I fit in 12 0 clock in 2 bits (won't it take 4 bits)? Actually you can't but that's not a problem since the clock can only be in 4 states so representing 00 as 12'0clock, 01 as 3'0clock and so on will work. This will make your final state be 0 since all clocks are then at 12 o'clock. After this you need some bit mask magic to change the state for a clock. (This is a bit non-trivial since we're changing 2 bits, but is still pretty very doable). If you're unfamiliar with bitmasks, check out bmerry's article at topcoder here.
We also need to add memoization to our BFS to make sure repeated states are not processed. Again, we can use an int to to represent a state of clocks similar to what we just saw.
I also discovered that using an ArrayDeque instead of a LinkedList for my Queue implementation speeded up things by about 20%, even though both are supposed to work in O(1). I believe this is because ArrayDeque does not resize it's elements as often as LinkedList, but I haven't confirmed this. Everything else is just straightforward BFS. Here's the code:
Excellent explanation, really helped. Thank you!!
ReplyDeleteThank you so much for taking the time to write this. I was getting so frustrated at the timeout I was getting on the later test cases!
ReplyDelete