## 10213 - How Many Pieces of Land ?

Moderator: Board moderators

lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

### 10213 .- Why Wrong Answer?

(n^4-6n^3+23n^2-18^n+24)/24

[c]
# include <stdio.h>

main(){
double x,y,z;
int n,i;
scanf("%d",&n);
for(i = 0; i<n;i++){
scanf("%lf",&x);
y =(((x*x*x*x)-(x*x*x*6) + (23*x*x) - (18*x) + 24))/24;
printf("%.0lf\n",y);
}
return 0;
}
[/c]

lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

### :) 10213

This is:

(n^4-6n^3+23n^2-18^n+24)/24

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Are you sure you won't get precision error?
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

shuniu
New poster
Posts: 34
Joined: Thu Oct 16, 2003 6:15 pm

### 10213 Combinatorics Approach

There is a combinatorics explaination to the formula, it is actually 1 + (n choose 2) + (n choose 4).

1 is the original circle.

(n choose 2) is the number of lines we are drawing, by choosing the 2 endpoints.

(n choose 4) is the number of intersections inside the circle, by choosing 4 points ABCD(in clockwise order) on the circle, then line AC and BD forms a unique intersection.

Basically each time we draw a line on the circle, we are adding (1+m) to the number of pieces, where m is the number of intersections on the new line.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### wa.. don't know why

I am also using the formula 1 + nc2 + nc4 but getting WA.
I also match all the samples from the board.

Can someone confirm the following I/O

Input

Code: Select all

``````10
0
1
54
12575
312544
110010
1112143
1000000000
2000000000
1234567890
``````
Output

Code: Select all

``````1
1
317683
1041390301833851
397580508821554746073
6102302473357942756
63742478475498293889839
41666666416666667624999999250000001
666666664666666670499999998500000001
96794050695522260242568330014498846
``````
BTW : I have used BIGNUM.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
Sohel, My AC code gives the same output.
You better see how you use your BigNum, maybe there is a pitfall.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
sohel,

There's something strage in your output - the first line
( the output for input == 10 )
is missing.

I hope this is just a copy-paste error.

Otherwise it would be some bug.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
Sedefcho wrote: sohel,

There's something strage in your output - the first line
( the output for input == 10 )
is missing.

I hope this is just a copy-paste error
the 10 is actually the number of test cases.

I got it AC.. silly mistake in my multiplication function.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Oh, sorry for that stupid remark of mine.
I see now, 10 is just the number of test cases to follow.

By the way I also have a BigInt custom class but currently
it does support division. And so I can not use it.

I mean that as the formula is :

Code: Select all

``````F(N) = ( N * (N-1) * (N*N-5*N+18) / 24 ) + 1
``````
we should be able to divide by 24 once we generate the BigInt
value

Code: Select all

``N * (N-1) * (N*N-5*N+18) ``

Should I necessarily implement division in my BigInt or is
that some tricky workaround letting me get away without
doing division of 24 at the end of the computation ?

What do you think about that ?
Last edited by Sedefcho on Sun Mar 13, 2005 7:42 pm, edited 1 time in total.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
The smiles in my last message should be replaced
by the digit EIGHT.

I don't know why I can not post the digit

EIGHT

here in that forum.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
You are getting the smilies because you are typing an '8' followed by a ')', which is interpreted as
There are several ways around this:
- allways place code within code tags:

Code: Select all

``8)``
will suppres the smilies (and is much better to read)
- disable smilies for the message: you can check this when writing it.

You can't get around doing division on bignums for this question (AFAIK), but since you're only dividing by small numbers, it isn't hard to implement long division (like you learned at school).
If your bigint is stored as a string of digits, you can split the division by 24 into a division by 3 followed by a division by 8. Then you only need to divide the bignum by a single digit, which is very easy to implement.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
I don't want to implement a method like
divideBy24

I will either have a general method divide(BigInt, int) or
won't have one at all.

That is what I mean.

By workaround I mean doing the multiplications in a clever
way so that I don't need to divide by 24 at the end.

That is what I mean.
And not implementing an easy or tricky or whatever method
divideBy24.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Hmm. Suit yourself.

What I wanted to say is that divide(BigInt, int) isn't hard to implement if your BigInt is based on an array of ints. But if it's based on an array of digits, there would be an easy trick that would help you solve this particular problem. But of course you're free to implement and solve any problem you like.

Did you discover the formula yourself? Or did you just copy it from the previous posts. If you did it yourself, you might have discovered that it is equivalent to:

Code: Select all

``F(N) = N*(N-1)/2 + N*(N-1)*(N-2)*(N-3)/24 +1``
Since either N or (N-1) is even, you can divide out 2 in the first term before doing the multiplication.
The same thing goes for the second term:
since two of N, (N-1), (N-2) or (N-3) are even, one of them is divisible by four and the other is divisible by 2. Also (at least) one of the four numbers is divisible by three.
So you can divide out 4, 2 and 3 before you do the multiplication.

And then there's no need for division on BigNums.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Of course there's no need of division of BigNums.
I mean we don't need a method like
divide(BigNum, BigNum).

But still we need a method divide(BigNum, int). It seems we can not
avoid that, right ?

And yes, my implementation of BigNum has an internal
integer array, in which each integer is a decimal digit.

OK, I continue working on this problem. I will see how it
goes with implementing the method
divide(BigNum, int) .
Thank you for the comments, Little Joey.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
It's only now that I got what you mean!
We should do the division before even forming our BigNum
instances. I see. I will try this.

Currently I am happy anyway as I managed to get my
JAVA program receive "TLE" from the Online Judge and not
WA, which is quite OK.

My BigNum class gets better and better which will be
useful for other problems too.

Thanks.