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.


Link to problem:
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.
Thanks in advance.
@gkcs I'll be glad if you help me :)

asked 11 Nov, 22:12

ashigahlawat's gravatar image

0★ashigahlawat
152
accept rate: 0%

edited 11 Nov, 23:15


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][0] = 1, f[A, B, C][0] = 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).

link

answered 12 Nov, 00:12

ashigahlawat's gravatar image

0★ashigahlawat
152
accept rate: 0%

edited 12 Nov, 02:35

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:

×1,292
×882
×444
×166
×136
×102
×82

question asked: 11 Nov, 22:12

question was seen: 71 times

last updated: 12 Nov, 02:35