## 136 - Ugly Numbers

Moderator: Board moderators

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
I am not sure. But something I just catch my attention.

You have generated 15^3 numbers by using the for loops.
Do you think that these 15^3 numbers are the 15^3 SMALLEST ugly numbers??

I don't think so. I think that 2^15 should be one of them.

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
i can increase from checking 15^3 numbers to more but how much should I do?

Is this the correct process?

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
I don't think it's the correct one~ since your approach can only generate some, say n, but not the smallest n ugly numbers.

Instead, you can try generate all ugly numbers less than a limit, say 2 x 10^9.

You can do that by multiply a number by 2 if it's less than the limit; multiply a number by 3 if it's less than the limit; multiply a number by 5 if it's less than the limit.[/code]

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
taj79 wrote: Is this the correct process?
There isn't "the" correct process. You sound a little bit as if there's only one approach to solve the problem.

Yes, yours will easily work if you make the exponents larger. Of course you will also produce some ugly numbers that are too large and therefore not really needed.

10153EN's tip to generate everything up to a limit can remove this waste. If you end up with fewer than 1500 ugly numbers, then you know your limit was too small and you just try it again with a larger limit.

Btw, there's a way to generate the first n ugly numbers in order with time and space O(n).

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
I did like this

for(r=0;r<25;r++)
for(q=0;q<80;q++)
for(p=0;p<300;p++)
{
u = ( pow(2,p)*pow(3,q)*pow(5,r) );
if(u > pow(2,1000) )
{/* printf("\n Exceeding\n"); */
continue; }
A[++t] = u;
}
My array size is 600000

the judge says it is wrong.

what should i do?
I can't make the size (array) 2400000
On running it gives segmentation fault.

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
You are nearly successful.

The last hint: try to check more carefully for your output with the sample output, some minor mistake would worth a WA.

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
I still can't figure out the mistake.
Could any one please give me more hint.
What does WA means.?

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
RTFM: http://acm.uva.es/problemset/replies.html

Sorry, don't want to offend anybody, but this is really getting annoying and some people are wasting their time here and some newbies exploit this and just don't care. I already stopped reading threads about specific problems two days ago. Exception: it's a problem I remember and I'm interested in it.

BIG BIG hint: the number you posted earlier is correct, now read the problem description again.

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
Please don't feel that I m misusing the board.
U said that my answer is correct.
On running my prog i m getting the output as

The 1500'th ugly number is 859963392 .

But thejudge says that wrong answer .

Is my answer is truly correct?

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
taj79, you are using the board in a right way. =)

If the following is your output:
The 1500'th ugly number is 859963392 .
I can tell you that your answer DIFFERS from the correct answer, what's different is not the value you computed.
Final hint: try to compare your answer, i.e. the above sentence, CHARACTER BY CHARACTER to that of the sample output.

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
I really can't see the difference.
I have submitted this prog:
Where's the diff between sample output and my output?

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
void sort(int A[],int t,int u);
void quicksort(double A[],int p,int r);
int partition(double A[],int p,int r);

main()
{ int t=0,i;
double p,q,r,u,A[1000000];

/* printf("\n 2^1000 = %.0f",pow(2,1000) );
u = ( pow(2,300)*pow(3,200)*pow(5,100) );
printf("\nu = %.0f",u);
if(u > pow(2,1000) )
printf("\n1");
else
printf("\n0");//exit(1);
printf("\n"); */
for(r=0;r<50;r++)
for(q=0;q<100;q++)
for(p=0;p<200;p++)
{
u = ( pow(2,p)*pow(3,q)*pow(5,r) );
if(u > pow(2,1000) )
{ /* printf("\n Exceeding\n"); */
continue; }
A[++t] = u;
/* if(t == 1)
A[1]= 1;
else
sort(A,t,u);
A[t]=u; */
/* if(A[t] < 0)
{ printf(" %d ",t);
exit(1);
} */
}
/* printf("t = %d\n",t);
printf("%.0f\n\n\n",A[t]);
printf("\n Before sorting: \n");
for(i=1;i<=1500;i++)
{ if(i%20 == 0)
printf("\n");
printf(" %.0f",A);
}
printf("\n\n\n\n\n Before entering quicksort\n\n"); */
quicksort(A,1,1000000);
/* printf("\n\n\n Exited quicksort\n\n");
printf("\n\n\n\n\n\n After sorting \n");
for(i=1;i<=1500;i++)
printf(" %.0f",A); */
/* printf("\n 1st number: %.0f",A[1]); */
printf("The 1500'th ugly number is %.0f.\n",A[1500]);
}

void quicksort(double A[],int p,int r)
{int q,count=0;
/* printf("\n\n Entered quicksort\n\n");
printf("p = %d r = %d\n",p,r); */
if(p<r){ ++count;
/* printf("%d",count); */
q = partition(A,p,r);
quicksort(A,p,q);
quicksort(A,q+1,r);
}
return;
}

int partition(double A[],int p,int r)
{ double x,u;
int i,j;
x = A[p];
i = p-1;
j = r+1;
while(1){
do{--j;
}while(A[j]>x);
do{ ++i;
}while(A<x);
if(i < j)
{ u = A ;
A= A[j];
A[j] = u;
}
else
return(j);
}
}

void sort(int A[],int t,int u)
{int y = t;
A[t] = u;
while(A[t] < A[t-1])
{
A[t] = A[t-1];
--t;
}
A[t]= u;
return;
}

Judge says
Your program has not solved the problem. It ran during 3.050 seconds.

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
Hello~

BTW, do you know there's a built-in function in C for quick sorting an array?

Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm
I just cut and pasted your code and got AC (although it's not the quickest implementation in the world...

Are you sure you've set up the problem number correctly in the code?
i.e. a line like:

/* @JUDGE_ID: *yourID* 136 C */

Failing that it is probably a problem with your email. Try sending using a different email (especially if you are using something like hotmail).

Mart.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
That's not quite correct, I believe? You did see a difference, because you removed the space before the ".". Btw, I just got your program accepted as is. Please read one of the many many other threads where email problems were already discussed...
Last edited by Stefan Pochmann on Wed Jun 19, 2002 5:19 am, edited 1 time in total.

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
My solution finally got accepted.
I really don't know what was the mistake in my last submission.
Anyway,THANKS to all of you for helping me out with my silly mistakes.

Hey stefan,
what does BTW means?