10049 - Self-describing Sequence

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

Moderator: Board moderators

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Fri Jul 15, 2005 4:26 am

At last, I got AC with a differente approach, thx a lot! :D

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

Post by midra » Tue Dec 20, 2005 5:56 am

how can I get the formula:
a(n+1) = 1 + a(n+1-a(a(n)))

I tried to get the formula for hours and I get nothing...I don't understand how to get to the formula, it doesn't seems obvious to me.
thanks...

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Tue Dec 20, 2005 5:20 pm

Hi, it's been 2 years since my post above...

The recursive formula is not required in this task. I just used loops (as somebody said above) and get a pretty simple solution.

Someone asked how I get f(2000000000) = 673365. "Trial and error", as you may call it... At first I guessed f(2000000000) <= 1000000, so I write a program with an array of 1000000 elements, and from that we get our result.

Have fun~
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

Post by midra » Wed Dec 21, 2005 1:18 am

thanks a lot!!! :D :D

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

10049

Post by serur » Wed Mar 29, 2006 12:58 am

Hello!

I remember hearing somewhere :D that 10049-Selfdescribing sequence is amenable to bisection method. Though I didn't consider this problem- for I have a long list of WA-s to consider :D - I want to know here is it so or not?

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Mon Apr 10, 2006 6:03 pm

Yes, You can store all the intervals, and for each input you should binary search on intervals. the order of algorithm is O(nlogn).

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Tue Apr 18, 2006 9:54 pm

Thank you Mohammad!

I'll elaborate your idea and see what happens. :D

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Wed Apr 19, 2006 9:44 am

Hi Moha!

Your hint was for me "like a ray of sunshine piercing through a fog", an Englishman would put it :), I did accopmplish its implementation, it passes all sample testcases, but OJ responded "WA".
So can you give me some I/O?
Also, since I got WA in 0.438, it will be of great moment to discuss how those nice fellows in 10049-ranklist got AC in 0.000.000.
Also, is it right that total amount of disjoint(I mean nonintersecting) intervals is about 162271?

Again, thank you.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Wed Apr 19, 2006 10:07 am

Well, I fixed my mistake - my program failed in just one case when n=2000000000; now AC in 0.426 - and I'm still curious about better solution in 0.00.000.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Wed Apr 19, 2006 10:27 pm

I took a look at my (Java) code that ran in .187 (or something like that) and it is not even optimized - e.g. I prebuild the sequence, but I calculate sums for each n in input. You can prebuild the sums and then find the answer by binary search. Hm, I might even try it - although I see a lot of .053 Java solutions, I bet I'll end up there :)

Darko

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Wed Apr 19, 2006 10:58 pm

Hm...
Prebuild... It's night and I spent last hours trying to improve my 10023 algo (if you have ideas, post please! :D ), so it's hard to grasp your idea at once - 'I'll try it tomorrow.

Thank you Darko for your reply, your time is about 2.5 times better than my as I see :D

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Wed Apr 19, 2006 11:50 pm

Hm, I just realized what I did there - maybe that's telling too much...

But from the example, try to see what happens if you add k first elements. Then see what's underneath the sum in the table :)

Darko

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Post by Leonid » Mon Aug 07, 2006 12:01 pm

Anyone cares to explain how is it possible to achieve 0.000 time on this problem? :)

User avatar
J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Location: Daffodil University,Dhaka,Bangladesh
Contact:

Thks a great forum...

Post by J&Jewel » Mon Aug 28, 2006 7:01 pm

Thaks to all these topics r helped me a lot..
I hate Wrong Answer!

User avatar
tany
New poster
Posts: 1
Joined: Wed Mar 21, 2007 6:58 pm
Location: Toulouse

10049 and recursive

Post by tany » Wed Mar 21, 2007 7:05 pm

Hi,
I saw the last topics about 10049, and nobody talk about the terminal recursion method ...
Is it possible to apply it for the 10049 problem ?
Because on my computer, do just a simple for loop from 1 to 20000000 take about 6 seconds !
And when I send my file with a non-terminal recursion method, the judge online indicates to me "Time limit exceeded", without surprises !
So, does anyone achieve the 10049 with a recursion method, or is it just impossible ?
Thank you.

Post Reply

Return to “Volume 100 (10000-10099)”