I don't know how Hall's Marriage Theorem relates to the problem, but here
is an example of what the theorem means.
We have 2 groups, and we're trying to match them
Group A tells us what in group B they would be satisfied with
Group B tells us what in group A they would be satisfied with
Lets say Group A are the positions in a row, and group B are the numbers
that could go into the row.
So lets say A1 is happy with only 1, and A2 is happy only with 2. Is there
a complete matching? Yes, and it's obvious what it is.
Lets say A1 is happy with only 1
A2 is happy with either 1 or 2
A3 is happy with either 1 or 3.
Halls marriage theorem asks you to count elements of different sets. First
look at order 1 sets. Are there enough 1 to satisfy those that only want a
1. Yes, we have 1 such case, and we have a 1 to put there.
Nobody is asking for only 2, or only 3.
Now we go to sets of order 2. Looking at all the requirements, how many
are covered by the set {1, 2}. A1 needs a 1, A2 needs a 1 or 2, so these
both count. A3 needs a 1 or 3, this doesn't count (yet) because 3 isn't in
the {1,2} set we are considering.
So we have 2 set or requirements that are subsets of {1,2}, and that set
has 2 elements, so we are still happy here.
Now we try {1,2}, and find again 2 subsets, then we try {2,3} and find 0
subsets.
Finally we try {1,2,3}, all 3 requirements are subsets of this, and we have
3 elements, so this is OK.
OK, lets try 4 positions, with 4 requirements:
A1 wants {1,2}
A2 wants {2,3,4}
A3 wants {3}
A4 wants {1,4}
Requirement set - how many subsets - how many elements - happy?
{1} - 0 - 1 - Yes
{2} - 0 - 1 - Yes
{3} - 1 - 1 - Yes
{4} - 0 - 1 - Yes
{1,2} - 1 - 2 - Yes
{1,3} - 1 - 2 - Yes
{1,4} - 0 - 2 - Yes
{2,3} - 1 - 2 - Yes
{2,4} - 0 - 2 - Yes
{3,4} - 1 - 2 - Yes
{1,2,3} - 2 - 3 - Yes
{1,2,4} - 2 - 3 - Yes
{1,3,4} - 2 - 3 - Yes
{2,3,4} - 2 - 3 - Yes
{1,2,3,4} - 4 - 4 - Yes
So this is happy and a matching can be found.
An example of an unhappy matching:
A1 wants {1, 2, 3}
A2 wants {4, 5}
A3 wants {1, 2, 3}
A4 wants {1, 2}
A5 wants {1, 2, 3}
The algorithm is happy through order 1 and 2, but at order 3 it finds that
there are 4 requirement sets that are subsets of {1,2,3}, but only 3
elements to go around, so no matching can be found.
Paul Smith
[email protected]
On Tue, 7 Apr 2020 at 01:54, Amogh Kamath <[email protected]> wrote:
> I understand (partially, as you'll see) the solution provided in analysis
> section of the problem. During the contest, I understood that traces of the
> form "AAAA ... AABC for some A, B, C (not necessarily all different)" will
> bear a solution. But I wasn't sure if greedily selecting the elements will
> yield the latin square. I tried to read Hall's Marriage Theorem
> <https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem>, but it went
> straight over my head.
>
> Could someone explain, in simple terms, what Hall's Marriage Theorem is
> and when and where I can use it?
> I'm not looking for proofs at the moment, I'm just trying to understand
> what the theorem states.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Google Code Jam" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/google-code/68641323-c0ce-4754-911c-4c75fa9e1791%40googlegroups.com
> <https://groups.google.com/d/msgid/google-code/68641323-c0ce-4754-911c-4c75fa9e1791%40googlegroups.com?utm_medium=email&utm_source=footer>
> .
>
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/CAJej63%2BwEDjBnc%2BHRBnhMBhJQd58sLy34MkfxvpV1YzqLu7FiQ%40mail.gmail.com.
