## 10213 - How Many Pieces of Land ?

Moderator: Board moderators

chang
New poster
Posts: 16
Joined: Wed Jan 16, 2002 2:00 am

### 10213 - How Many Pieces of Land ?

Hey !
Pls inform what'll be the output for the following values of N ?
N=5,6,7,8,9,10,2147483647

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
5 16
6 31
7 57
8 99
9 163
10 256
2^31-1 886151993063477126682488902248300547

and use BIG NUM...
I got WA even use long double...

chang
New poster
Posts: 16
Joined: Wed Jan 16, 2002 2:00 am
Hey Even!

Oh! my recurrence was wrong. But I can't detect how the recurrence can be built. Would u please inform how built up ur recurrence,Or is there any direct formula to solve this one?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Hi~

There is a formula to solve this question, I don't know if it has a name, because I prove it myself by induction:

answer = (i - 1) * i * (i * i - 5 * i + 18) / 24 + 1
where i is the input (For i > 1)

<font size=-1>[ This Message was edited by: .. on 2002-01-20 07:55 ]</font>
Last edited by .. on Fri Jan 24, 2003 3:14 pm, edited 1 time in total.

chang
New poster
Posts: 16
Joined: Wed Jan 16, 2002 2:00 am
Hey ..

Would u pls tell how u derive that formula by induction procedure? I'm really so curious to know it. I've the idea of induction, but I can't find out the way of thinking.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
oh......that is quite difficult to tell you the proof by text......hope you will understand what I say:

Let P(n) be the number of lands when n points are drawn on circle

Now assume knowing P(n-1), want to know P(n) by adding the n-th point

when the n-th point draw a line to the k-th point (1 <= k <= n-1)
on the LHS on k-th point, there is k-1 points between k-th and n-th point
on the RHS on k-th point, there is (n-1)-k+1 points between k-th and n-th point
the points in these 2 sets(LHS, RHS) are completely connected,
so there are (k-1)*(n-k) lines crossed by the newly drawn line,
creating (k-1)*(n-k)+1 new lands......

So, drawing lines from newly added n-th point to all n-1 old points,
will create

summation[(k-1)(j-k)+1] {k = 1..j (j = n-1)} new lands

let says the summation be F(j)

P(n)= P(n-1) + F(n-1)
= P(n-2) + F(n-2) + F(n-1)
.....
= P(0) + F(1) + F(2) + ....... + F(n-1)
= 1 + summation(F(i)) {i = 1..n-1}

by using formula of summation to simplify the equatoin(what a difficult job.....)
I get
answer = (i - 1) * i * (i * i - 5 * i + 18) / 24 + 1;

Good luck~
Last edited by .. on Fri Jan 24, 2003 3:15 pm, edited 1 time in total.

zhangl
New poster
Posts: 4
Joined: Tue Nov 05, 2002 2:28 am
Location: China
Although being far far away,
Still I do do feel you.
Through the sky,
Across the ocean,
I hear

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

### 10213 - How many pieces of land?

Hi all!

I was thinking in this problem and don't get the recurrence relation...

Can anyone help?

Thanks,

JP!

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am
Or yes... this one is very hard. I just can give an answer
answer = (n - 1) * n * (n * n - 5 * n + 18) / 24 + 1
please, take a look at the previous posts...

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

### And how do I get it?

Ok, it appears to be right!

But, how do I get to this formula?

Thanks!

PS: I searched the board and did not found any topic on this problem, can you tell me where it is?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
topics are divided into pages ... on top of table with list of them you see some numbers like 1,2,3 .... and so on ....

Try to click on it and you got next page of forum for such vlume

Bet regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

### I've found it!

Sorry, I've found it now!!!

My search was using the board search feature, on 10213, and it did not return that topic...

Looking page by page, I've found it, is there a bug in the search engine?

Again, sorry for my fault..

JP!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
No problem. Life is sometimes hard

DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Alexander Denisjuk
New poster
Posts: 35
Joined: Sat Jan 05, 2002 2:00 am
Contact:
By the way, it is not very hard to obtain the formula. The easiest way is the following:

1. To beleive that the formula is polynomial.
2. To calculate the interpolation polynomail.

chervensky
New poster
Posts: 4
Joined: Wed Oct 22, 2003 9:11 pm

### 10213 how to solve?!?

huh
for k points
is it the answer something like 2^k
can you suggest some recurrence relation

thanks!

nick