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?

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
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 :P

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.