Search found 112 matches

by epsilon0
Thu Nov 14, 2002 11:54 am
Forum: Volume 1 (100-199)
Topic: 136 - Ugly Numbers
Replies: 156
Views: 18064

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]; i...
by epsilon0
Wed Nov 13, 2002 8:56 pm
Forum: Volume 1 (100-199)
Topic: 136 - Ugly Numbers
Replies: 156
Views: 18064

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.
by epsilon0
Wed Nov 13, 2002 7:34 pm
Forum: Volume 1 (100-199)
Topic: 136 - Ugly Numbers
Replies: 156
Views: 18064

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 = _max-1; int middle; int min = 0; while (min < max) { middle = (min + max)/2; if (ugly[middle] < target) min = middle+1; else max = middle...
by epsilon0
Wed Nov 13, 2002 7:29 pm
Forum: Volume 1 (100-199)
Topic: 136 - Ugly Numbers
Replies: 156
Views: 18064

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 nu...
by epsilon0
Wed Nov 13, 2002 3:44 pm
Forum: Volume 3 (300-399)
Topic: 305 - Joseph
Replies: 41
Views: 3737

0.002 seconds with a little trick

Your C program has solved Ok the problem 305 (Joseph) in 0.002 seconds with low memory spent. Congratulations! here is the code (answers for k>4 hidden): [c]#include <stdio.h> int solution[14] = {0,2,7,5,30,*,*,*,*,*,*,*,*,*}; int main() { int k; while(scanf("%d",&k) && k != 0) printf("%d\n",solutio...
by epsilon0
Tue Nov 12, 2002 11:31 pm
Forum: Volume 3 (300-399)
Topic: 305 - Joseph
Replies: 41
Views: 3737

305 - Joseph

i looked at Joseph (315) and saw on this board someone that oculd not solve it faster than 29s. this kind of problem can be solved fast very easily, because there are only 13 possible values. they say each line is a 0<k<13 so you compute f(k) for each k on your home PC , then write something like: w...
by epsilon0
Tue Nov 12, 2002 11:19 pm
Forum: Volume 3 (300-399)
Topic: 315 - Network
Replies: 68
Views: 21324

hello, i'm new here, just solved 315

hello everyone, i'm a depressed loser and found this site as i was looking for programming challenges/wargames on the internet... this site is very cool, there are a lot of problems too hehe after a first tryon problem 315, i found out my program was too slow, and redesigned it almost entirely, and ...

Go to advanced search