WATCHFB Editorial

PROBLEM LINK:

Practice
Contest

Author: Hasan Jaddouh
Tester & Editorialist: Hussain Kara Fallah

PROBLEM EXPLANATION

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.

DIFFICULTY:

Easy

PREREQUISITES:

None

EXPLANATION:

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

3 Likes

please tell me why I am getting WA for this solution?

https://www.codechef.com/viewsolution/26834508

because you din check if score was known previously while checking condition at line 43 of your code.

In first one the minimum value must be strictly less than the max one.

I am not able to get what is wrong in this code.

int t = in.nextInt();
    for (int _t = 0; _t < t; _t++) {
        int n = in.nextInt();
        int t1 = -1;
        int t2 = -1;
        for (int i = 0; i < n; i++) {
            int type = in.nextInt();
            int qt1 = in.nextInt();
            int qt2 = in.nextInt();
            if (type == 1) {
                t1 = qt1;
                t2 = qt2;
                System.out.println("YES");
            } else if (type == 2) {
                if (qt1 == qt2) {
                    t1 = t2 = qt1;
                    System.out.println("YES");
                } else if (t1 == -1) {
                    System.out.println("NO");
                } else if (Math.min(qt1, qt2) < Math.max(t1, t2)) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
    }