Page **1** of **2**

### 11226 - Reaching the fix-point.

Posted: **Sun Jun 10, 2007 5:48 am**

by **trulo17**

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**

by **sohel**

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**

by **little joey**

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**

by **DP**

What is the output for the following inputs?

I got

Just say is it wrong or correct?

Posted: **Sun Jun 10, 2007 9:36 am**

by **jan_holmes**

Yes, it is correct.

Posted: **Sun Jun 10, 2007 12:16 pm**

by **Spykaj**

Try:

90000 4560

489000 94561

Same answer, hihi

Posted: **Sun Jun 10, 2007 10:03 pm**

by **trulo17**

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;
}
```

Is it really that bad?

Posted: **Mon Jun 11, 2007 10:01 am**

by **sunny**

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**

by **trulo17**

I don't get your idea.....how you avoid factoring the numbers?

Posted: **Mon Jun 11, 2007 9:20 pm**

by **txandi**

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**

by **sohel**

or you can do a modified Sieve!

Posted: **Tue Jun 12, 2007 11:28 am**

by **sjn**

keeping WA...

which number's sopf function value is 15?

Posted: **Tue Jun 12, 2007 12:31 pm**

by **little joey**

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**

by **helloneo**

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**

by **sunny**

inclusive.