BinaryCrazy's blog

By BinaryCrazy, history, 5 years ago, In English

Hello all,

I recently stumbled upon this USACO problem linked here for reference. However, I wasn't able to solve it. When I looked at the editorial (here) of the solution, I realized that my logic was the same, but I couldn't prove the inclusion-exclusion for higher orders (> 2 sets).

I would really appreciate it someome could prove the addition-subtraction logic used for inclusion exclusion.

Thank a bunch, and hope you have a great day!

[Edit] I realized it may not be clear what I am asking. To be more brief, how can I prove that you can get the number of distinct connections by adding all subsets of size 1, subtracting subsets of 2, adding 3 ... and so on.

-BC

  • Vote: I like it
  • -6
  • Vote: I do not like it

| Write comment?