zephxr's blog

Need Help in Atcoder Problem(ThREE)
By zephxr, history, 4 years ago, In English

Link to the Problem :- https://atcoder.jp/contests/hitachi2020/tasks/hitachi2020_c?lang=e 29

Can anyone discuss it's solution and how to implement it. I read the editorial but not able to understand the two cases they discussed!

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

Comments Comments (8)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

First you color the tree in two colors, alternating. We count the nodes of both colors, the smaller group has max N/2 members since if it would have more, it would be the bigger group.

Then we need to place the numbers into the nodes of this smaller group. One possible way to do this, is to place all numbers which are divisable by 3 into those nodes. That way we would create a proper distribution, since all pairs of nodes of different color would fullfill the constraints (ie the product of the nodes would be diviseable by 3).

But there is a problem: The number of nodes in the smaller group can be bigger than the number of available numbers which are devisable by 3. In this case we do not use the x%3==0 numbers, but we use the x%3==1 numbers. Note that there is the same amount of them, or one more.

After having used all x%3==1 numbers, we go on and use the x%3==0 numbers. Note that there are allways enough such numbers to fill all nodes of the smaller group.

Then consider the remaining nodes, which get the remaining numbers: All of them get x%3==2 number, or a x%3==0 number. So all pairs of different colorered nodes have at least one x%3==0 number (which makes the product divisable by 3), or one is from smaller group and has x%3==1 number, and the other is from bigger group, and hence has x%3==2 numbers. So the sum is divisable by 3.

The two cases are

  1. Number of nodes in smaller group <= Available Numbers with x%3==0
  2. The opposite of 1.
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Adding to this, the most crucial observation is:

    If two nodes are distance $$$3$$$ apart, they will have opposite colors in original $$$2$$$-coloring. That's why we aren't concerned about property being held within the same color group.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks spookywooky for explaining it beautifully.

    I wanted to Ask why we are considering the smaller group first and then the bigger group

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Since one of the cases is, that the number of elements in the group is less than the available numbers devisable by 3. That case cannot be seen by considering the bigger group.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        According to your statement,you meant to say that bigger group will have atleast N/2 numbers which would be greater than the number of elements divisible by 3 in any case.

        Am i correct or not?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The bigger group allways has more members than available numbers divisable by 3.

          The point is, it could have even more members than available x%1==0 + x%1==1. So we use the smaller group, since we can distribute the numbers greedyly in the smaller group.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thank you for clearing my doubts mahn. One question more i want to ask:

            If we put all numbers divisible by 3 in the bigger group then what will be the problem?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Since the bigger group has more members than you have numbers available which are diviseable by 3, you have to put more numbers into that group.

              So you have to choose x%3==1 or x%3==2 ones. Most likely there will be some left over, or you have to use both kinds. Which will result in the fact that you have numbers of the same kind in both groups. Which is what you not want, since pairs of such nodes do not fullfill the constraints.

              → Reply