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

Post by Red Scorpion » Tue Jul 22, 2003 8:15 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. :D :D :D :D :D

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

Post by Almost Human » Tue Jul 22, 2003 4:29 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

Post by titid_gede » Tue Jul 22, 2003 5:21 pm

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

Post by Almost Human » Tue Jul 22, 2003 5:29 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

Post by Faizur » Fri Aug 22, 2003 3:18 pm

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
Location: BANGLADESH
Contact:

Post by Jalal » Fri Aug 22, 2003 5:28 pm

SAME 2 ME :(
HAVE 2 CHEAK CRITICAL INPUTS :-?

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

10519 !! Really Strange !! [Resolved]

Post by shamim » Sat Nov 15, 2003 2:39 pm

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:

Post by Larry » Sat Nov 15, 2003 2:49 pm

Why do you think if there is zero circles, there's zero regions?

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sat Nov 15, 2003 3:29 pm

What about the others, are they correct.

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Sat Nov 15, 2003 5:37 pm

Yes, the others are correct.

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

10519 - !!REALLY STRANGE!!

Post by helloneo » Thu Sep 01, 2005 5:19 pm

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.

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

Re: 10519 - !!REALLY STRANGE!!

Post by Martin Macko » Thu Sep 01, 2005 8:23 pm

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:

Post by sclo » Fri Feb 10, 2006 12:10 pm

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.

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

10519 -- getting WA

Post by dust_cover » Sat Oct 07, 2006 9:14 am

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!

Thanx in advance
i wanna give it a try....

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

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

Post by dust_cover » Sat Oct 07, 2006 8:29 pm

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!

Thanx in advance
i wanna give it a try....

Post Reply

Return to “Volume 105 (10500-10599)”