PROBLEM LINK:
Contest link: ICLFIN06
Author
Tester
Editorialist
DIFFICULTY:
HARD
PREREQUISITES:
Graphs, DP
PROBLEM:
Hexabot moves in a series of one-sixth 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.
r(n) = first nth root of 1 = e2*pi*i/n
w = r(3)
There are 6 directions in which the robot can be facing
d(i)=r(12)^(2i+1) where 0<=i<=5
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 (d,z)
If the robot moves clockwise,
(d(i),z) -> ( d((i-1)%6), z + r(6)^i)
If the robot moves anti-clockwise,
(d(i),z) -> ( d((i+1)%6), z + r(6)^(i+1))
Now we can convert this problem to a simpler problem:
Consider a hexagon with vertices marked from 0 to 5
The edge joining the adjacent vertices i and (i+1)%6 is the increase in z when going from d(i) to d((i+1)%6) or when going from d((i+1)%6) to d(i) (you can verify that both will be the same)
e(i,(i+1)%6) = r(6)^(i+1)
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.
e(0,1) = r(6)^1 = 1+w
e(1,2) = r(6)^2 = w
e(2,3) = r(6)^3 = -1
e(3,4) = r(6)^4 = -1-w
e(4,5) = r(6)^5 = -w
e(5,0) = r(6)^0 = 1
Let r(6)^i = p(i)+q(i)*w, where p(i) and q(i) are integers
(We can store p(i) and q(i) in arrays, p=[1,1,0,-1,-1,0], q=[0,1,1,0,-1,-1])
Let f(k,n,a,b) be the number of ways to reach vertex k from vertex 0 in n steps such that path sum is a+b*w.
Then f(k,n,a,b) = f((k-1)%6, n-1, a-p(k), b-q(k)) + f((k+1)%6, n-1, a-p((k+1)%6), b-q((k+1)%6))
In f(k,n,a,b), a and b can be atmost n
Base case n=0:
f(k,0,a,b) = 0
f(0,0,0,0) = 1
Using this we can 3D DP a solution.
Memory complexity:
O(n3)
Time complexity:
O(n3+T)