LCOLLIS - Editorial

what is problem in my solution? i got nzec…

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

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

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

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

many people have submitted the solution like this one: CodeChef: Practical coding for everyone

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

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

}

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)

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

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

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

worst editorial -_-

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

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!

#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

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

}

RE can anyone explain

The part with the tmp basically calculates the nC2 value.
In plain words,if n people like 1 girl,then no.of collisions resulting for that girl is nC2.

nC2 =n*(n-1)/2

Bro input is of string type
In problem we have to read character ‘1’ and ‘0’ not seprated by white space …

whereas in integer array its not convenient to read ‘1’ and ‘0’ for that we need whitespace char after each ‘1’, ‘0’ which willl not be provided in authors input file while checking code for AC verdict hence its giving runtime error
Read in form of sttring the following N lines

use getline keyword

#include
#include

int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
int t;
std::cin >> t;
while (t–)
{
int n, m, count = 0;
double sum = 0;
std::cin >> n >> m;
std::string s[10];
for (int i = 0; i < n; ++i)
{
std::cin >> s[i];
}
for (int i = 0; i < m; ++i)
{
count = 0;
for (int j = 0; j < n; ++j)
{
if (s[i][j] == ‘1’)
{
count++;
}
}
sum = sum + (((count * count) - count) / 2);
}
std::cout << sum << std::endl;
}
}

what ami doing wrong plz tell.