We will hold AtCoder Regular Contest 117.

- Contest URL: https://atcoder.jp/contests/arc117
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210418T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: E869120, square1001
- Tester: tempura0224
- Rated range: — 2799

The point values will be 200-400-600-600-900-900.

We are looking forward to your participation!

Setter should have swapped C and D.

+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.

same

Genius3435 please give the link of that video u have mentioned above.

You could literally just search Mathologer and it's one of his videos, but here's the link.

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

How to solve D ? , Even a small explanation would be appreciated .

Its hard to explain without a diagram, but I'll try. Our main objective is to reduce the number of "skips" while assigning numbers to nodes.

Basically, If we're going to assign values by dfs, For each node, when we visit the subtree of one of its child A and move on the the child B, we'll be "skipping" some numbers in order to satisfy 2nd condition. Skips are shown in the code below.

Naive dfs satisfying first 2 conditionsNow to minimize the final number "val", we've to notice that other than some straight line path in a tree, every other edge is going to contribute to 1 skip.

Now since the longest staight path in a tree is the diameter we just iterate throught the diameter and naively use the above algorithm to assign values to subtrees connected to the diameter. My Submission

https://atcoder.jp/contests/arc117/submissions/21869171

can u see my submission tell me whats wrong with it i have applied same approach only 7 testcase pass please help

Thanks for the explanation :)

i agree with you

Was the problem C inspired by this?

I didn't get the idea provided in the editorial for problem C !! Can somebody explain in a more detailed way?

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.

thank you very mush,i think your explain is helpful to me

Another option: use Lucas's theorem to compute $$${n-1 \choose i-1} \space mod \space 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)

How to solve D? I thought that starting traversal from leaf node is enough.

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

My approach for D was to find the diameter of the tree and then I was setting the value equal to 1 and diameter +1 which nodes (a,b) give the diameter and then run the dfs on the other node such that every node value is less than diameter+1 but please help where my approach is wrong. Submission link

Problem C is the typical “have you seen this trick before?” or “can you search this at google” type of problem. Or did people manage to deduce the solution by themselves? I am glad to get to know this problem though

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).

Do you mean blue+(white+red)? I assume blue+white+red would be $$$(b+w)+r=r+r=r$$$?

blue = -(white+red), note the minus sign!

I just wanted to emphasize that the associative property is not given.

I totally agree on $$$blue = -(white+red)$$$. I disagree on $$$blue+white+red = blue+blue+blue$$$ though.

Oh right. Yeah, I missed things, I guess it was too intuitive for me. Since we want 3*blue = 3*white = 3*red, that hints at modulo 3, then it's = 0, and then -blue = 2*blue = white+red.

We demand associativity because we lose nothing by trying to find an operator + that's associative first and trying other things later. Since we found a solution with this requirement (namely regular operator + modulo 3), everything's fine on that front.

This isn't the only possible idea (obviously, since bruteforce exists), but it's a pretty common approach to solving problems to try several increasingly more complex / uglier ideas.

Nice problems!

Screencast with commentary

Nice explanation!

Very good contest!! I think the problems are very fascinating and the time is friendly to Chinese participants.

However I didn't solve B very quickly and I think D is easier than C.

It's hard to come up with the construction without watching that video

Hi could anyone give a hint about the O(n log A) approach to problem F? Read many accepted codes but still have no idea about how it works.

Um.. I think the editorial is wrong on Problem F.

`Additionally, the larger s_N is, the smaller s_N - s_{N-1} will be.`

I believe the truth is the larger s_N is, the large s_N — s_{N-1} will be.I still do not get how in the editorial of e, when there are 4 2's in third col, how the number of ways of choosing two of them is 4, when 4c2 is 6.

Great contest. I was just wondering about the Bonus part given in

Problem D's editorial where the authors have asked to implement a checker code in $$$O(n\log n)$$$ time. Does anyone have any idea how this might be done? Thanks!