Team of Two Scored Problem Code: TEAMOF2 CodeChef Solution

 

Problem

Your class recently got a maths assignment with $5$ questions. There are $N (\le 20)$ students in the class and at most $2$ people can collaborate. For each student, you know which problems they solved.

Find out if there exists a team of two students who can together solve all problems.

Input Format

The first line of input will contain a single integer $T$, denoting the number of test cases. $T$ test cases follow.

• Each of the following test cases contains $N + 1$ lines, where $N$ is the number of students in the class.
  • The first line contains a single integer $N$.
  • Each of the following $N$ lines contains $K_i + 1$ positive integers separated by whitespaces.
    • In the $i^{th}$ line, the first positive integer $K_i$ is the number of problems the $i^{th}$ student can solve. The next $K_i$ integers are $x_1, x_2, \ldots, x_{K_i}$, the indices of the problems this student can solve.

Output Format

The output must consist of $T$ lines.

• Each line must contain a single string: The solution to the $i^{th}$ test case as a YES or NO (where YES should be returned if some pairing of students is capable of solving all the problems, and NO otherwise).

You may print each character of the string in uppercase or lowercase (for example, the strings YES, yEs, yes, and yeS will all be treated as identical).

Constraints

• $1 \leq T \leq 1000$
• $2 \leq N \leq 20$
• $0 \leq K_i \leq 5$
• $1 \leq x_i \leq 5$

Sample 1:

Input

Output

4
3
1 3
1 1
4 1 3 4 5
2
4 2 3 4 5
3 1 2 4
3
1 1
1 2
1 3
2
2 1 5
3 2 3 4

NO
YES
NO
YES

Explanation:

Test case $1:$ There is no student who solved the second question.

Test case $2:$ The second student can solve the first question and the first student can solve all the remaining problems, so they can form a team to solve all the problems together.

Test case $3:$ There is no student who solved fourth and fifth questions.

Test case $4:$ Given $2$ people can collaborate to solve all the problems.

int n;

cin>>n;

vector<vector<int>>v;

for (int i = 0; i < n; i++)

{

    int t;

    cin>>t;

    vi p;

    for (int j = 0; j < t; j++)

    {

        int x;

        cin>>x;

        p.pb(x);

    }

    v.pb(p);

    

}

for (int i = 0; i < n; i++)

{

    

    for (int j = i+1; j < n; j++)

    {

        map<int,int>m;

    for(auto x:v[i]){m[x]++;}

        for(auto x:v[j]){m[x]++;}

        if(m.size()==5){

        cout<<"YES\n";

        return;

    }

    // bug(m.size());

    }

    

    

    

}

cout<<"NO\n";