Page 1 of 2

### 11226 - Reaching the fix-point.

Posted: Sun Jun 10, 2007 5:48 am
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.

Posted: Sun Jun 10, 2007 6:17 am
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.

Posted: Sun Jun 10, 2007 8:44 am
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.

Posted: Sun Jun 10, 2007 9:10 am
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? Posted: Sun Jun 10, 2007 9:36 am
Yes, it is correct.

Posted: Sun Jun 10, 2007 12:16 pm
Try:
90000 4560
489000 94561

Same answer, hihi Posted: Sun Jun 10, 2007 10:03 pm
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;
}``````

Posted: Mon Jun 11, 2007 10:01 am
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).

Posted: Mon Jun 11, 2007 9:12 pm
I don't get your idea.....how you avoid factoring the numbers?

Posted: Mon Jun 11, 2007 9:20 pm
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?

Posted: Tue Jun 12, 2007 6:15 am
or you can do a modified Sieve!

Posted: Tue Jun 12, 2007 11:28 am
keeping WA... which number's sopf function value is 15?

Posted: Tue Jun 12, 2007 12:31 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.

Posted: Wed Jun 13, 2007 5:36 pm
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..?

Posted: Wed Jun 13, 2007 5:46 pm
inclusive.