Editorial for COCI '08 Contest 6 #6 Slicice
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
The problem can be modeled with a flow network, the maximum flow through the network being the answer. The vertices in the network are the source, sink, purchases and children. The number of purchases is half the number of cards.
The source is connected to all purchases with links of capacity two. Known purchases are connected only to the two children who went, again with links of capacity two. Unknown purchases are connected to all children. Finally, we connect all children to the sink, the capacity of links equal to the number of cards they have in the end. The maximum flow through the network tells us how the cards were distributed.
Comments