I have this problem (complete description): There is a list of persons N and M t
ID: 659125 • Letter: I
Question
I have this problem (complete description):
There is a list of persons N and M topics.
I have to find out the maximum number of topics a 2-person team can know. And also find out how many teams can know that maximum number of topics.
2<= N <= 500
1<= M <= 500
Ex.
Rows are persons, columns are topics.
If there is 1 the person know that topic, 0 otherwise.
10101
11100
11010
00101
The result are 5,2
My algorithm is a bruteforce implementation, I think the complexity is O(n^3)
vector<bitset<501>> v;
int nMax = 0;
int nMaxCounter = 0;
for(int i=0; i<N; i++) {
for(int j=i+1; j<N; j++){
bitset<501> t = v[i] | v[j];
if(t.count() > nMax) {//t.count() -> returns the number of bits set to true
nMax = t.count();
nMaxCounter = 1;
} else {
if(t.count() == nMax)
nMaxCounter++;
}
}
}
cout<<nMax<<endl;
cout<<nMaxCounter<<endl;
First question:
Is the complexity O(n^3) ?
Second question
Do you are able to find a better algorithm?
Explanation / Answer
1) Let's assume that t.count() is a linear-time operation with respect to the size of the bitset (it probably isn't on real hardware, but ignore that). Then it would be correct to say that the algorithm is O(M*N^2), for the obvious reason that you have an M-iteration-loop (t.count()) inside an N-iteration-loop inside an N-iteration-loop. That might be equivalent to O(n^3) if you chose a somewhat awkward definition of n, but since your problem size is already defined in terms of two different variables there's not much point trying to smush them into one.
2) In general, you can only beat the brute force solution to an algorithm if checking one or more solutions lets you "rule out" other solutions you haven't checked yet. For example, binary search beats linear search because after checking the middle element, you can rule out half of the list without checking all the elements individually. With this problem, unless your input is in some sense "pre-sorted", I don't see any way of getting around the need to check every single pair, so no I cannot find a better algorithm (in terms of time complexity class).