## 11226 - Reaching the fix-point.

Moderator: Board moderators

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

### 11226 - Reaching the fix-point.

I pre-calculated in a reasonable time the half million values. Where I had problems was with answering the querys. I couldn't find anything better than the naive lineal search. I realized that the maximum value was 15, but couldn't use this fact at all. So.......how did you solve this task? It had a good number of accepted solutions during contest.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
The naive linear search is enough to pass the time limit.
The number of test cases and values of n,m aren't really that big to cause any worry.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I did exactly that: precalculation + linear search, which is fast enough. To improve on the speed of finding queries you could use a binary tree like structure, f.i. max(13,37)= max{max(13,13),max(14,15),max(16,31),max(32,35),max(36,37)}, which requires 5 lookups in stead of 25.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:
What is the output for the following inputs?

Code: Select all

``````4560 90000
94561 489000
``````
I got

Code: Select all

``````12
14
``````
Just say is it wrong or correct?

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:
Yes, it is correct.

Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm
Try:
90000 4560
489000 94561

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru
mmm..... I submited my contest solution and it passed in 1.754, so after what you said maybe my precalc step is too expensive.
This is my meoized function:

Code: Select all

``````int f(int x){
int &r=t[x];
if(r!=-1)return r;
int s=0,x2=x;
while(x%2==0){x/=2;s+=2;}
for(int i=3;i*i<=x;i+=2)while(x%i==0){x/=i;s+=i;}
if(x>1)s+=x;
if(x2==s)r=1;
else r=1+f(s);
return r;
}``````

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
u're prime factoring each number which costs some times.

instead of prime factoring every number u can generate all primes to 500000. and then do a backtrack over the primes to precalculate the answers. thus the precalculation will be in O(n).

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru
I don't get your idea.....how you avoid factoring the numbers?

txandi
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am
Instead of factoring, just try to think the inverse problem... If you know sopf, can you calculate sopf[j] where j is a multiple of i?

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
or you can do a modified Sieve!

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:
keeping WA...
which number's sopf function value is 15?

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
sjn wrote:keeping WA...
which number's sopf function value is 15?
I guess you mean lsopf
There isn't one. And there's only one with value 14 (334142). That is, within the range of course.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Hello..~
Your task is, given two natural numbers n and m (with n > 1 and m > 1), find the largest value the function lsopf takes in the interval between n and m.
Btw, the bounds n and m are inclusive..? or not inclusive..?

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
inclusive.