11226 - Reaching the fix-point.

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

11226 - Reaching the fix-point.

Post by trulo17 » Sun Jun 10, 2007 5:48 am

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.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sun Jun 10, 2007 6:17 am

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Jun 10, 2007 8:44 am

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.

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by DP » Sun Jun 10, 2007 9:10 am

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
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Sun Jun 10, 2007 9:36 am

Yes, it is correct.

User avatar
Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm

Post by Spykaj » Sun Jun 10, 2007 12:16 pm

Try:
90000 4560
489000 94561

Same answer, hihi :P

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

Post by trulo17 » Sun Jun 10, 2007 10:03 pm

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
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny » Mon Jun 11, 2007 10:01 am

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
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

Post by trulo17 » Mon Jun 11, 2007 9:12 pm

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

txandi
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am

Post by txandi » Mon Jun 11, 2007 9:20 pm

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?

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Tue Jun 12, 2007 6:15 am

or you can do a modified Sieve!

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Post by sjn » Tue Jun 12, 2007 11:28 am

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Jun 12, 2007 12:31 pm

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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Wed Jun 13, 2007 5:36 pm

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
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny » Wed Jun 13, 2007 5:46 pm

inclusive.

Post Reply

Return to “Volume 112 (11200-11299)”