10213 - How Many Pieces of Land ?

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10213 .- Why Wrong Answer?

Post by lord_burgos » Sun Nov 16, 2003 8:19 pm

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]

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

:) 10213

Post by lord_burgos » Sun Nov 16, 2003 8:30 pm

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

Post by .. » Mon Nov 17, 2003 9:43 am

Are you sure you won't get precision error?
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    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

Post by shuniu » Wed Nov 26, 2003 12:59 am

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.

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

wa.. don't know why

Post by sohel » Sat Jan 15, 2005 7:16 am

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.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sat Jan 15, 2005 3:09 pm

Sohel, My AC code gives the same output.
You better see how you use your BigNum, maybe there is a pitfall.

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

Post by Sedefcho » Wed Jan 26, 2005 11:51 pm

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.

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

Post by sohel » Tue Feb 01, 2005 12:00 pm

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
Thanks for your reply..
the 10 is actually the number of test cases.

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

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

Post by Sedefcho » Tue Feb 01, 2005 1:56 pm

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.

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

Post by Sedefcho » Tue Feb 01, 2005 1:57 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Feb 01, 2005 3:02 pm

You are getting the smilies because you are typing an '8' followed by a ')', which is interpreted as 8)
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.

About your question:
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.

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

Post by Sedefcho » Tue Feb 01, 2005 3:14 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Feb 01, 2005 4:59 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.

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

Post by Sedefcho » Tue Feb 01, 2005 6:28 pm

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.

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

Post by Sedefcho » Tue Feb 01, 2005 9:41 pm

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.

Post Reply

Return to “Volume 102 (10200-10299)”