136 - Ugly Numbers

[shamim]

If somebody really want to get accepted that way, it's really easy to write
a brute force algorithm just to get the answer and then print it.

About this technique, The first time i saw the problem, the bruteforce method came to my mind. But I knew that it will never finish.

On a later day, I actually implemented the bruteforce method and set it running. While the program was running, i was thinking how to get the answer instantaneously. By the time my other program had finished, i came up with a solution and implemented it and got the answer in no time. Still the other program had not finished.

[Dominik Michniewski]

But if you think deeper, you could discover, that exists some pretty fast solutions for this problem :) i.e. using priority queue :)

Best regards
DM

PS. Not good time, but without cheating
2792 0:00.030 64 Dominik Michniewski C 1998/10/21-19:57:31.417 35279 (H0)

[Julien Cornebise]

hello...

I think for test your algo correct or not, you can try to solve problem "humble number " http://acm.uva.es/p/v4/443.html both of them can be solved with same algorithm.

Thanks, that's one more done...
I've just discovered STL and C++, and I shrunk my 79 lines C code done 1 year ago with a hand made priority queue to a 23 lines C++ code twice faster... I wonder why I didn't use it before

[junjieliang]

If I remember correctly, there were some discussion on this problem a while back. There's plenty of different algorithms for solving this problem, with varying runtime. I can think of O(n^2), O(n log n), O(n) algorithms which will all solve this problem.

[Rock]

When i submet the solution i got this reply:-
Your program has not solved the problem. It ran during 0.008 seconds.
-------------------------------------------------------------------------------------

class Main
{
public static void main(String a[])
{
int count=0;
for(int i=1;count<=1500;i++)
{
if(i==1) count++;

if(i%2==0)
{
int x=i/2;
if(isPrime(x))
if(isUgly(x))
count++;
else
continue;
else
count++;
}
else if(i%3==0)
{
int x=i/3;
if(isPrime(x))
if(isUgly(x))
count++;
else
continue;
else
count++;


}
else if(i%5==0)
{
int x=i/5;
if(isPrime(x))
if(isUgly(x))
count++;
else
continue;
else
count++;
}

if(count==1500)
{ System.out.println("The 1500'th ugly number is "+i);
break;
}
}
}
static boolean isPrime(int i)
{
if (i % 2 == 0) return false;
else if (i==0)return false;
else if(i==2)return true;

for (int j = 2; j < Math.sqrt(i); j++)
if (i % j == 0) return false;

return true;

}

static boolean isUgly(int i)
{
if(i==2|i==3)return true;
else if(i==5|i==1)return true;
else
return false;
}
}

[_.B._]

Never mind!, it is Time Limit indeed.

Greetings!.
I made the 136 in Pascal, and it runs just fine.
Thing is, it takes a great deal of time to solve it.
Even when it doesn't say it's a "Time Limit" problem, is it?.
Don't want to submit it before I'm sure it's not TL.

Thanks in advance!.

B.

[El-idioto]

Hi rock,

I simply add as many factors as will fit within a certain range.
You can supply any range you like, as long as there are at least n (in this case 1500) ugly numbers in the range.
By calculating the entire 64-bit unsigned range, I found the following amount of ugly numbers:

Code: Select all

RANGE g_range[21] =
{
                     1,     1,
                    10,     9,
                   100,    34,
                  1000,    86,
                 10000,   175,
                100000,   313,
               1000000,   507,
              10000000,   768,
             100000000,  1105,
            1000000000,  1530,
           10000000000,  2053,
          100000000000,  2683,
         1000000000000,  3429,
        10000000000000,  4301,
       100000000000000,  5310,
      1000000000000000,  6466,
     10000000000000000,  7780,
    100000000000000000,  9259,
   1000000000000000000, 10941,
  10000000000000000000, 13790,
  18446744073709551615, 41853
};

As you can see, we only need to check the range [0, 1000000000].
Basically, this is what you do:
[cpp]
// Calculate the maximum powers for 2, 3, and 5
u8MaxPower2 = (uint8)(log((double)u64Max) / log(2.0));
u8MaxPower3 = (uint8)(log((double)u64Max) / log(3.0));
u8MaxPower5 = (uint8)(log((double)u64Max) / log(5.0));

// Keep adding factors of 5 while we are within the range
for(uint8 u8Factor5=0;u8Factor5<=u8MaxPower5;u8Factor5++)
{
// Keep adding factors of 3 while we are within the range
for(uint8 u8Factor3=0;u8Factor3<=u8MaxPower3;u8Factor3++)
{
// Keep adding factors of 2 while we are within the range
for(uint8 u8Factor2=0;u8Factor2<=u8MaxPower2;u8Factor2++)
{
// Is the ugly number within the range?
pu64Ugly[u16TotUgly] = g_pu64Pow2[u8Factor2] * g_pu64Pow3[u8Factor3] * g_pu64Pow5[u8Factor5];
if(pu64Ugly[u16TotUgly] <= u64Max)
u16TotUgly++;
else
break;
}
}
}
[/cpp]
My complete program is as follows:
[cpp]
// @JUDGE_ID: 33444KK 136 C++
//
// 136_UglyNumbers: Find the nth number which is only divisible by 2,3, or 5
//


#include <cstdio>
#include <cmath>

// The base types
#ifdef WIN32
typedef __int8 int8;
typedef __int16 int16;
typedef __int32 int32;
typedef __int64 int64;
typedef unsigned __int8 uint8;
typedef unsigned __int16 uint16;
typedef unsigned __int32 uint32;
typedef unsigned __int64 uint64;
#else
typedef char int8;
typedef short int16;
typedef long int32;
typedef long long int int64;
typedef unsigned char uint8;
typedef unsigned short uint16;
typedef unsigned long uint32;
typedef unsigned long long int uint64;
#endif

// These macros safely delete (an array of) objects
#define SAFE_DELETE(pObj) { if(pObj) { delete pObj; pObj = NULL; } }
#define SAFE_DELETE_ARRAY(pArr) { if(pArr) { delete[] pArr; pArr = NULL; } }

// The 2^n table
uint64 g_pu64Pow2[64] =
{
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768,
65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216,
33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648,
4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472,
274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104,
8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328,
281474976710656, 562949953421312, 1125899906842624, 2251799813685248,
4503599627370496, 9007199254740992, 18014398509481984, 36028797018963968,
72057594037927936, 144115188075855872, 288230376151711744, 576460752303423488,
1152921504606846976, 2305843009213693952, 4611686018427387904, 9223372036854775808
};

// The 3^n table
uint64 g_pu64Pow3[42] =
{
1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323,
4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203,
31381059609, 94143178827, 282429536481, 847288609443, 2541865828329, 7625597484987,
22876792454961, 68630377364883, 205891132094649, 617673396283947, 1853020188851841,
5559060566555523, 16677181699666569, 50031545098999707, 150094635296999121,
450283905890997363, 1350851717672992089, 4052555153018976267, 12157665459056928801,
18026252303461234787
};

// The 5^n table
uint64 g_pu64Pow5[28] =
{
1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625, 48828125, 244140625,
1220703125, 6103515625, 30517578125, 152587890625, 762939453125, 3814697265625,
19073486328125, 95367431640625, 476837158203125, 2384185791015625, 11920928955078125,
59604644775390625, 298023223876953125, 1490116119384765625, 7450580596923828125
};

struct RANGE
{
uint64 u64Max; // The highest possible ugly number
uint16 u16TotCount; // The amount of ugly numbers in the range [1,u64Max]
};

// The amount of ugly numbers in the range [1,u64Max];
RANGE g_range[21] =
{
1, 1,
10, 9,
100, 34,
1000, 86,
10000, 175,
100000, 313,
1000000, 507,
10000000, 768,
100000000, 1105,
1000000000, 1530,
10000000000, 2053,
100000000000, 2683,
1000000000000, 3429,
10000000000000, 4301,
100000000000000, 5310,
1000000000000000, 6466,
10000000000000000, 7780,
100000000000000000, 9259,
1000000000000000000, 10941,
10000000000000000000, 13790,
18446744073709551615, 41853
};


// The ugly number
#define NTH_UGLY_NUMBER 1500

// The function prototypes
void GetUglyNumbers(uint64 *pu64Ugly, uint64 u64Max);
void QuickSort(uint64 *pu64Ugly, int32 i32LeftOrg, int32 i32RightOrg);


//-------------------------------------------------------------
// F U N C T I O N S
//-------------------------------------------------------------


// This function is the entrance of the app
int main()
{
// Get the upper limit of the ugly number
for(uint8 u8=0;u8<21;u8++)
{
// Are there enough ugly numbers?
if(g_range[u8].u16TotCount > NTH_UGLY_NUMBER)
{
uint64 *pu64UglyNumbers;

// Allocate a new buffer to hold the ugly numbers
pu64UglyNumbers = new uint64[g_range[u8].u16TotCount+1];

// Find all the ugly numbers in the range [1,N]
GetUglyNumbers(pu64UglyNumbers, g_range[u8].u64Max);

// Show the requested number
printf("The 1500'th ugly number is %I64u.", pu64UglyNumbers[NTH_UGLY_NUMBER-1]);

// Free the resources
SAFE_DELETE_ARRAY(pu64UglyNumbers);
break;
}
}

return 0;
}


//-------------------------------------------------------------


// This function locates all the ugly numbers in the range [u64Min,u64Max]
void GetUglyNumbers(uint64 *pu64Ugly, uint64 u64Max)
{
uint8 u8MaxPower2, u8MaxPower3, u8MaxPower5;
uint16 u16TotUgly = 0;

// Calculate the maximum powers for 2, 3, and 5
u8MaxPower2 = (uint8)(log((double)u64Max) / log(2.0));
u8MaxPower3 = (uint8)(log((double)u64Max) / log(3.0));
u8MaxPower5 = (uint8)(log((double)u64Max) / log(5.0));

// Keep adding factors of 5 while we are within the range
for(uint8 u8Factor5=0;u8Factor5<=u8MaxPower5;u8Factor5++)
{
// Keep adding factors of 3 while we are within the range
for(uint8 u8Factor3=0;u8Factor3<=u8MaxPower3;u8Factor3++)
{
// Keep adding factors of 2 while we are within the range
for(uint8 u8Factor2=0;u8Factor2<=u8MaxPower2;u8Factor2++)
{
// Is the ugly number within the range?
pu64Ugly[u16TotUgly] = g_pu64Pow2[u8Factor2] * g_pu64Pow3[u8Factor3] * g_pu64Pow5[u8Factor5];
if(pu64Ugly[u16TotUgly] <= u64Max)
u16TotUgly++;
else
break;
}
}
}

// Sort the values
QuickSort(pu64Ugly, 0, u16TotUgly-1);
}


//-------------------------------------------------------------


// This function uses the quick sort algorithm to sort elements
void QuickSort(uint64 *pu64Ugly, int32 i32LeftOrg, int32 i32RightOrg)
{
int32 i32Left, i32Right;
uint64 u64Mid;

// Get the left and right positions
i32Left = i32LeftOrg;
i32Right = i32RightOrg;

// Get the middle element (hopefully also somewhere in the middle value-wise)
u64Mid = pu64Ugly[(i32Left + i32Right) / 2];

// Let the left and right positions walk towards each other until they pass each other
while(i32Right >= i32LeftOrg && i32Left <= i32RightOrg)
{
// Find the left-most element which is too high to be on the left side of the middle element
while(u64Mid > pu64Ugly[i32Left]) i32Left++;

// Find the right-most element which is too low to be on the right side of the middle element
while(pu64Ugly[i32Right] > u64Mid) i32Right--;

// Have the left and right pointer not yet passed each other?
if(i32Left <= i32Right)
{
// Are the left and right element different elements?
if(i32Left < i32Right)
{
uint64 u64Temp;

// Swap the elements which are on the wrong side of the middle element
u64Temp = pu64Ugly[i32Left];
pu64Ugly[i32Left] = pu64Ugly[i32Right];
pu64Ugly[i32Right] = u64Temp;
}

// Step towards each other
i32Left++;
i32Right--;
}
else break;
}

// Have we not yet walked all the way from the right element to the left element?
if(i32LeftOrg < i32Right) QuickSort(pu64Ugly, i32LeftOrg, i32Right);

// Have we not yet walked all the way from the left element to the right element?
if(i32Left < i32RightOrg) QuickSort(pu64Ugly, i32Left, i32RightOrg);
}[/cpp]

[HerrAachen]

I just wrote an algorithm for the ugly numbers problem. Running my prog is probably going to take several hours although I already tried to optimize my code slightly. How do these people in the ranking list achieve times like 0.00.000? Do they just submit codes like:

#include <stdio.h>
void main()
{
printf("The number is 895640402 or whatever.");
}

What is this? Where do these running times come from?

[Adrian Kuegel]

Probably a lot of people use the printf("") solution.
But it is possible to solve this problem in O(n) time. My program got also accepted with 0 seconds, but it uses O(n) time and space. Well, it was at the time when the runtime was rounded to nearest 1/100 of a second. Now it is rounded to nearest 1/1000 of a second, so perhaps it is not possible now to get Accepted in 0 seconds.
By the way, there are already a lot of threads for this problem, why did you open a new one?
http://online-judge.uva.es/board/viewtopic.php?t=93
http://online-judge.uva.es/board/viewtopic.php?t=2749
http://online-judge.uva.es/board/viewtopic.php?t=3586

[junbin]

I just wrote an algorithm for the ugly numbers problem. Running my prog is probably going to take several hours although I already tried to optimize my code slightly. How do these people in the ranking list achieve times like 0.00.000? Do they just submit codes like:

#include <stdio.h>
void main()
{
printf("The number is 895640402 or whatever.");
}

What is this? Where do these running times come from?

There is another question very similar to this (443). My personal take is that for questions such as 136 where you are only asked to print one number, there is no point including the entire generation code. Therefore, for 136, I sent in a 5 line code (ie: the printf). But to test your algorithm, I suggest trying 443.

[HerrAachen]

I think there is a point in posting the whole code, because it is quite tricky (in my view) to achieve running times below the time limit. But it's easy to write some slow algorithm, let the prog run 8 hours or whatever, write down the number and post the "printf("There you go")"-version.

(sorry about creating a new thread. Didn't see that other one)

Herr Aachen

[DavidDeharbe]

As an educator, I tend to agree that contests should allow functional languages - they allow for quick experimentation of ideas and are a natural medium to practice programming as an art. In that sense, I would suggest SCHEME and OCAML.

As for spending hours polishing code to shave milliseconds off of execution time, this is indeed not the spirit of the ACM contest, much more a by-product of the UVA maintaining a ranking of the solutions based on execution time. And this is craftmanship.

Cheers,

David.

[nibbler]

my code:
[cpp]#include <queue>
#include <iostream>
using namespace std;

int main() {
priority_queue < unsigned long long, vector <unsigned long long> , greater <unsigned long long> > PQ;
PQ.push(1);
for (int i=0;i<1499;i++) {
if (PQ.top()%5!=0 && PQ.top()%3!=0) PQ.push(PQ.top()*2);
if (PQ.top()%5!=0) PQ.push(PQ.top()*3);
PQ.push(PQ.top()*5);
PQ.pop();
}
cout << "The 1500'th ugly number is " << PQ.top() << "." << endl;
return 0;
}[/cpp]

[PerHagen]

my code is
program acm136;
var
i,cont:integer;
begin
i:=1;
cont:=1;
while (cont<>1500) do
begin
if ((i mod 2=0) or (i mod 3=0) or (i mod 5=0))then inc(cont);
inc(i);
end;
writeln('The 1500',#39,'th ugly number is' ,i);
end.

but is bad!!
i don't understan
#39=';
help me

[Ghust_omega]

Hi !! Perhagen ,what its wrong with your code is WA, TLE , and your answer can post here to compare
Hope it Help
Keep posting