You are not logged in. Please login at www.codechef.com to post your questions!

×

ICLFIN06 - Editorial

PROBLEM LINK:

Contest link: ICLFIN06

Author

Eklavya Sharma

Tester

Shubham Gupta

Editorialist

Eklavya Sharma

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)

PROBLEM SETTER's SOLUTION:

http://ideone.com/bqSOiX

This question is marked "community wiki".

asked 12 Apr '15, 07:40

sourabh13's gravatar image

2★sourabh13
16
accept rate: 0%

edited 23 Apr '15, 17:02

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,719
×2,181
×1,343
×1,228
×40

question asked: 12 Apr '15, 07:40

question was seen: 1,203 times

last updated: 23 Apr '15, 17:02