10519 - !! Really Strange !!

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

Moderator: Board moderators

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
for :
n= 1 we get -> 2
n = 2 we get -> 4
n = 3 we get -> 8
n = 4 we get -> 14
... this pattern repeated

Code: Select all

2
2
4          2
4         0
8          2
6
14
see this sequences have 2 extrapolation, so the formula is :
f(n) = a*n^2 + b*n + c
n = 1 -> a + b + c = 2 ...1)
n = 2 -> 4a + 2b + c = 4 ...2)
n = 3 -> 9a + 3b + c = 8 ...3)

solve it you will get a = 1, b = -1, and c = 2;
so the equation is:
f(n) = n^2 - n + 2.

I hope it helps.     Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm
I've generated the same formula ... May be I can explain a little to you. Hope it's useful.

But by the way ... I got WA for this .... Is this problem big number or what ?

Firstly, I didn't add 1 to the result... so I got the sequence :

1 , 3 , 7 , 13 , 21 ...

we get the extrapolation :
2 2 2
2 4 6 8
1 3 7 13 21

I'm using a recursive approach :

f(n) = f(n-1) + range, where range is defined as 2 * ( n - 1 )
so :
f(n) = f(n-1) + 2 * (n-1)
f(n) = f(n-2) + 2 * (n-2) + 2*(n-1)..
f(n) = f(1) + 2 * ( 1 ) + ... + 2 * ( n-1 ) where f(1) = 1

f(n) = f(1) + total of the sequence above, that is
2*(1) + 2*(2) + ... + 2*(n-1)

Sum = (n-1)/2 * ( 2 + 2*(n-1) )

so ...
f(n) = f(1) + (n-1)/2*(2+2*(n-1))
f(n) = f(1) + (n-1)*(1+(n-1))
f(n) = f(1) + (n-1)*n ;
f(n) = 1 + n(n-1) ;

then .. we add 1 to this formula ....
f(n) = 2 + n(n-1)

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
yes, the input can be up to 1000 digits (not 1000 numbers!), and be careful of n = 0. hope it can help.
Kalo mau kaya, buat apa sekolah?

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm
Allright ....

I've changed my code and used my bignum class and got ACC..

thanks ...

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm

10519 WA after rejudge

I get Wa after rejudge of the problem 10519.What is changed after the rejudgement............

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Contact:
SAME 2 ME HAVE 2 CHEAK CRITICAL INPUTS shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

10519 !! Really Strange !! [Resolved]

I am getting WA, I realize that I have to use BigNumber. Here are some output from my program.

INPUT
• 0
1
2
3
4
5
6
7
8
9
10
99
100
9999
10000
OUTPUT
• 0
2
4
8
14
22
32
44
58
74
92
9704
9902
99970004
99990002
Please verify whether they are correct.
Last edited by shamim on Sun Nov 16, 2003 12:47 pm, edited 1 time in total.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Why do you think if there is zero circles, there's zero regions?

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
What about the others, are they correct.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
Yes, the others are correct.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

10519 - !!REALLY STRANGE!!

Code: Select all

code removed
i got WA..
did i miss anything..?
when there is no circle.. ouput should be 1.. right..?
Last edited by helloneo on Fri Dec 08, 2006 5:50 am, edited 1 time in total.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10519 - !!REALLY STRANGE!!

Any comment about algorithm you have used? Why just posting the code without any comment? It would be much easier to help you if you would describe your algorithm instead of posting just the code.

Have you read all topics on this problem? You can find a lot of usefull info in them: http://online-judge.uva.es/board/viewtopic.php?t=4402, http://online-judge.uva.es/board/viewtopic.php?t=3520, or http://online-judge.uva.es/board/viewtopic.php?t=3408.

BTW, cited from the board main page: "If there is a thread about your problem, please use it."

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
Here's a way to derive the formula without using any sequences, just uses some elementary graph theory.

The case n=0 and n=1 are special cases, but it turns out that for n=1 the formula is correct.

For the cases n>1,
Let v be the number of intersection points, we know there are n(n-1) of them since there are n(n-1)/2 pairs of circles and each pair has exactly 2 intersection points. These are the vertices of our graph. Now v=n(n-1).

We can now think of the arcs of the circles bounding the regions as edges between the vertices. It is easy to see that the degree of each vertex is 4 (since exactly 2 circles intersect at each intersection point), so by the handshaking lemma, the total number of edges, e = 4v/2 = 2v = 2n(n-1).

We are asked to compute the number of regions f, so by Euler's formula,
f = e - v + 2 = n (n - 1) + 2.

This is the same formula as above.

dust_cover
New poster
Posts: 23
Joined: Tue Sep 12, 2006 9:46 pm

10519 -- getting WA

can anybuddy tell me what should be the output for inout 0 & 1.....I am getting WA.
I used BigInt library
Also used the standard formula for the problem!

i wanna give it a try....

dust_cover
New poster
Posts: 23
Joined: Tue Sep 12, 2006 9:46 pm

10519 -- getting WA PLZ HELP!!!!!!!!!!!!!

can anybuddy tell me what should be the output for inout 0 & 1.....I am getting WA.
I used BigInt library
Also used the standard formula for the problem!