TEAMOF2 - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Aatman Supkar
Testers: Jeevan Jyot Singh, Hriday
Editorialist: Nishank Suresh

DIFFICULTY:

1512

PREREQUISITES:

None

PROBLEM:

N students receive a math assignment of 5 questions. You are given which questions each student knows to solve.

Is it possible for some pair of students to solve all the questions together?

EXPLANATION

N is quite small, so a straightforward brute force solution is good enough.

Iterate over each pair of students, and check if together they cover all 5 questions. This check can be done in a variety of ways, for example:

  • Insert all the questions solvable by one of the two students into a set, then check if this set has size 5; or
  • Keep an array of size 5, initially all zero. Mark each question one of the two students can solve with a 1. Finally, check if every index is marked; or
  • Represent the set of questions a given student can solve with a 5-bit bitmask, i.e, an integer from 0 to 31. Then, check if the bitwise OR of the two students’ bitmasks equals 31.

TIME COMPLEXITY

\mathcal{O}(N^2) per test case.

CODE:

Editorialist's code (Python)
for _ in range(int(input())):
    n = int(input())
    a = []
    for i in range(n):
        solved = list(map(int, input().split()))[1:]
        a.append(solved)
    ans = 'no'
    for i in range(n):
        for j  in range(n):
            if len(set(a[i] + a[j])) == 5:
                ans = 'yes'
    print(ans)

Why this code is giving wrong answer on some test cases

    Scanner scn  = new Scanner(System.in);
    int t = scn.nextInt();
    while (t-- > 0) {
      int a = scn.nextInt();
      a--;
      Set<Integer> ideal = new HashSet<>();
      for (int i = 1 ; i <= 5 ; i++) {
        ideal.add(i);
      }

      int ll = scn.nextInt();
      int[] tee = new int[ll];
      for (int i = 0 ; i < ll ; i++) {
        tee[i] = scn.nextInt();
      }
      int flag = 0;
      while (a-- > 0 && flag == 0) {

        Set<Integer> los = new HashSet<>();
        for (int i = 0 ; i < ll ; i++) {
          los.add(tee[i]);
        }
        int aa = scn.nextInt();
        int[] arr3 = new int[aa];
        for (int i = 0 ; i < aa ; i++) {
          arr3[i] = scn.nextInt();
          los.add(arr3[i]);
        }
        if (los.equals(ideal) == true) {
        //   printY();
          flag = 1;
        }
        


      }
      if (flag == 1 ) {
        printY();
      } else {
        printN();
      }
      flag = 0;

why is [1:] taken while reading the input
why 0th index is neglected

coz 0th is size you need not to worry about it while taking input in python in list.

can anybody provide me with some special test cases for this problem. idk why it is still showing wa although it passed the test cases i could think of.

Why this code is not able to pass all hidden test cases . Anyone pls just look at it .
This what i did in this proble .
first i have initialized a 2-d vector ‘a’ then i run a loop which will take m lines and in each line it will take only question numbers not total numbers of questions then this 1D vector ‘b’ will pushed back in e-D vector ‘a’
in the last i just ran two nested loop for earch two students i put all questions numbers for two students and inserted in set ‘st’ and chechking if st.size()=5 then it printing YES if no to students solved all wuestion then printing NO .Preformatted text
#include<bits/stdc++.h>
using namespace std;
define ll long long
define pll pair<ll,ll>
define vl vector
define vvl vector<vector>
define vpl vector
define um unordered_map<ll,ll>
define om map<ll,ll>
define yes cout<<“YES”<<endl
define no cout<<“NO”<<endl
define all(x) x.begin(), x.end()
define rtn return
int main()
{
int t = 1 ;
cin>>t;
while( t-- )
{
int n;
cin>>n;

      vector<vector<int>>a;
      bool flag = false;
      //collecting data in Data Structure
      for ( int i = 0;i<n; i++)
      {
          int m ;
          cin>>m;
          vector<int>b(m);
          for ( int j = 0;j<m; j++)cin>>b[j];
         
          a.push_back(b);
      }
      

      // Accessign data from 2D vector
      for(int i= 0;i<n; i++)
      {   set<int>st;
          for (auto it:a[i])st.insert(it);
          if ( st.size()==5){
              flag = true;break;
             }
          for ( int j = i+1; j<n;j++)
          {
              for (auto it:a[j])st.insert(it);
             // for (const int it:st)cout<<it<<" ";
              if ( st.size()==5){
              flag = true;break;
             }
          }if (flag)break;
      }
  if ( flag )yes;
  else no;
}
rtn 0;

}