+1

I found C relatively easy, but it was basically the same as a Mathologer video I watched a few days ago, so I got it pretty quickly. I don't think problems should be similar to videos like that, although it's hardly the setter's fault if they didn't see the video.

yea, I got D pretty quickly but thought of C for an hour and nothing

i agree with you

There is a mathologer video with almost the same idea https://www.youtube.com/watch?v=9JN5f7_3YmQ

Let the colours be represented by distinct numbers in modulo 3 space. Then, convince yourself the "combining function" is $$$f(x,y) = -(x+y) \mod 3$$$. This is easy to figure out by just trying all the combinations.

From now on, let all operations be done modulo 3, and our function be $$$g(x,y)=(x+y) \mod 3$$$. Then, we want to keep finding sums of adjacent pairs till we have only one array left. Say we start with $$$a_1, a_2, \cdots, a_n$$$ numbers (each representing a colour). Then, the next array will be $$$a_1+a_2, a_2+a_3, \cdots, a_{n-1} + a_n$$$. The array after that is $$$a_1 + 2a_2 + a_3, a_2 + 2a_3 + a_4, \cdots$$$. This is pretty much Pascal's triangle, and the final sum becomes $$$S = \sum_{i=1}^n \binom{n-1}{i-1} a_i$$$. Since our initial function was actually $$$f(x,y) = -g(x,y)$$$, if $$$n$$$ is even, then the answer will actually be $$$-S$$$, otherwise it is $$$S$$$. Find the colour which matches $$$S$$$, and that will be the answer.

Something noteworthy is you have to calculate binomial coefficients modulo 3, but you can't do it naively since $$$n! = 0 \mod 3, \forall n \geq 3$$$. To get around this, keep track of the power of 3 in $$$n!$$$ (say $$$p$$$) and the value of $$$n!$$$ without any powers of 3.

i used the property that for n=4 if i have to determine the colour of the topmost element i could simply determine it with the help of the 2 corner most elements of the bottom most row as x=(2*y+2*z)%3 (y and z being the cornermost elements) so it is basically independent of the other elements for n=4 you could extrapolate it now for greater n.

reference:- (http://digitaleditions.sheridan.com/publication/?i=648526&article_id=3591614&view=articleBrowser&ver=html5)

my code:- (https://atcoder.jp/contests/arc117/submissions/21868359)

Travelling from any leaf of the diameter should work. All vertices except the ones on diameter would be visited twice.

You should know about pascals triangle and binomial coefficients at least. Then It is plausible.

Well, I didn't know the idea and was thinking for quite some long time about C. I also assigned 0,1,2 to the colors. I tried to find a relation for the resulting block on two other blocks. Like I tried $$$c=a+b$$$, $$$a=a*b$$$, $$$c=k*(a+b)+j*a*b$$$ and so on... I also tried writing the numbers as vectors (1,0,0), (0,1,0) and (0,0,1) and try combine them with the crossproduct (spoiler: it didn't work out, since $$$a \times a = (0,0,0)$$$).

Then I wrote down a 3x3 table with all combinations and analysed simple addition again, and then noticed that you only have to swap the twos and ones, so $$$c=-(a+b)$$$. Knowing Pascals Triangle the solution then seemed obvious. I just had no idea how to calculate all binomial coefficients for $$$n$$$ efficiently and then there was no more time left.

I solved it myself though 10 min after contest my solution got AC. I think if you try to find some valid function to deal with string, it becomes solvable.

We intuitively want to reduce both cases to one case, and blue+white+red = blue+blue+blue if blue = -(white+red).

Nice explanation!