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.