A group of N friends are going out to dinner. They need to decide whether to go to a Chinese restaurant or a Greek restaurant, so they decided to take a vote. Each person has their own preference, but will not necessarily vote what they like. This is because some of the people are best friends and best friends try not to disagree with each other.
There is a disagreement in the voting if either two best friends voted for different options or if someone voted against their opinion. Given the pair of best friends (best friends are symmetric - if X is Y's best friend, then Y is X's best friend) and each person's opinion, find how each person should vote to minimize the total amount of disagreements.
Solution: This problem is based off problem K in 2006 Pacific Northwest ACM ICPC Regional. The original problem statement is here. Here is a sample solution by Robert.
UVA problem 563 - Crimewave
Solution: Robert's solution