11226 - Reaching the fix-point.

[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.

[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.

[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.

[DP]

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]

Yes, it is correct.

[Spykaj]

Try:
90000 4560
489000 94561

Same answer, hihi

[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?

[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).

[trulo17]

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

[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?

[sohel]

or you can do a modified Sieve!

[sjn]

keeping WA...
which number's sopf function value is 15?

[little joey]

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.

[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..?

[sunny]

inclusive.