LCOLLIS - Editorial

editorial
, , , ,
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 \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:

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

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)

2 Likes
3

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;i<n;i++)
{

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

{

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

}

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

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

if(a[i][j]==1)

{

b++;

}
}

if(b==2)
{

c++;

}
else if(b>2)
{

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

}

}

System.out.println©;

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
	{
	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<N;i++)
		{
			
			for( j=0;j<M;j++)
			{
				
				A[i][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[i][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[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;
}
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.

My solution : link text

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[i]=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[i]++;
temp–;
}

		}
	}
	
}
for(i=0;i<n;i++)
	{
		cout << coll[i] << 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[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;
}

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[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;
}

14

RE can anyone explain

15

#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[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.

16

worst editorial -_-

17

//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<=m+5;i++)
if(hs[i]>1)
{
c+=comb(hs[i]);
}
cout<<c<<endl;
}
return 0;
}

18

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!

19

#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

20

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

}