×

# LCOLLIS - Editorial

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 \times 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[i][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:

This question is marked "community wiki".

2.5k53137170
accept rate: 20%

19.8k350498541

 4 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) answered 25 Jun '16, 23:05 5★aayushdw 81●3 accept rate: 0%
 0 import java.util.; import java.io.; class collision { public static void main(String args[] )throws IOException { InputStreamReader isr=new InputStreamReader(System.in); BufferedReader br=new BufferedReader(isr); int t=Integer.parseInt(br.readLine()); int n,m,i,j; int c=0,b=0; int a[][]=new int[10][10]; t=Integer.parseInt(br.readLine()); while(t!=0) { n=Integer.parseInt(br.readLine()); m=Integer.parseInt(br.readLine()); c=0; b=0;  for(i=0;i2) { c=c+(b*(b-1)/2); } } System.out.println(c); t--; } } } answered 25 Jun '16, 23:23 2★vivek96 533●2●20 accept rate: 8%
 0 what is problem in my solution? i got nzec.... answered 25 Jun '16, 23:24 2★vivek96 533●2●20 accept rate: 8%
 0 you got NZEC error since the input is a string and not white space separated integers .. see the sample input carefully.. answered 26 Jun '16, 10:19 1 accept rate: 0%
 0 import java.io.; import java.util.;  class collision { public static void main(String args[])throws IOException { try { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); 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; t=Integer.parseInt(br.readLine()); while(t>0) { count=0; col=0; k=0; s=0; int i=0; int j=0; String lines=br.readLine(); String arr[]=lines.split(" "); N=Integer.valueOf(arr[0]); M=Integer.valueOf(arr[1]); String A[][]=new String[N][M]; for(i=0;i

Why is this showing runtime error?

# include <iostream>

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[i][j];}
}
for(i=1;i<=l;++i)
{for(j=1;j<=k;++j)
{if(a[j][i]==1)
++ctr;
}
b[i]=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<<"\n";
g=0;
--tc;}
return 0;
}


2★akshatp
213
accept rate: 0%

 0 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. My solution : link text answered 26 Jun '16, 16:15 4★apaar_97 21●2 accept rate: 0%
 0 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; } } answered 26 Jun '16, 18:52 115●2●10 accept rate: 0%

# include <iostream>

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[i]="0;" cin="">> row >> col; int arr[row][col]; for(k=0;k<row;k++) {="" for(l="0;l&lt;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[i]++; temp--; }

        }
}

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


}

0★csk8888
1
accept rate: 0%

 0 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)  answered 22 Jul '16, 20:51 1 accept rate: 0%

# 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[i][j]);}

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

}

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

}


return 0; }

1
accept rate: 0%

# 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[i][j]);}

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

}

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

}


return 0; }

1
accept rate: 0%

RE can anyone explain

(29 Sep '16, 03:19)

# 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[i][0] == p && set[i][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[i][j] = temp % 10;
temp /= 10;
j++;
}
}

for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++)
{
if(mat[i][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\n", count - 1);
}

getch();


}

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

This answer is marked "community wiki".

2★susil95
1
accept rate: 0%

 0 worst editorial -_- answered 19 Dec '16, 12:12 2★udit043 1 accept rate: 0%

//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[i]=0; string s[n+1]; for(int i=0;i<n;i++) {="" cin="">>s[i]; for(int j=0;j<m;j++) if(s[i][j]="='1')" hs[j]++;="" }="" int="" c="0;" for(int="" i="0;i&lt;=m+5;i++)" if(hs[i]="">1) { c+=comb(hs[i]); } cout<<c<<endl; } return 0; }

5★salman_1
1
accept rate: 0%

 0 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! answered 06 Jun '17, 12:00 1 accept rate: 0%

# 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[i][j]); } } for(i=0;i<n;i++) { for(j=i+1;j<n;j++) { for(k=0;k<m;k++) { if(arr[i][k]==1&&arr[j][k]==1) collision+=1; } } } printf("%d\n",collision); } return 0; } why it give run time error but in local environment it gives the correct output

This answer is marked "community wiki".

-1
accept rate: 0%

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

# 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\n",s);
}


}

1★vinay612
1
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,679
×1,652
×53
×4
×2

question asked: 25 Jun '16, 18:23

question was seen: 4,473 times

last updated: 09 Oct '18, 19:59