10213 - How Many Pieces of Land ?
Moderator: Board moderators
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
Thanks in advanve.
Pls inform what'll be the output for the following values of N ?
N=5,6,7,8,9,10,2147483647
Thanks in advanve.
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>
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.
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~
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.
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!
I was thinking in this problem and don't get the recurrence relation...
Can anyone help?
Thanks,
JP!
-
- Experienced poster
- Posts: 146
- Joined: Sat Apr 26, 2003 2:51 am
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?
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?
-
- 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
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)
Born from ashes - restarting counter of problems (800+ solved problems)
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!
![:oops:](./images/smilies/icon_redface.gif)
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!
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
-
- New poster
- Posts: 35
- Joined: Sat Jan 05, 2002 2:00 am
- Contact:
-
- 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
for k points
is it the answer something like 2^k
can you suggest some recurrence relation
thanks!
nick