## Search found 429 matches

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 ...
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...
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...
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 ...
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...
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...
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).
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.
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...