user311's blog

By user311, history, 5 weeks ago, In English

An undirected graph is called a ring if all its nodes have degree two. For a ring of size n, find the number of ways to color it using three colors Red, Green or Blue such that no two adjacent nodes have the same color.

Constraint — n < 2e5

 
 
 
 
  • Vote: I like it
  • -10
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I used dp and wrote this code. But it failed.

code
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
Hint
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • This is the recursive solution, it can be memoized to get a solution of time complexity 0(n)

int fun(int i,int prev,int first_node,int n) {

// three different colors 1,2,3 // here i is state, prev is the color of previous node,first_node is color of first node, n is total number of nodes if(i==n) { int ans=0;

for(int k=1;k<=3;k++)
   if(k!=prev and k!=first_node)//for the last node we can't paint color of first node and color of previous node 
     ans++;

   return ans;

} if(i==1) { int a=0,b=0,c=0; //for the first node we can paint any color a=fun(i+1,1,1,n); b=fun(i+1,2,2,n); c=fun(i+1,3,3,n);

return a+b+c;

}

int ans=0;
   //for any other node we can paint a color that is different from previous one 
 for(int k=1;k<=3;k++)
 { 
   if(k!=prev)
     ans+=fun(i+1,k,first_node,n);
 }

 return ans;

}

int findans(int n) { int ans=fun(1,-1,-1,n);

return ans; }