10007  Count the Trees
Moderator: Board moderators

 New poster
 Posts: 9
 Joined: Fri Nov 03, 2006 1:25 am
 Location: Canada
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?
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?
here is the output of my AC program for input 300:
Code: Select all
13737807510976206042952273897263258508116975599604959518836124365862819224972658
54247030784146639904262298233057468287928668494180243215174601311778665118426704
17171885915385919843693603797986405860478580069565298906600371579310154166721548
84642821868426332272555365876086239190316574236560064566289860573384870560398989
02530980551460458426544345837161718124181949606274255138205520532384213599681911
63606267378157023283379718208347819449062986359065168271437231036651857351986944
96342113923556380223811493708762698490251880849682072220871314430821012003878532
64012017604175970350255386228567910306655728454185976665239017777964057814520236
76412850909472964586763768638262987637255558541460374176087541426615261698457600
000000000000000000000000000000000000000000000000000000000000000000000000

 New poster
 Posts: 9
 Joined: Fri Nov 03, 2006 1:25 am
 Location: Canada
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 wrote:here is the output of my AC program for input 300:Code: Select all
13737807510976206042952273897263258508116975599604959518836124365862819224972658 54247030784146639904262298233057468287928668494180243215174601311778665118426704 17171885915385919843693603797986405860478580069565298906600371579310154166721548 84642821868426332272555365876086239190316574236560064566289860573384870560398989 02530980551460458426544345837161718124181949606274255138205520532384213599681911 63606267378157023283379718208347819449062986359065168271437231036651857351986944 96342113923556380223811493708762698490251880849682072220871314430821012003878532 64012017604175970350255386228567910306655728454185976665239017777964057814520236 76412850909472964586763768638262987637255558541460374176087541426615261698457600 000000000000000000000000000000000000000000000000000000000000000000000000
here is my input and output code:
Code: Select all
while(cin >> n) {
if (n == 0) break;
cout << result[n] << endl;
}

 New poster
 Posts: 9
 Joined: Fri Nov 03, 2006 1:25 am
 Location: Canada
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)
After that, I just print out the appropriate element of the array.
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.length1; 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));
}

 New poster
 Posts: 9
 Joined: Fri Nov 03, 2006 1:25 am
 Location: Canada
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 wrote:Code: Select all
BigInt arr[] = new BigInt[301]; arr[0] = new BigInt(1); for (int k=0; k<arr.length1; 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)); }
Ami ekhono shopno dekhi...
HomePage
HomePage

 New poster
 Posts: 9
 Joined: Fri Nov 03, 2006 1:25 am
 Location: Canada
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.Jan wrote: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 wrote:Code: Select all
BigInt arr[] = new BigInt[301]; arr[0] = new BigInt(1); for (int k=0; k<arr.length1; 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)); }
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.
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.
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.