PROBLEM LINK:Contest link: ICLFIN06 AuthorTesterEditorialistDIFFICULTY:HARD PREREQUISITES:Graphs, DP PROBLEM:Hexabot moves in a series of onesixth circular arcs (60°). At any point it can either move in a clockwise or an anticlockwise direction, but it cannot turn on the spot. It is allowed to cross its path and it is allowed to traverse an arc more than once (i.e. retrace a part of its walk). In how many ways can the robot return to its starting point in exactly n moves? EXPLANATION:We'll describe things on the complex plane. It's possible to solve this question without knowing anything about complex numbers and using vectors instead, but it is easier for me to explain using complex numbers. There are 6 directions in which the robot can be facing Robot's state can be described using 2 things : direction in which it is facing and a complex number denoting its position on the argand plane If the robot moves clockwise, Now we can convert this problem to a simpler problem: Consider a hexagon with vertices marked from 0 to 5 The original problem is equivalent to finding the number of ways in which we can walk this hexagon such that the path sum is zero. Now we will focus completely on solving this problem and not talk about the original problem.
Let Let Using this we can 3D DP a solution. Memory complexity:O(n^{3}) Time complexity:O(n^{3}+T) PROBLEM SETTER's SOLUTION:
This question is marked "community wiki".
asked 12 Apr '15, 07:40
