user311's blog

By user311, history, 5 weeks ago,

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

• -10

 » 5 weeks ago, # |   0 I used dp and wrote this code. But it failed. codeint ansRing(int n){ int r = 1, g = 0, b = 0; for(int i{1}, curg, curb, curr; i <= n; ++i){ curg = r + b; curb = r + g; curr = g + b; r = curr; g = curg; b = curb; } return 3 * r; } 
 » 5 weeks ago, # |   0 HintThere are two cases: nodes $1$, $n-1$ may have the same color or different colors. From here, it should be easy to find a dp.
 » 5 weeks ago, # |   0 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; }