sankalp_'s blog

Help Needed
By sankalp_, history, 6 years ago, In English

I didn't understand why the method mentioned in the editorial works. Can someone provide me with a proof for why it works?

Question : 357B

Editorial Solution :

Let's process the dances in the given order and determine the colors of dancers' clothes. If there are no dancer from some previous dance, we can give the dances different colors arbitrarily. And if there is such dancer, we already know the color of his clothes. So, we arbitrarily distribute the other two colors between the remaining two dancers.

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

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

It's guaranteed that each dance will have no more than one dancer that participated in a previous dance, isn't it?

So, in any dance, when we see one of the dancers danced in a previous dance, we will be sure that the remmaining two dancers are new, and they haven't had clothes yet, thus we give them two different colors that also differ from the color that the old dancer had.

And when we see that all the dancers in a dance are new, we give them the colors in an arbitrary order, and declare that they become old from now.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks fam!

    Lol I misunderstood the question and I thought consecutive dances should not have more than one dancer in common.

    I should really stop thinking about sequences :)

    → Reply