136  Ugly Numbers
Moderator: Board moderators

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
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...)
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
preprocess then output is fine.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
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.

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
just solved it n.log(n)
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
[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
[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 = _max1;
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[i1];
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[k1]);
return 0;
}[/c]
#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 = _max1;
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[i1];
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[k1]);
return 0;
}[/c]

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
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
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
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.
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.

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
better solution... looks linear :D
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[i1]+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[k1]);
return 0;
}[/c]
i'm not sure it's linear... is this your solution? what do you think?
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[i1]+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[k1]);
return 0;
}[/c]
i'm not sure it's linear... is this your solution? what do you think?

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
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 k1 (or n1, 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 errorprone. Alternatively, I'd suggest you include the C++ header <algorithm> and then write
min( a, min( b, c ))
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 k1 (or n1, 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 errorprone. 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
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!
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!

 New poster
 Posts: 19
 Joined: Fri Oct 04, 2002 7:50 pm
 Location: Warsaw, Poland
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 underlinear 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.
problem that judge accepts inline asm in c++.
I just used three loops for logarithms and "jo" instruction
to detect overflows.
I think underlinear 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.

 Learning poster
 Posts: 93
 Joined: Sun Jan 12, 2003 3:30 pm
136  Ugly Numbers
What is the answer actually ?

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact: