Why is this not right????? (LCOLLIS)

general
, ,
1

This is my simple solution:

import java.util.Scanner;
class LCOLLIS
{
	final static long[] factorial = {1,1,2,6,24,120,720,5040,40320,362880,3628800};
	public static void main(String[] args) 
	{
		Scanner scan = new Scanner(System.in);
		long n = scan.nextLong();
		for(long i=0;i<n;i++)
		{
			long coll=0;
			long N = scan.nextLong();
			scan.nextLong();
			for(long j=0;j<N;j++)
			{
				coll+=combinations(count1(scan.next()));
			}
			System.out.println(coll);
		}
		scan.close();
	}
	static long count1(String input)
	{
		return input.length()-(input.replaceAll("1", "").length());
	}
	static long combinations(long N)
	{
		if(N==1||N==0)
			return 0;
		return factorial[(int) N]/((2)*factorial[(int) (N-2)]);
	}
}

I thought of using P&C here, cause I found it easy!

What’s wrong in this??
THANKS A LOOOT!!

2

Hey @arnavvarshney

Your code fails for this test case.

The question states that if there are two different boys x and y, who both like girl z, then there will be a collision. For two boys two like a girl, matrix will have 1 as value for two different value of i but for same value of j. You should apply this combination not on every N rather you should apply it on every M. You have applied the combination on every row but according to the question, it should be applied on every column.

2 Likes
3

Got it… Thanks a lot @therisingsun…

4

Hey! @therisingsun

Now, what I wanted to clarify is, that if there are 3 (1)s for one girl,
as in:

101
100
101

Will there be 3 collisions or 2?
Thanks!