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;
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;