## Search found 90 matches

Wed Aug 18, 2004 3:35 pm
Forum: Volume 3 (300-399)
Topic: 331 - Mapping the Swaps
Replies: 11
Views: 5901

### 331 speed

I wanted to ask if there is a better way to approach 331. I did this problem by counting the number of inversions to tell me the minimum number of swaps, then from there I generated all possible swap sequences of that size by brute force. When #inversions==10, the only case is a list of length 5 com...
Wed Aug 18, 2004 8:18 am
Forum: Volume 100 (10000-10099)
Topic: 10066 - The Twin Towers
Replies: 35
Views: 13229
I am getting P.E. for this problem. I wish some of these problems would explicitly specify where you are supposed to put newlines. ^^; I have tried always putting two newlines after a test case, as well as putting two newlines after each test case but only one newline after the last one, but both go...
Wed Aug 18, 2004 6:50 am
Forum: C
Topic: Need correct syntax
Replies: 3
Views: 2051
[EDIT]
ok i'm newb
[/EDIT]
Wed Aug 18, 2004 6:08 am
Forum: Volume 102 (10200-10299)
Topic: 10267 - Graphical Editor
Replies: 190
Views: 52676
If I understand the problem statement correctly, there can be errors in the commands given, such as for example the user entering the 'C' command before the 'I' command. In your code, sizex and sizey would not yet be set if the first command was 'C', and thus could be some arbitrary value. Thus when...
Wed Aug 18, 2004 2:24 am
Forum: Volume 5 (500-599)
Topic: 562 - Dividing coins
Replies: 73
Views: 30354
AC. I changed [c] for (i = 1; i <= sum; i++) if (possible && ABS(2 * i - sum) < min) min = ABS(2 * i - sum); [/c] to this: [c] for (i = 0; i <= sum; i++) if (possible && ABS(2 * i - sum) < min) min = ABS(2 * i - sum); [/c] Basically the problem is that the problem statement says that ncoins is a non...
Tue Aug 17, 2004 4:37 pm
Forum: Volume 5 (500-599)
Topic: 562 - Dividing coins
Replies: 73
Views: 30354
hm..i guess i must have changed something after all. i copy/pasted your source again and resubmitted and now got WA..i don't remember changing anything though the first time ^^;

wait 'til tomorrow morning when i get to work, and i'll see what i did
Tue Aug 17, 2004 6:38 am
Forum: Volume 106 (10600-10699)
Topic: 10615 - Rooks
Replies: 12
Views: 4568
We have a bipartite graph with first set of vertices representing rows & second set of vertices representing columns. Row vertex is connected with appropriate column vertex if and only if there is a rook in the appropriate cell. How do we have a bipartite graph? Don't we have a k-partite graph with...
Tue Aug 17, 2004 4:27 am
Forum: Volume 5 (500-599)
Topic: 562 - Dividing coins
Replies: 73
Views: 30354
i submitted your code just as it is and it got AC. maybe it's the way you are submitting it? i tend to just submit via http://online-judge.uva.es/problemset/submit.php to avoid any of the weird errors that can occur from submitting via email.
Tue Aug 17, 2004 3:39 am
Forum: Volume 3 (300-399)
Topic: 383 - Shipping Routes
Replies: 27
Views: 6036
hm, i just tried this problem to see and also got PE... i followed your advice about only one blank line when p==0, but still PE here are the parts of my code that actually involve newlines: [c] printf("SHIPPING ROUTES OUTPUT\n\n"); for (caseno=0;caseno<cases;caseno++) { printf("DATA SET %d\n\n",cas...
Tue Aug 17, 2004 2:45 am
Forum: C
Topic: bignum using multiple int's
Replies: 2
Views: 1775

### bignum using multiple int's

Many people make their own bignum classes which are basically digit arrays, but I feel like there should be a way to do it with int arrays (the first int represents 2^0 to 2^31, the next one represents 2^32 to 2^63, etc.) which would be much more efficient. However, I am not familiar enough with the...
Mon Aug 16, 2004 6:18 am
Forum: Volume 106 (10600-10699)
Topic: 10689 - Yet another Number Sequence
Replies: 22
Views: 11642
I find matrix method the best... I think it depends what you mean by best. I used this first also because I already had it pre-coded from doing other fibonacci-type problems. But this method runs slower than the periodic method, and it is also more lines to code if you don't have it coded up already.
Mon Aug 16, 2004 4:02 am
Forum: Volume 3 (300-399)
Topic: 374 - Big Mod
Replies: 79
Views: 12011
your algorithm grows exponentially because you calculate bigmod twice. [c] else if (p%2==0) return (bigmod(b,p/2,m))*(bigmod(b,p/2,m))%m [/c] should be [c] else if (p%2==0) return square((bigmod(b,p/2,m)))%m; [/c] define the square function somewhere. or do [c] temp = bigmod(b,p/2,m); return (temp*t...
Mon Aug 16, 2004 3:09 am
Forum: Volume 106 (10600-10699)
Topic: 10689 - Yet another Number Sequence
Replies: 22
Views: 11642
not valid for all (a,b) pairs. there's nothing profound about the number 15000; this number changes as a,b, or m changes. i used this 'pisano period' method (but at the time i submitted didn't realize it was even called that until i see this thread now). just figure that the last m digits of fib(n-1...
Mon Aug 16, 2004 2:46 am
Forum: Algorithms
Topic: Maximal suffix
Replies: 2
Views: 1308
build a suffix tree then start at the root and always go down to the lexicographically highest child until you hit a leaf. this will end you with the suffix you are looking for. One way to build a suffix tree is Ukkonen's Algorithm. This site explains how that works and even has a sample implementat...
Sat Aug 14, 2004 2:36 am
Forum: Algorithms
Topic: USACO Broken Necklace Problem
Replies: 8
Views: 4593
[c] beads1 = numberBeads(brokenBeads.substr(0, i)); beads2 = numberBeads(brokenBeads.substr(i + 1, beads.length())); [/c] This is wrong. You are not accounting for the fact that the necklace is not a straight line. The necklace is a circle. The first piece of the necklace is connected to the last pi...