You are not logged in. Please login at www.codechef.com to post your questions!

×

LCOLLIS - Editorial

PROBLEM LINK:

Practice
Contest

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

This question is marked "community wiki".

asked 25 Jun '16, 18:23

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170
accept rate: 20%

edited 25 Jun '16, 23:40

admin's gravatar image

0★admin ♦♦
19.8k350498541


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)

link

answered 25 Jun '16, 23:05

aayushdw's gravatar image

5★aayushdw
813
accept rate: 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;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(c);

t--; }

}

}

link

answered 25 Jun '16, 23:23

vivek96's gravatar image

2★vivek96
533220
accept rate: 8%

what is problem in my solution? i got nzec....

link

answered 25 Jun '16, 23:24

vivek96's gravatar image

2★vivek96
533220
accept rate: 8%

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

link

answered 26 Jun '16, 10:19

tarun_174's gravatar image

2★tarun_174
1
accept rate: 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<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

link

answered 26 Jun '16, 12:43

vidhitchandra's gravatar image

2★vidhitchandra
112
accept rate: 0%

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

answered 26 Jun '16, 13:38

akshatp's gravatar image

2★akshatp
213
accept rate: 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

link

answered 26 Jun '16, 16:15

apaar_97's gravatar image

4★apaar_97
212
accept rate: 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; } }

link

answered 26 Jun '16, 18:52

aniketsanadhya's gravatar image

1★aniketsanadhya
115210
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;

}

link

answered 20 Jul '16, 21:03

csk8888's gravatar image

0★csk8888
1
accept rate: 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)
link

answered 22 Jul '16, 20:51

thejeremyjohn's gravatar image

2★thejeremyjohn
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; }

link

answered 29 Sep '16, 03:17

yash1234567's gravatar image

1★yash1234567
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; }

link

answered 29 Sep '16, 03:18

yash1234567's gravatar image

1★yash1234567
1
accept rate: 0%

RE can anyone explain

(29 Sep '16, 03:19) yash12345671★

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.

link
This answer is marked "community wiki".

answered 04 Oct '16, 22:41

susil95's gravatar image

2★susil95
1
accept rate: 0%

worst editorial -_-

link

answered 19 Dec '16, 12:12

udit043's gravatar image

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

link

answered 25 Dec '16, 23:02

salman_1's gravatar image

5★salman_1
1
accept rate: 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!

link

answered 06 Jun '17, 12:00

krshubham's gravatar image

3★krshubham
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

link
This answer is marked "community wiki".

answered 27 Jun '17, 09:25

ashishkirtiwed's gravatar image

1★ashishkirtiwed
-1
accept rate: 0%

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

}

link

answered 09 Oct '18, 19:59

vinay612's gravatar image

1★vinay612
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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