# LCOLLIS - Editorial

#1

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

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

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:

#2

Three for loops are not required to get the answer. For any girl i count the number of boys that like her (say n). Then the collision due to this girl is simply nC2. So the complexity can be reduced to O(nm)

#3

import java.util.;
import java.io.
;
class collision
{

public static void main(String args[] )throws IOException
{

int n,m,i,j;

int c=0,b=0;
int a[][]=new int[10][10];

while(t!=0)
{

n=Integer.parseInt(br.readLine());

c=0;

b=0;


for(i=0;i<n;i++)
{

for(j=0;j<m;j++)


{

a*[j]=Integer.parseInt(br.readLine());


}

}
for(j=0;j<m;j++)
{
b=0;

for(i=0;i<n;i++)
{

if(a*[j]==1)


{

b++;


}
}

if(b==2)
{

c++;

}
else if(b>2)
{

c=c+(b*(b-1)/2);

}

}

t–;
}

}

}

#4

what is problem in my solution? i got nzec…

#5

you got NZEC error since the input is a string and not white space separated integers … see the sample input carefully…

#6

import java.io.;
import java.util.
;

 class collision {

public static void main(String args[])throws IOException
{
try
{
Scanner sc=new Scanner(System.in);
int q=0,s=0;
int k=0,count=0;
int N=0,M=0;
int col=0;
int t;

while(t>0)
{
count=0;
col=0;
k=0;
s=0;

int i=0;
int j=0;
String arr[]=lines.split(" ");
N=Integer.valueOf(arr[0]);
M=Integer.valueOf(arr[1]);

String A[][]=new String[N][M];
for(i=0;i<N;i++)
{

for( j=0;j<M;j++)
{

A*[j]=sc.next();
}

}
if(N==1)
{
col=0;
System.out.println(col);
}
for(j=0;j<M;j++)
{
for(i=0;i<N;i++)
{

k=i;
while(k<N-1)
{

if(A*[j].equals("1") && A[k+1][j].equals("1"))
{
col++;

}
k++;
}

}
}
System.out.println(col);
t--;
}

}
catch(Exception e)
{
return;

}

}


}
Why is this showing wrong answer?.It is working for all test cases

#7

Why is this showing runtime error?

# include

using namespace std; int a[10][10]; int main() {

int tc,i,j,k,l,ctr=0,g=0,b[10];
long int f=1;
cin>>tc;
while(tc)
{cin>>k>>l;
for(i=1;i<=k;++i)
{for(j=1;j<=l;++j)
{cin>>a*[j];}
}
for(i=1;i<=l;++i)
{for(j=1;j<=k;++j)
{if(a[j]*==1)
++ctr;
}
b*=ctr;
ctr=0;
}
for(j=1;j<=l;++j)
{
while(b[j])
{f*=b[j];
--b[j];
}
g+=f*0.5;
f=1;

}
cout<<g<<"
";
g=0;
--tc;}
return 0;
}


#8

It is really frustrating, now that I find that the input was a string type. I think it was unclear in the problem statement. And my program that would have easily run in O(n*m) kept giving TLE.

#9

many people have submitted the solution like this one: https://www.codechef.com/viewsolution/10610421

I want to know the logic behind using statements like :
for(j=1;j<=m;j++)
{
if(summ[j]>1)
{
tmp = summ[j]*(summ[j]-1);
tmp = tmp/2;
sum = sum + tmp;
}
}

#10

#include
using namespace std;

int main()
{
int n,i,row,col,k,l,temp;
char ch;
cin >> n;
int coll[n];
for(i=0;i<n;i++)
{
coll*=0;
cin >> row >> col;
int arr[row][col];
for(k=0;k<row;k++)
{
for(l=0;l<col;l++)
{
cin>>ch;
arr[k][l] = ch - ‘0’;
temp = k-1;
while(temp>=0)
{
if(arr[k][l] == 1 && arr[k][temp]== 1)
coll*++;
temp–;
}

		}
}

}
for(i=0;i<n;i++)
{
cout << coll* << endl;
}
return 0;


}

#11

A solution using Python:

for t in xrange(int(raw_input())):
N, M = map(int, raw_input().split())
matrix = []
for _ in xrange(N):
matrix.append(raw_input())
popular = {}
# iterate thru the matrix to build a dictionary of liked girls counting how many boys like them
for girl in xrange(M):
for boy in xrange(N):
if matrix[boy][girl] == '1':
popular[girl] = popular.get(girl, 0) + 1
# calculate the numbers of unique pairs possible given each value from the dictionary
# ignoring any value of '1' because that's not a collision and would eval to '0' anyway
# output the sum of these numbers
print sum((n * (n - 1)) / 2 for n in popular.values() if n > 1)

#12

#include<stdio.h>
int main(void){
int t;
scanf("%d",&t);
while(t–)
{int n,m,i,j,a[11][11];
scanf("%d %d",&n,&m);
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{scanf("%d",&a*[j]);}

	}
int count=0,m1;
for(i=0;i<m;i++)
{ m1=0;
for(j=0;j<n;j++)
{
if(a[j]*==1)
{m1++;}

}

if(m1>1)
{count+=(m1*(m1-1))/2;}
}
printf("%d


",count);

}


return 0;
}

#13

#include<stdio.h>
int main(void){
int t;
scanf("%d",&t);
while(t–)
{int n,m,i,j,a[11][11];
scanf("%d %d",&n,&m);
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{scanf("%d",&a*[j]);}

	}
int count=0,m1;
for(i=0;i<m;i++)
{ m1=0;
for(j=0;j<n;j++)
{
if(a[j]*==1)
{m1++;}

}

if(m1>1)
{count+=(m1*(m1-1))/2;}
}
printf("%d


",count);

}


return 0;
}

#14

#include<stdio.h>
#include<conio.h>

int set[100][2];
int length = 0;

int find(int p, int q) {

int i = 0;
for(i = 0; i <= length; i++)
{
if(set*[0] == p && set*[1] == q)
{
return 1;
}
}
return 0;


}

void main()
{

int i, j, k, t;
int mat[100][100];

int n, m, count, temp;

scanf("%d", &t);

while(t--)
{
count = 0;
scanf("%d %d", &n, &m);

for(i = 0; i < n; i++)
{
j = 0;
scanf("%d", &temp);
while(temp)
{
mat*[j] = temp % 10;
temp /= 10;
j++;
}
}

for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++)
{
if(mat*[j] == 1)
{
temp = j;
while(temp < n)
{
if(find(i, j))
{
temp++;
continue;
}

count++;
set[length][0] = i;
set[length][1] = j;
length++;
temp++;
}
}
}
}

printf("%d


", count - 1);
}

getch();


}

I tried the solution using set. It gave correct answer while testing basic cases. but gives wrong answer.

#15

worst editorial -_-

#16

//here is a solution using hashing
#include <bits/stdc++.h>
using namespace std;
int comb(int n)
{
return n*(n-1)/2;
}
int main()
{
int t;
cin>>t;
while(t–)
{
int n,m;
cin>>n>>m;
int hs[m+5];
for(int i=0;i<=m+5;i++)
hs*=0;
string s[n+1];
for(int i=0;i<n;i++)
{
cin>>s*;
for(int j=0;j<m;j++)
if(s*[j]==‘1’)
hs[j]++;
}
int c=0;
for(int i=0;i<=m+5;i++)
if(hs*>1)
{
c+=comb(hs*);
}
cout<<c<<endl;
}
return 0;
}

#17

You just need to count the number of 1’s in a given column and then find the number of ways of choosing 2 out of this. This is equal to nC2 and hence for each column add the value of nC2 and you will get your answer!

Three for loops not required!

#18

#include<stdio.h>
int main()
{
int t;
scanf("%d",&t);
while(t–)
{
int n,m;
scanf("%d %d",&n,&m);
int arr[n][m];
int i,j,k;
int collision=0;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
scanf("%d",&arr*[j]);
}
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
for(k=0;k<m;k++)
{
if(arr*[k]==1&&arr[j][k]==1)
collision+=1;
}
}
}
printf("%d
",collision);
}
return 0;
}
why it give run time error but in local environment it gives the correct output

#19

why is this code giving WA (wrong answer) whereas in online compiler the output is right

#include<stdio.h>
#include<stdlib.h>
int main()
{
int t,i;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
int m,n,p,q;
scanf("%d %d",&m,&n);
char a[m][n];
for(p=0;p<m;p++)
{
scanf("%s",a[p]);
}

int c=0,s=0;
for(q=0;q<n;q++)
{
c=0;
for(p=0;p<m;p++)
{
if(a[p][q]=='1')
c++;
}
s+=(c*(c-1))/2;
}
printf("%d


",s);
}
}

#20

RE can anyone explain