The following problem is from the Google code jam 2014 qualification round. Head-over there to read the complete problem description.
The problem description is as follows.
A magician starts by arranging 16 cards in a square grid: 4 rows of cards, with 4 cards in each row. Each card has a different number from 1 to 16 written on the side that is showing. Next, the magician asks a volunteer to choose a card, and to tell him which row that card is in.
Finally, the magician arranges the 16 cards in a square grid again, possibly in a different order. Once again, he asks the volunteer which row her card is in. With only the answers to these two questions, the magician then correctly determines which card the volunteer chose.
We have to write a program to help you understand the magician’s technique. The program will be given the two arrangements of the cards, and the volunteer’s answers to the two questions: the row number of the selected card in the first arrangement, and the row number of the selected card in the second arrangement. The rows are numbered 1 to 4 from top to bottom.
Your program should determine which card the volunteer chose; or if there is more than one card the volunteer might have chosen (the magician did a bad job); or if there’s no card consistent with the volunteer’s answers (the volunteer cheated).
This problem is simply finding the intersection elements of the rows chosen by the volunteer in the first, and second arrangements. If the intersection contains a single element, then magician can correctly guess the element. If the intersection contains zero elements, volunteer has cheated. If it contains more than one element, then the magician is bad at arranging the cards.
Here is the C++ code to solve this problem.