PathToMaster's blog

By PathToMaster, history, 4 years ago, In English

Hi! I was trying to solve that problem but it gave me WA on subtask 3. Reading the official solution, I realized that it was pretty similar to what I did, but verifying that the two components have a size more than a. I verified that the remaining component (the one not used to assign vertices to A) had a size more than or equal to b.

Could someone tell me why the solution works? I just don't get it. Logically speaking (or writing lol), it would be impossible to assign b vertices from a subgraph of size less than b.

Update: Thinking very much, I realized why it works. Please correct me if I am wrong. If the size of the remaining component is greater or equal to a and lower than b, then we can use such component to assign vertices to A and the "original" one to assign vertices to B, because the size of the original component is greater than (a+b+c)-b = (a+c) >= b (remember b <= c so b <= a+c).

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

4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by PathToMaster (previous revision, new revision, compare).