I am stuck with this question of codeforces- Problem - E - Codeforces
I read the editorial. Can’t understand, how they are solving it without dp. Can anyone help?
It’s quite standard dp question. Let’s say initially ant was somewhere outside tetrahedron.
Now it should get at 'D' first becuz we need to start from there. Now ant can roam anywhere
unless number of moves remains is '2'. At this time ant cannot be at position 'D' becuz in next and final step we need to get at 'D'.
Let define dp[A,B,C,D][x] such that we are about to go {A,B,C,D} and moves remain (n-x);
Base case will be dp[D][0] = 1 as from outside first ant will go on pos 'D'.
i am linking solution try to summarize else ask again.
Solution – https://ideone.com/vrbwkM
Also use modulo arithmetic while submitting. i didn’t take care for that.
EDIT : i gave O(n) solution. The intended solution requires faster solution. so you can optimize dp relations which i stated. i guess the relations can be solved by matrix power. if you didn’t get anything ask.
Let A(n), B(n), C(n), D(n) be the number of ways the ant is at points A,B,C,D after n moves respectively. As the ant was at D, the ant has equal probability of going to A,B or C…Hence A(n)=B(n)=C(n)
Now after n+1 moves,
D(n+1)=3B(n) ( For the ant to be at D after n+1 moves,D(n+1)=A(n)+B(n)+C(n) );
B(n+1)=A(n)+C(n)+D(n) = 2B(n)+D(n)…
get a recurrence relation in one variable and iterate it to get the required ans…