10007 - Count the Trees

[Scottathon]

I'm having a hard time understanding why I'm getting WA. I'm computing all of the values up to 300 dynamically, sticking them into an array, and calling the appropriate values when requested.

The correct value for n=300 is going to work out to 600!/301!, right?
I've compared that value worked out with maple and my program's output, and they are identical.

Is there any specific formatting that I might be missing?

[Donotalo]

here is the output of my AC program for input 300:

Code: Select all

13737807510976206042952273897263258508116975599604959518836124365862819224972658
54247030784146639904262298233057468287928668494180243215174601311778665118426704
17171885915385919843693603797986405860478580069565298906600371579310154166721548
84642821868426332272555365876086239190316574236560064566289860573384870560398989
02530980551460458426544345837161718124181949606274255138205520532384213599681911
63606267378157023283379718208347819449062986359065168271437231036651857351986944
96342113923556380223811493708762698490251880849682072220871314430821012003878532
64012017604175970350255386228567910306655728454185976665239017777964057814520236
76412850909472964586763768638262987637255558541460374176087541426615261698457600
000000000000000000000000000000000000000000000000000000000000000000000000

[Scottathon]

here is the output of my AC program for input 300:

Code: Select all

13737807510976206042952273897263258508116975599604959518836124365862819224972658
54247030784146639904262298233057468287928668494180243215174601311778665118426704
17171885915385919843693603797986405860478580069565298906600371579310154166721548
84642821868426332272555365876086239190316574236560064566289860573384870560398989
02530980551460458426544345837161718124181949606274255138205520532384213599681911
63606267378157023283379718208347819449062986359065168271437231036651857351986944
96342113923556380223811493708762698490251880849682072220871314430821012003878532
64012017604175970350255386228567910306655728454185976665239017777964057814520236
76412850909472964586763768638262987637255558541460374176087541426615261698457600
000000000000000000000000000000000000000000000000000000000000000000000000

Thanks for the reply. My value for 300 is identical, so it's got to be a formatting issue. Did you add the line breaks yourself, or does your code print it like that? I have it going to a newline only at the end of the number, because I didn't see any mention of anything different in the problem.

[Donotalo]

here is my input and output code:

Code: Select all

while(cin >> n) {
	if (n == 0) break;
	cout << result[n] << endl;
}

[Scottathon]

Thanks again for the response. I'm still completely puzzled as to why I continue to get WA.

Do you see anything wrong with this algorithm? (it's in java and uses a BigInt class that I found on the java forum, but I think it's fairly straight forward)

Code: Select all

BigInt arr[] = new BigInt[301];
	arr[0] = new BigInt(1);
	for (int k=0; k<arr.length-1; k++) {
		int top = (((2*k)+1)*((2*k)+2));
		int bottom = (k+2);
		
		arr[k+1] = arr[k].multiply(new BigInt(top));
		arr[k+1] = arr[k+1].divide(new BigInt(bottom));
			
	}	

After that, I just print out the appropriate element of the array.

[Donotalo]

look at the catalan number formula once again. shudn't the top be 2 * (2*k + 1) ?

[Scottathon]

I'm pretty what I have is correct, because the Catalan numbers correspond to the number of unlabeled binary trees. In the case of 10007, the trees are labelled, so the formula is multiplied by n!.

(2n)!/(n+1)! is the formula, if I am not mistaken.

[Jan]

Code: Select all

BigInt arr[] = new BigInt[301];
	arr[0] = new BigInt(1);
	for (int k=0; k<arr.length-1; k++) {
		int top = (((2*k)+1)*((2*k)+2));
		int bottom = (k+2);
		
		arr[k+1] = arr[k].multiply(new BigInt(top));
		arr[k+1] = arr[k+1].divide(new BigInt(bottom));
			
	}

I think your algorithm is correct. I dont have any java compiler. So, I just used your formula in C++ and the output matches correctly. Make sure that you are printing correctly and breaking when necessary.

[Scottathon]

Code: Select all

BigInt arr[] = new BigInt[301];
	arr[0] = new BigInt(1);
	for (int k=0; k<arr.length-1; k++) {
		int top = (((2*k)+1)*((2*k)+2));
		int bottom = (k+2);
		
		arr[k+1] = arr[k].multiply(new BigInt(top));
		arr[k+1] = arr[k+1].divide(new BigInt(bottom));
			
	}

I think your algorithm is correct. I dont have any java compiler. So, I just used your formula in C++ and the output matches correctly. Make sure that you are printing correctly and breaking when necessary.

Thanks for your response. I've sent some submissions that I set to TLE after a certain amount of iterations, to verify that I'm at least getting *some* answers right, and this has revealed that I'm getting at least the first 50 test cases correct.

Perhaps this simply just another issue of Java being a poor choice for the judge. I will have to revisit this problem after I learn C++.

Thanks for your help, everyone.

[Darko]

If you get a TLE, it doesn't mean that answers were correct.

On this judge, when you get a WA in Java (and in Pascal) that might mean a Run Time Error. So, check if there are blank lines, spaces at the end of lines, that sort of thing. I didn't send the table in, but you can compare your time with other Java times - if your solution returns WA much faster, then it is most probably RTE.