B - Perfect Editorial by en_translator
Consider managing who solved which problems.
Specifically, maintain an array of flags representing whether person \(i\) has solved problem \(j\) for all integer pairs \((i,j)\) with \(1\leq i\leq N\) and \(1\leq j\leq M\). Initially, all flags are set False.
Also, for each person, we also maintain a flag representing whether they has solved all problems. These flags are also all set False at first.
Finally, we prepare a list (vector) of persons where we store the person numbers who solved all problems in chronological order, which will be finally printed.
For each of the \(K\) events in order, repeat the following:
- Set the flag representing whether person \(A_i\) has solved problem \(B_i\) to True.
- Inspect every person to check if they have solved all problems. If person \(i\) has solved all problems and the flag representing that state is set
False, then append person \(i\) to the output list and set the flag toTrue.
Finally, we print the person numbers stored in the list, separated by spaces.
The total computational complexity of the procedure above, which inspects all flags in every step, is \(O(KNM)\); however, there is no repeated event, \(K\leq NM\), and thus the computational complexity is \(O(N^2M^2)\)—fast enough under the constraints of the problem.
Actually, the following optimizations are possible:
- In the \(i\)-th event, only person \(A_i\) may newly become a person to solve all problems, so it is enough to inspect the flags for person \(A_i\). This reduces the complexity to \(O(KM)\).
- Since there is no repeated event, we do not need to manage who solved which problem, and only need to manage how many problems each person has solved. The time complexity is \(O(K)\) (and space complexity is, naively, \(O(N)\)).
Sample code in C++ (Naive solution):
#include <bits/stdc++.h>
using namespace std;
int main(void){
int n,m,k;
int a,b,cnt;
bool solved[10][10]={};
bool recorded[10]={};
vector<int>ans;
cin>>n>>m>>k;
for(int ievent=0;ievent<k;ievent++){
cin>>a>>b;
solved[a-1][b-1]=true;
for(int i=0;i<n;i++){
cnt=0;
for(int j=0;j<m;j++){
if(solved[i][j])cnt++;
}
if((cnt==m)&&(!recorded[i])){
ans.push_back(i+1);
recorded[i]=true;
}
}
}
int sz=ans.size();
for(int i=0;i<sz;i++){
cout<<ans[i];
if(i<(sz-1))cout<<" ";
else cout<<endl;
}
return 0;
}
Sample code in C++ (\(O(K)\) solution):
#include <bits/stdc++.h>
using namespace std;
int main(void){
int n,m,k;
int a,b;
int cnt[10]={};
vector<int>ans;
cin>>n>>m>>k;
for(int i=0;i<k;i++){
cin>>a>>b;
cnt[a-1]++;
if(cnt[a-1]==m)ans.push_back(a);
}
int sz=ans.size();
for(int i=0;i<sz;i++){
cout<<ans[i];
if(i<(sz-1))cout<<" ";
else cout<<endl;
}
return 0;
}
Sample code in Python (naive solution):
n,m,k=map(int, input().split())
solved=[[False for j in range(m)]for i in range(n)]
recorded=[False for i in range(n)]
ans=[]
for ievent in range(k):
a,b=map(int, input().split())
solved[a-1][b-1]=True
for i in range(n):
cnt=0
for j in range(m):
if solved[i][j]:
cnt+=1
if cnt==m and recorded[i]==False:
ans.append(i+1)
recorded[i]=True
print(*ans)
posted:
last update: