The-Winner's blog

[Request problems] Hall's Marriage Theorem
By The-Winner, history, 9 months ago, In English

Hello!

I've seen a couple of problems where the intended solution is to use Hall's Marriage Theorem on some weird reduction to solve the problem. These are few and hard to find, so I wanted to ask you for any problems/learning materials regarding this theorem.

One example is IOI-2015/Day1/Teams (although the reduction is fairly natural).

Thank you in advance

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

»
9 months ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

ARC076F — Exhausted

→ Reply
»
9 months ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

https://www.acmicpc.net/problem/8177

Ice skates is the classic example I know and a really good problem imo

→ Reply
»
9 months ago, hide # |
 
Vote: I like it +24 Vote: I do not like it

628F - Bear and Fair Set

→ Reply
»
9 months ago, hide # |
 
Vote: I like it +24 Vote: I do not like it

106016J - Arranged Marriage

→ Reply
»
9 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

iirc candies from this year's NOI in Bulgaria uses Hall's theorem.

→ Reply
»
9 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

JOI Spring Camp Ants and Sugar (sorry on the phone no link)

→ Reply
»
9 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

https://qoj.ac/problem/6339

Not Hall's Theorem itself, but a similar idea

→ Reply
  • »
    »
    9 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Thank you

    Not sure if it is something on my behalf, but it seems you need to be logged in to see the problem

    → Reply
»
9 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

https://mirror.codeforces.com/gym/106017/problem/M I haven't coded the solution but my ideas for this problem all come from Hall's theorem.

→ Reply
»
9 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Everything listed here;

search query on solved.ac

→ Reply