Page **3** of **11**

Posted: **Wed Jun 19, 2002 5:16 am**

by **Stefan Pochmann**

BTW = By The Way

And sorry for my offensiveness. Every once in a while I get tired and say mean things I shouldn't. But you really asked some questions that you could've easily answered yourself, I think. Try finding things out yourself, otherwise you'll always depend on others to help you... for example enter "acronym" and "btw" in Google and with the first page you'll find out that

BTW = Belasting over de Toegevoegde Waarde

(or that other meaning I gave above)

(Also, I just found out that I had mistaken you for somebody else...)

### 160 answear

Posted: **Tue Nov 12, 2002 6:33 pm**

by **naps90**

necropower wrote:hey guys, i solved the 136 problem[ugly numbers] , but i cant see HOW can i solve it in 0 SECONDS!! i take at least 3 or 4 seconds to do that[using quicksort in a array] , is there a equation to solve that problem? can u help me??

[[]] Necropower

preprocess then output is fine.

However,I think I have an O(n) method (very fast,the constant is

3 or less).

I posted it,but I get WA.

Can I send you my ansear (and the linear algorithm

and just tell me wether it was your answear.

Posted: **Tue Nov 12, 2002 7:14 pm**

by **Stefan Pochmann**

Yeah, show me your linear time algorithm. I'd be happy to talk about our solutions.

### just solved it n.log(n)

Posted: **Wed Nov 13, 2002 7:29 pm**

by **epsilon0**

of course i cheated and sent a lame

[c]#include <stdio.h>

int main()

{

printf("The 1500'th ugly number is ********.\n");

return 0;

}[/c]

BUT here is the explanation of my N LOG N algo:

my algo was as follow... store the ith first ugly numbers in an array.

you know the i+1th ugly number is an ugly number ou already know multiplied by 2, 3 or 5.

so you try to guess this ugly number. it's easy, let's say the ith ugly number is N. you know the numbers you need to look for are close to N/2 N/3 and N/5.

call them mul2 mul3 and mul5, then all you have to do is pick the smallest among mul2*2, mul3*3 and mul5*5.

since looking for a number in an ordered array is log(n), and you do it n times, the solution is n.log(n) (roughly)

there is a constant = 3, due to the fact you look 3 times in the array.

please tell me how you did it if you have a log(n) algo, i'm really curious about it

### and here is my n.log(n) program that runs in 0.00 on my PC

Posted: **Wed Nov 13, 2002 7:34 pm**

by **epsilon0**

[c]#include <stdio.h>

#define MIN(a,b,c) ((a) > (b) ? ((b) > (c) ? (c) : (b)) : ((a) > (c) ? (c) : (a)))

int ugly[1500];

int find(int _max,int target)

{

int max = _max-1;

int middle;

int min = 0;

while (min < max)

{

middle = (min + max)/2;

if (ugly[middle] < target)

min = middle+1;

else

max = middle;

}

return ugly[max];

}

int main()

{

int k = 1500;

int mul2,mul3,mul5;

int i,target;

ugly[0]=1;

for (i=1;i<k;i++)

{

target=ugly[i-1];

mul2 = find(i,target/2+1);

mul3 = find(i,target/3+1);

mul5 = find(i,target/5+1);

ugly* = MIN(2*mul2,3*mul3,5*mul5);*

}

printf("The %d'th ugly number is %d.\n",k,ugly[k-1]);

return 0;

}[/c]

Posted: **Wed Nov 13, 2002 8:15 pm**

by **Stefan Pochmann**

epsilon0, you're very close to my linear time solution. The big difference is that I don't search for mul2, mul3 and mul5. I know where to look them up in constant time.

No idea about a logarithmic solution and I doubt that there is one. It's easy to see that an O(n) solution is optimal for the reporting variant (where you compute the first n ugly numbers), though, so I'm at least proud of that

### please drop a few hints

Posted: **Wed Nov 13, 2002 8:56 pm**

by **epsilon0**

care to share your knowledge?

i see why your solution is O(n). but how do you manage to look up ugly numbers in O(1)?

do you use a hash function?

seriously, you cannot have an array A big enough to store an ugly number U as A

= 1; it has to be a hash... but i still don't see.

Posted: **Thu Nov 14, 2002 6:56 am**

by **Stefan Pochmann**

No hash and no arrays as large as the numbers. Here's a spoiler: I have three queues, one for each prime factor, and the total number of numbers added to the queues doesn't exceed 3n.

### better solution... looks linear :D

Posted: **Thu Nov 14, 2002 11:54 am**

by **epsilon0**

ok i figured it's useless to test all the ugly numbers each time... the numbers you pick in each of the 3 queues are in ascending order.

so here's my solution with 3 "pointers":

[c]#include <stdio.h>

#define MIN(a,b,c) ((a) > (b) ? ((b) > (c) ? (c) : (b)) : ((a) > (c) ? (c) : (a)))

int ugly[1500];

int main()

{

int k = 1500;

int index2=0, index3=0, index5=0;

int candidate2, candidate3, candidate5;

int i,target;

ugly[0]=1;

for (i=1;i<k;i++)

{

target=ugly[i-1]+1;

while((candidate2 = 2 * ugly[index2]) < target) index2++;

while((candidate3 = 3 * ugly[index3]) < target) index3++;

while((candidate5 = 5 * ugly[index5]) < target) index5++;

ugly* = MIN(candidate2, candidate3, candidate5);*

}

printf("The %d'th ugly number is %d.\n",k,ugly[k-1]);

return 0;

}[/c]

i'm not sure it's linear... is this your solution? what do you think?

Posted: **Thu Nov 14, 2002 2:55 pm**

by **Stefan Pochmann**

1) It is linear.

2) It is not exactly like mine.

3) It is better than mine.

Why?

1) Your whole work is done inside the loop, which is executed k-1 (or n-1, we called used to call it n) times. Inside you have two constant time commands and three loops. In one iteration of the outer loop, each inner loop could take long, but if you look at the computation as a whole, the time spend in each of the inner loops is O(k), since each "index" starts at 0, is increased with every inner loop iteration, never set back and never exceeds k. So even though a single outer loop iteration might take long, the overall average for one iteration is constant time. Similar to convex hull finding with Graham's Scan.

2) I have three queues, one for numbers that can still be multiplied by {2,3,5}, one for numbers that can still be multiplied by {3,5} and one for {5}. See below.

3) We both need linear time, but my memory usage is higher. Don't know how much, since for example my first queue only contains {1,2,4,8,16,...}, so you probably don't win much. The third queue gets k numbers pushed into it, but I don't know about the second one. And the situation might get worse if we look at the "superugly" numbers built from {2,3,5,7,11} or even more primes.

Here's mine:

[cpp]

#include <iostream>

#include <queue>

using namespace std;

int main () {

int factor[] = { 2, 3, 5 };

queue<int> lists[3];

//----- Everybody can only extend 1.

for( int i=0; i<3; ++i )

lists*.push( 1 );*

//----- Simulate by extending.

for( int i=1; i<1500; ++i ){

//--- Calculate next number for each factor.

int next[3];

for( int j=0; j<3; ++j )

next[j] = lists[j].front() * factor[j];

//--- Find the winner (factor with smallest next number).

int winner = 0;

for( int j=1; j<3; ++j )

if( next[j] < next[winner] )

winner = j;

//--- Extend.

for( int i=winner; i<3; ++i )

lists*.push( next[winner] );*

lists[winner].pop();

}

//----- Answer.

cout << "The 1500'th ugly number is " << lists[2].back() << ".\n";

}

[/cpp]

Btw, I'd suggest this minOfThree:

#define MIN(a,b) (((a)<(b)) ? (a) : (b))

#define MIN3(a,b,c) MIN(a,MIN(b,c))

I think this is less error-prone. Alternatively, I'd suggest you include the C++ header <algorithm> and then write

min( a, min( b, c ))

### actually it can be made even faster

Posted: **Thu Nov 14, 2002 7:16 pm**

by **epsilon0**

your solution is pretty smart, especially the fact that you don't always add the new ugly numbers in all 3 queues... on the other hand this causes extra computation and i'm not sure it's worth it. i still don't fully understand how you manage to always have the 3 candidates in front of your queue.

i improved my program with the use of pointers:

[c]#include <stdio.h>

#define FINDME 1500

#define MIN(a,b) ((a)>(b)?(b):(a))

#define MIN3(a,b,c) MIN(a,MIN(b,c))

int ugly[FINDME];

int main()

{

int k = FINDME;

int *last = ugly, *next = ugly + 1, *end = ugly + k;

int *pointer2 = last, *pointer3 = last, *pointer5 = last;

int candidate2, candidate3, candidate5;

int target;

*last = 1;

while(next < end)

{

target = *last + 1;

while((candidate2 = 2 * *pointer2) < target) pointer2++;

while((candidate3 = 3 * *pointer3) < target) pointer3++;

while((candidate5 = 5 * *pointer5) < target) pointer5++;

*next++ = MIN3(candidate2, candidate3, candidate5);

last++;

}

printf("The %d'th ugly number is %d.\n",k,*last);

return 0;

}[/c]

and just to prove that it's possible to get a 0.000 without "cheating":

Your C program has solved Ok the problem 136 (Ugly Numbers)

in 0.000 seconds with low memory spent.

Congratulations!

Posted: **Thu Nov 21, 2002 2:09 am**

by **wsarzynski**

Your solution is really good. Myself, i learned from this

problem that judge accepts inline asm in c++.

I just used three loops for logarithms and "jo" instruction

to detect overflows.

I think under-linear complexity algorithm is possible if "easy & dense" subset of ugly numbers exists, ie for numbers of some special form you can know it's position in constant time, so you can localize your number.

Anybody seen something like this ? I tried, no results as for now.

Also, I draw ugly numbers in gnuplot, and in small scale with interpolation it seems like some fractal curve.

### 136 - Ugly Numbers

Posted: **Tue Apr 22, 2003 11:11 am**

by **Almost Human**

What is the answer actually ?

Posted: **Tue Apr 22, 2003 1:20 pm**

by **little joey**

42, of course!

Posted: **Wed Apr 23, 2003 8:31 am**

by **Dominik Michniewski**

nice

DM