LCOLLIS - Editorial





Author: Pavel Sheftelevich
Tester: Karan Aggarwal
Editorialist: Praveen Dhinwa




basic implementation


There are n boys and m girls in a class. You are given a matrix of size n imes m whose i, j-th entry denotes whether i-th boy likes j-th girl or not. There will be a collision if two boys i, j likes a girl k. You have to find number of collisions that can possibly happen in the class. Note that collision i, j liking k and j, i liking k is the same collision and should not be counted more than once.


We can just iterate over all possible pairs of boys and girls and check whether the corresponding triplets causes a collision or not.


There will be a collisions if two boys i, j likes girl k. Let a[n][m] denote the matrix given in the input, whose a_{i, j} entry denotes whether i-th boy likes j-th girl or not. Then we can check whether their a collision formed by triplets i, j, k by checking whether a_{i, k} and a_{j, k} both are equal to 1 or not.

We should notice one important thing is the order of boys in the collision does not matter, i.e. if order of i, j in the collision should not be counted twice. (i, j, k) and (j, i, k) collisions are essentially the same. So, for ease of counting, we can count a collision of pairs (i, j, k) if i < j.

For finding total number of collisions, we can notice that dimensions of the matrix dimensions are very small, n, m \leq 10. So, we can counting the collisions by just checking all triplets (i, j, k).

See the following pseudo code.

collisions = 0
for i from 1 to n:
for j from i + 1 to n:
for k from 1 to m:
if (a*[k] == 1 and a[j][k] == 1):
collisions += 1
print collisions


As we iterate over pairs i, j, k, where i and j can take values upto n and k can take values up to m. So, the overall time complexity will be \mathcal{O}(n * n * m) = \mathcal{O}(n^2 m). In the worst case, for a single test case, our program will take around \mathcal{O}(10^3) operations. There are total 100 test cases. So, total number of operations our program will take will be around \mathcal{O}(10^5) which will run very comfortably in 1 secs. Usually C, C++, Java can perform roughly 10^8 simple arithmetic operations in a second.


Author’s solution
Tester’s solution


RE can anyone explain