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

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

10213 - How Many Pieces of Land ?

Post by chang » Wed Jan 16, 2002 9:49 am

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

Thanks in advanve.

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Post by Even » Wed Jan 16, 2002 5:33 pm

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

Post by chang » Sat Jan 19, 2002 9:20 pm

Hey Even!

Thanks for ur reply.
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?
Thanks in advance.

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

Post by .. » Sun Jan 20, 2002 8:54 am

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

Post by chang » Sun Jan 20, 2002 8:46 pm

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.
Thanks in advance.

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

Post by .. » Mon Jan 21, 2002 8:16 am

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

Post by zhangl » Wed Nov 06, 2002 5:14 pm

answer=c(n,4)+c(n,2)+1
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?

Post by jpfarias » Wed Jun 11, 2003 2:03 am

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

Post by Dmytro Chernysh » Wed Jun 11, 2003 5:55 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?

Post by jpfarias » Wed Jun 11, 2003 1:58 pm

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:

Post by Dominik Michniewski » Wed Jun 11, 2003 2:34 pm

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!

Post by jpfarias » Wed Jun 11, 2003 5:57 pm

Sorry, I've found it now!!! :oops:

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:

Post by Dominik Michniewski » Thu Jun 12, 2003 7:49 am

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:

Post by Alexander Denisjuk » Thu Jun 12, 2003 10:03 am

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?!?

Post by chervensky » Thu Oct 23, 2003 9:40 pm

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

thanks!

nick

Post Reply

Return to “Volume 102 (10200-10299)”