Search found 429 matches

by Per
Tue Apr 29, 2003 10:51 pm
Forum: Volume 2 (200-299)
Topic: 280 - Vertex
Replies: 95
Views: 21583

My solution outputs: 83 12 13 15 16 17 18 19 20 21 22 23 24 26 27 29 30 31 32 34 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 83 12 13 15 16 17 18 19 20 ...
by Per
Tue Apr 29, 2003 10:24 pm
Forum: Volume 6 (600-699)
Topic: 643 - Bulk Mailing
Replies: 5
Views: 3466

The problem clearly states that: If there are 16 letters and you have to make a 3-digit bundle, you should combine the 15 with lowest zip code. One thing that is somewhat fuzzy is the letter count: with the number of letters and number of bundles for each zip code Suppose the number of letters for a...
by Per
Wed Apr 16, 2003 10:51 pm
Forum: Volume 2 (200-299)
Topic: 262 - Transferable Voting
Replies: 22
Views: 9774

262 - Transferable Voting

This seemingly simple problem turned out to be really troublesome for me. Judging from the accept-rate, it seems I'm not the only one having trouble. So what's the catch? I've tried having testcases with no candidates, no ballots, no valid ballots, etc. It also seems that the input format for candid...
by Per
Wed Apr 16, 2003 7:49 pm
Forum: Volume 3 (300-399)
Topic: 307 - Sticks
Replies: 56
Views: 17408

turuthok: your output is correct (or at least my accepted solution outputs the same). Here are the test cases I used. 57 50 49 48 43 32 29 28 17 14 13 12 12 9 8 6 28 29 12 32 48 40 8 13 9 49 12 43 17 14 50 2 3 3 2 1 2 37 30 19 2 31 3 12 31 31 23 9 5 49 4 23 49 43 50 25 24 8 8 10 21 14 13 11 9 6 4 3 ...
by Per
Sat Dec 14, 2002 3:45 pm
Forum: Algorithms
Topic: Prime Factors !!!!!!
Replies: 12
Views: 5739

Pollard-rho is quite simple, though it's very hard to see why it'll give good performance. Let f(x)=x^2+1 (mod N). Here is the Pollard-rho algrithm (in almost-C) [c]x = y = uniformly chosen random number in 0..N-1; d = 1; while (d == 1) { x = f(x); y = f(f(y)); d = gcd(y - x, N); } [/c] When the whi...
by Per
Sun Dec 08, 2002 10:19 pm
Forum: Algorithms
Topic: Prime Factors !!!!!!
Replies: 12
Views: 5739

Shahab, even though the idea used by Shor in his factorization algorithm for quantum computers is not directly related to quantum computing (as it's math!), it is not really possible to implement it efficiently on our common Turing machine-like computers. Shor's paper has been around for almost 10 y...
by Per
Thu Dec 05, 2002 10:40 pm
Forum: Volume 2 (200-299)
Topic: 283 - Compress
Replies: 16
Views: 6070

Ah, I got accepted. All strange test cases considered, it still came down to a silly array initialization bug.


I did something similar; a simple O(n^2) (which could triviallly be turned into O(n log n)) thing using dynamic programming (where n is the number of distinct characters in the text).
by Per
Sun Dec 01, 2002 9:55 pm
Forum: Volume 3 (300-399)
Topic: 333 - Recognizing Good ISBNs
Replies: 166
Views: 21035

Input:
0-8104-5687-7
0-8104-5687-7432
Output:
0-8104-5687-7 is correct.
0-8104-5687-7432 is incorrect.
So more than 10 digits can never be a valid ISBN.
by Per
Fri Nov 29, 2002 11:44 pm
Forum: Volume 2 (200-299)
Topic: 283 - Compress
Replies: 16
Views: 6070

Doing only the second case as it's smaller, 167 is what you get when using, for instance, this encoding scheme: [space] -> 000 b -> 001 e -> 010 h -> 011 i -> 100 o -> 101 t -> 110 a -> 111000 n -> 111001 q -> 111010 r -> 111011 s -> 111100 T -> 111101 u -> 111110 $ -> 1111110 . -> 11111110 , -> 111...

Go to advanced search