10213 - How Many Pieces of Land ?

[lord_burgos]

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]

This is:

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

[..]

Are you sure you won't get precision error?

[shuniu]

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]

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]

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

[Sedefcho]

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]

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.

[Sedefcho]

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 ?

[Sedefcho]

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]

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.

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.

[Sedefcho]

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]

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]

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]

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.