Hello CF community, I was trying to solve this problem 584B - Kolya and Tanya , I saw that my logic gives wrong answers but I don't know why, my friends' solutions was like find the total cases, subtract the invalid cases but I was thinking of finding the valid cases immediately, here's how I think:
Let's take $$$n=2$$$ for example:
I can either make $$$a_0, a_2, a_4$$$ valid or $$$a_1, a_3, a_5$$$ valid, I know that for every $$$3$$$ vertexes (which are to be valid) I have $$$3^3 - 7 = 20$$$ valid cases, as the invalid cases are:
1. ($$$1, 2, 3$$$)
2. ($$$1, 3, 2$$$)
3. ($$$2, 1, 3$$$)
4. ($$$2, 3, 4$$$)
5. ($$$3, 1, 2$$$)
6. ($$$3, 2, 1$$$)
7. ($$$2, 2, 2$$$)
and for the rest of the vertexes the values I can take are either $$$1, 2,$$$ or $$$3$$$, which means $$$3^{3n-3}$$$ options, so I have $$$n$$$ options ($$$a_0$$$, $$$a_1$$$ in case $$$n=2$$$) with $$$20$$$ valid cases, and for every options of this I have $$$3^{3n-3}$$$ options $$$ \rightarrow $$$ $$$(20\times 3^{3n-3})\cdot n$$$.
Can anyone tell me what's wrong?