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
This might help: https://cp-algorithms.com/combinatorics/inclusion-exclusion.html