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

×

# codeforces 166E help needed (binary matrix exponentiation) for a begineer

Just learnt Binary Matrix Exponentiation for Codeforces 166E problem from:
Youtube: Gaurav Sen's (gkcs) Matrix Exponentiation video
As there are a few blogs along with tutorial on codeforces itself for the problem, and some google results includes solutions as well. I have already read them but couldn't understand the base cases and the matrix formation that we will be multiplying with itself to some power , then using DP and finally multiplying with base cases matrix to obtain actual solution.
Probably they weren't beginners friendly or least I couldn't understand any of them.

# I will be glad if someone help me out explaining his solution, or a brief description would be fine.

Codeforces 166E
Couldn't think of any of the ways of solving 166E as defined in tutorial except recursive tree traversal solution which exceeded time limit obviously: My solution: 32205350
Will be glad to be guided if needs to learn something else.
@gkcs I'll be glad if you help me :)

asked 11 Nov '17, 22:12 875
accept rate: 0%

# I found this in comment section and finally got it,

Let Ai denote number of ways to finish near the vertex A after i moves (same for Bi, Ci, Di). Easily,
Ai = Di - 1 + Bi - 1 + Ci - 1
Bi = Di - 1 + Ai - 1 + Ci - 1
Ci = Di - 1 + Ai - 1 + Bi - 1
Di = Ai - 1 + Bi - 1 + Ci - 1
with the initial conditions
A0 = 0, B0 = 0, C0 = 0, D0 = 1
Due to the symmetry $A_i=B_i=C_i=ABC_i$, so
ABCi = Di - 1 + ABCi - 1 + ABCi - 1 = Di - 1 + 2  ABCi - 1
Di = ABCi - 1 + ABCi - 1 + ABCi - 1 = 3
ABCi - 1

# and

TETRAHEDRON : can this problem be think in a way that if u want to reach at D in n steps,
then to travel n — 1 steps 3 ^ (n — 1) ways possible, now this case include that if u reached at D in n — 1 steps
therefore to reach in n steps ans(in n steps) = 3 ^ (n — 1) — ans(in n — 1 steps);
which is a DP solution eg — to reach in 1 steps = 0 to reach in 2 steps — 3 ^ (2 — 1) — 0;
to reach in 3 steps — 3 ^ (3 — 1) — 3 = 6 to reach in 4 steps — 3 ^ (4 — 1) — 6 = 21
to reach in 5 steps — 3 ^ (5 — 1) — 21 = 60

# and

Let f[A][j] is the number of ways from D to A by going j steps,as same,f[B][j], f[C][j] and f[D][j],
we know f[D] = 1, f[A, B, C] = 0(because the ant starts at D).
then you get four equations below:
f[A][j] = f[B][j - 1] + f[C][j - 1] + f[D][j - 1]
f[B][j] = f[A][j - 1] + f[C][j - 1] + f[D][j - 1]
......
f[D][j] = ...
you can solve this problem in O(n),the answer is f[D][n] mod 1e9+7.
but it's too slow.you can express the four equations by matrix.then it's obvious to solve the problem by
matrix fast power algorithm in O(lg n).

answered 12 Nov '17, 00:12 875
accept rate: 0%

 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×2,212
×1,220
×688
×303
×166
×157
×153

question asked: 11 Nov '17, 22:12

question was seen: 759 times

last updated: 12 Nov '17, 02:35