Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

maroonrk's blog

By maroonrk, history, 5 months ago, In English

We will hold AtCoder Regular Contest 117.

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

We are looking forward to your participation!

 
 
 
 
  • Vote: I like it
  • +158
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Setter should have swapped C and D.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    +1

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

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

      • »
        »
        »
        »
        5 months ago, # ^ |
        Rev. 4   Vote: I like it +6 Vote: I do not like it

        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 conditions

        Now 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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    i agree with you

»
5 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Was the problem C inspired by this?

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

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +24 Vote: I do not like it

    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.

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)

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

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

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

»
5 months ago, # |
  Vote: I like it +21 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            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.

»
5 months ago, # |
  Vote: I like it +41 Vote: I do not like it
»
5 months ago, # |
  Vote: I like it -26 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

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

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.

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

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.

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

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!