Tetrahedran codeforces que

#1

https://codeforces.com/problemset/problem/166/E

tell me this question concept also?

#2

Hey @ankit_verma
This is very simple DP problem

#include <iostream>
using namespace std;
#define mod 1000000007
#define ll long long

int main() {
    int n;
    cin>>n;
    ll a=0,b=0,c=0,d=1;
    for(int i=1;i<=n;i++){
        ll x=(b+c+d)%mod;  //a
        ll y=(a+c+d)%mod;  //b;
        ll z=(a+b+d)%mod;  //c
        ll D=(a+b+c)%mod;
        a=x,b=y,c=z,d=D;

    }
    cout<<d<<endl;
    return 0; 
    
}

So there can be 4 possible states of ant at any time
its at A or B or C or D
So We start with possible ways for n=0 at A=0,B=0,C=0 and D=1
So for n=1 we can go to A form B,C & D
similarly for rest
And finally for next iteration we update a,b,c,d with x,y,z,D

#3

i don’t understand why we this?

#4

What u didn’t understand exactly

#5

this for loop why we do this

#6

Tetrahedron is a prism
We have to find no of ways to reach at top in n moves
So initially its already there so for n=0
d=1 and for rest corners a,b,c at n=0 is 0

Now
We can go to any corner from other 3 corners
So we this is what we are doing in loops

My suggestion is calculate manually for smal test cases
And then see the loop

#7

why we put d=1 and others is zero?

#8

These are the states of DP
dp(A)(0)=0
dp(B)(0)=0
dp©(0)=0
dp(D)(0)=1
dp(A)(n)=dp(B)(n-1)+dp©(n-1)+dp(D)(n-1)
dp(B)(n)=dp(A)(n-1)+dp©(n-1)+dp(D)(n-1)
dp©(n)=dp(A)(n-1)+dp(B)(n-1)+dp(D)(n-1)
dp(D)(n)=dp(A)(n-1)+dp(B)(n-1)+dp©(n-1)

#9

Bro for n=0 that is we cant move
So ways to reach a,b,c are 0 and sice we are already on top so way to reach top is 1 i.e d=1

#10

if you see this question the first time then you able to make it or not??

#11

I am seeing this for the first time :slight_smile:
This will come to you naturally with practice.
The more problems you solve the better you will become handling new problems :slight_smile:

1 Like
#12

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.