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 '17, 22:12

ashigahlawat's gravatar image

0★ashigahlawat
152
accept rate: 0%

edited 11 Nov '17, 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 '17, 00:12

ashigahlawat's gravatar image

0★ashigahlawat
152
accept rate: 0%

edited 12 Nov '17, 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,402
×925
×479
×180
×140
×119
×104

question asked: 11 Nov '17, 22:12

question was seen: 197 times

last updated: 12 Nov '17, 02:35