LCOLLIS - Editorial

basic-implement
cakewalk
editorial
lcollis
ltime37

#1

PROBLEM LINK:

[Practice][111]
[Contest][222]

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

DIFFICULTY:

Cakewalk

PREREQUISITES:

basic implementation

PROBLEM:

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.

QUICK EXPLANATION

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

EXPLANATION:

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

TIME COMPLEXITY

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 AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution
[111]: http://www.codechef.com/problems/LCOLLIS
[222]: http://www.codechef.com/LTIME37/problems/LCOLLIS


#20

RE can anyone explain