493 - Rational Spiral

[Ghost77 dimen]

My sample test is


input

5000
2000
9999

output

13 / 64
41 / 2
91 / 10

And my max limit is 9999,
min one is 0.
I got W.A. at 1.6...seconds.

[Adrian Kuegel]

Your values are correct, try with a higher upper limit (my limit is 500000).

[Ghost77 dimen]

Can you post some samples for me?

I want to rewrite the code, because it is slow when the max input data

is 500000.

[Ghost77 dimen]

I got A.C. at 0.391 second, but I submitted it mpre than 10 times.

I am so frustrated that I am poor at programming.

But why the problem didn't point out the range?

By the way I found a interesting thing.

analyze as follows:Adrian Kuegel got A.C. ---limit 500000;

I got W.A. ----- array[500000]----limit 499999;

I got A.C. ----- array[1000000]-----limit 999999;

so that the max input is 500000.

How do Adrian Kuegel find the largest input ?

[Adrian Kuegel]

But why the problem didn't point out the range

I agree, it would be better if a range is given.

I got W.A. ----- array[500000]----limit 499999;

Sorry, my fault, I should have told you the exact limit I used (I checked if I have more than 500000 values only when I computed next row/column. Therefore my exact limit is 500071.
I have forgotten how I got this value, there are two possibilities: It was a hint in the algorithm field of that problem (I miss this field sometimes, it was really useful in such cases), or I tried several limits.

[eloha]

Can anyone tell me how to solve 493 Rational Spiral ?
I have no idea at all. Thanx.

[hujialie]

Hello.

I have used 0.45sec and 4200KB memory to AC this problem
(using array[500000]).

Usually,when I got Crash(RunTime Error) for the sake of out of
range,I just check the table how many memory did those ACed
people use and calculate...

But I wonder how those who used 0.000sec and 64KB solve it?
Does anyone know a math method?

[Ivor]

I used more than a megabyte. Please, feel free to search the board about timing and memory usage issues. It's been explained again and again and again.... I just don't feel like telling the story once more.

Ivor

[Sedefcho]

I think this is a nice problem.

In my opinion it is not too easy and not too hard
at the same time.

I see there're only about 260 people who have solved it.
Why is that ? Judging from this fact one would say
it is a very difficult problem.

Here are some test cases for anyone who
is trying to solve it or will be trying to solve it.

Seems the Judge has some test case in which the input
number is bigger than 500 000.
Currently the Judge has no test case in which the
input number is bigger than 510 000.
My program has an upper limit ( for the input number
it can process ) of 510 000.


INPUT

Code: Select all

0
1
2
3
4
5
6
7
8
9
10
101
2000
2521
5000
9999
30101
499999
500000
509990
509999
510000 

OUTPUT

Code: Select all

1 / 1
0 / 1
-1 / 1
-2 / 1
2 / 1
1 / 2
-1 / 2
-3 / 2
-3 / 1
3 / 1
3 / 2
5 / 9
41 / 2
-46 / 25
13 / 64
91 / 10
-19 / 157
72 / 641
71 / 641
-374 / 647
-383 / 647
-384 / 647

[Dominik Michniewski]

Hello, I got Accepted this problem but with very poor time (more than 7 sec).
Could anyone help me and tell how can I speed up it ?

I generate all values as in specification and use tree for eliminating duplicates. Is any faster algorithm ? From ranklist I hope that yes Maybe exist direct algorithm ? I know that most time-consuming parts of my algorithm are operations on the tree.

Best regards
DM

[Sedefcho]

Well, my ACC program is written in Java and runs for about 1.5 secs.
So I guess if I rewrite it in C++ it will run for about half of that time
( at least from the problems I have solved so far this is my impression
when comparing Java with C++ ). Sometimes that runtime ratio is even 1:3 or 1:5 ( talking about the same algorithm in C++ vs. Java ).

So if you your program is written in C++ the fact that it has a runtime
of 7 secs obviously means there's something in your algorithm which
is quite unefficient and could be optimized a lot.

I do not use trees I use just 4 large arrays. Which I think are used
exactly for eliminating doubles. Maybe that's where the speed up
comes from ( you use trees ).

So, Dominik, I can send you my code so that you compare
the algorithms on your own. It was a long time ago I solved
this one so I do not understand in details my algorithm

Regards

[DD]

Can anyone tell me how to solve 493 Rational Spiral ?
I have no idea at all. Thanx.

You can just directly simulate the whole process as problem defined, and prune the undesired rational spiral numbers.
The input limit and some test cases are already have some discussions in here (http://acm.uva.es/board/viewtopic.php?f ... acfa553906).

[L I M O N]

Can anyone tell me how to solve 493 Rational Spiral ?
I have no idea at all. Thanx.

idea here : http://www.youngprogrammer.com

[Hikari9]

You can actually check for reoccurences of fractions using a 2D boolean array to eliminate the O(nlogn) tree checking.
(although make sure to simplify the fraction first )

Code: Select all

bool vis[1500][1500]; // will be able to hold for inputs upto 510000

...

// checking part
if( den!=0 && vis[num+750][den+750]==false ){ // +750 for offset on negative numbers
   vis[num+750][den+750] = true; // visit

   ... // add fraction to your list

}