11226  Reaching the fixpoint.
Moderator: Board moderators
11226  Reaching the fixpoint.
I precalculated 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.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.
What is the output for the following inputs?
I got
Just say is it wrong or correct?
Code: Select all
4560 90000
94561 489000
Code: Select all
12
14

 Experienced poster
 Posts: 136
 Joined: Fri Apr 15, 2005 3:47 pm
 Location: Singapore
 Contact:
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:
Is it really that bad?
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;
}

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
I guess you mean lsopfsjn wrote:keeping WA...
which number's sopf function value is 15?
There isn't one. And there's only one with value 14 (334142). That is, within the range of course.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.