Chef and his son Chefu want to watch a match of their favourite football team playing against another team.
Chef asks Chefu for the score N times and each time he received a reply.
There are two types of replies:
1 A B: their favorite team scored A goals and the other team scored B goals
2 A B: one team scored A goals and the other scored B goals without specifying who scored A and who scored B.
After each reply, based on the current reply and all previous information (but without any following replies), tell Chef whether it is possible to certainly determine the number of goals scored by his favourite team.
We need to handle all possible cases in this problem.
First, let’s keep track of the scores Chefu replied with to the last question (they would be 0-0 at the beginning). Also, we need to distinguish at each point of time if we really know the mapping between the scores and the teams or not.
Let’s start processing replies one by one then:
- If the score told is a draw (our previous queries don’t really matter) the answer is YES.
- ELSE If the reply was of the first type, the answer is YES and we definitely know the score-to-team mapping from this moment on.
- ELSE If we don’t know the score-to-team mapping at this moment and first two conditions are not met, then definitely we won’t get any information with the new reply so the answer is NO.
- ELSE If we already know the mapping between the last recorded scores and the teams (min_p,max_p) with min_p being the score of the team with fewer goals. If on the current reply (min_c,max_c) the team with fewer goals min_c didn’t reach the team with most goals on the previous reply max_p (In short min_c < max_p) then we know for fact that the team who scored min_p on previous reply and min_c on current one are the same team.
- ELSE In any other case, the answer is NO. And we should mark that we don’t know the mapping for processing future replies until we get some reply that points out the mapping.
AUTHOR’S AND TESTER’S SOLUTIONS:
EDITORIALIST’s solution: Can be found here