## Search found 90 matches

Fri Aug 13, 2004 4:58 pm
Forum: Volume 106 (10600-10699)
Topic: 10692 - Huge Mods
Replies: 15
Views: 11435
I understand how to solve this problem by looking for the order of the group generated by a^i mod m for each level up in the exponents. However, is there some number theory result that tells you the order of the group a (mod m), a^2 (mod m), ..., given a and m by doing less work? I see people have u...
Thu Aug 12, 2004 5:10 pm
Forum: Volume 106 (10600-10699)
Topic: 10685 - Nature
Replies: 41
Views: 18122
Oh sorry, I am dumb. I see now why your binary search works since you do not break when lo>=hi ^^;

i still don't see why your make_set works tho but maybe i will realize it latter : (
Thu Aug 12, 2004 5:03 pm
Forum: Algorithms
Topic: Diameter of a Graph
Replies: 6
Views: 1753
ah thank you, i understand now what you are saying. and about the d(N) and d2(N) i was saying, it is the same idea sort of. although i still did have a bug (what i was saying was only consider the d(N) and d2(N) for an arbitrary N out of each connected component when really i should have done it for...
Thu Aug 12, 2004 4:41 pm
Forum: Volume 106 (10600-10699)
Topic: 10689 - Yet another Number Sequence
Replies: 22
Views: 11653
Hint: Coefficients -- F(0) = a
-------------
F(1) = 0a + b
F(2) = a+b
F(3) = a+2b
F(4) = 2a+3b
F(5) = 3a+5b

Fib(0,1,2...) = 0, 1, 1, 2, 3, 5
Thu Aug 12, 2004 11:41 am
Forum: Algorithms
Topic: USACO Broken Necklace Problem
Replies: 8
Views: 4598
you forgot that the necklace loops around on itself. if you split it right before the first b, these are the two pieces: going backwards from the b: wrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrrwrwrwrwrwrwrwrwrwrwrwrw -> break at b (size 72) going forwards: bw -> break at r (size 2) so correct o...
Thu Aug 12, 2004 11:29 am
Forum: Volume 106 (10600-10699)
Topic: 10685 - Nature
Replies: 41
Views: 18122
acctually I have used a different type of binary search( as i m not so good with it ) my last element is list[c-1], there is nothing in list[c] as i m indexing from list[0] not from list[1]. I know that your array is 0-indexed. high should still be set to c and not c-1 (i know that there is nothing...
Thu Aug 12, 2004 5:06 am
Forum: Volume 106 (10600-10699)
Topic: 10690 - Expression Again
Replies: 23
Views: 9723
[EDIT]
I think what I said before works but am not sure...let me code it
and submit and check to make sure. ^_^
[/EDIT]
Thu Aug 12, 2004 3:30 am
Forum: Volume 106 (10600-10699)
Topic: 10685 - Nature
Replies: 41
Views: 18122
you do this: [c] void makeset(int x,int y) { if(!set[y]) set[y]=x; else makeset(x,set[y]); } [/c] but then do this [c] j=bin_s(0,c-1,temp1); k=bin_s(0,c-1,temp2); j++; k++; if(find1(j)!=find1(k)) { makeset(j,k); } [/c] what if j==0? then the next time make_set gets called with k, it will think k has...
Thu Aug 12, 2004 3:06 am
Forum: Algorithms
Topic: Diameter of a Graph
Replies: 6
Views: 1753
ah yes, you are right. : ) thank you. [EDIT] Although maybe I can fix this by letting d(N) be depth of deepest subtree and d2(N) be the depth of the2nd deepest subtree? Or maybe there is also a bug in that, but I do not see one yet ^^; And then the diameter of that connected component (I think) shou...
Wed Aug 11, 2004 5:05 pm
Forum: Algorithms
Topic: Diameter of a Graph
Replies: 6
Views: 1753
i reread the problem statement after reading your post.. i somehow missed this the first time: "Being frugal people, they have ensured that no road has been built between two squares if it had been possible to travel between the two squares without the road." :cry: Thank you for your reply, I spent ...
Tue Aug 10, 2004 4:25 am
Forum: Algorithms
Topic: Diameter of a Graph
Replies: 6
Views: 1753

### Diameter of a Graph

Is there a faster way to find the diameter of a graph besides running the O(n^3) Floyd-Warshall algorithm? [EDIT] and also one that takes less space :D Oh, and the edges that do exist have weight 1. I was thinking of DFS'ng each connected component, but I couldn't figure out how to modify DFS to kee...
Tue Aug 10, 2004 2:57 am
Forum: Volume 1 (100-199)
Topic: 102 - Ecological Bin Packing
Replies: 485
Views: 50677
I suspect this line [c] long bgc = bin2[0] + bin3[0] + bin1[2] + bin3[2] + bin1[1] + bin2[1]; [/c] should be changed to this: [c] long bgc = bin1[1] + bin1[2] + bin2[0] + bin2[2] + bin3[0] + bin3[1]; [/c] [EDIT] For problems like these, it is very easy to just screw up one index somewhere and have t...
Tue Aug 10, 2004 2:46 am
Forum: Volume 1 (100-199)
Topic: 101 - The Blocks Problem
Replies: 635
Views: 40431
If you run your code on the example they give you, you'll see that it thinks any command you enter is the quit command. I changed this piece of your code to make it at least output the right answer on the example. [cpp] switch(act[0]) { case 'm': cmd.action=1; break; case 'p': cmd.action=2; break; c...
Mon Aug 09, 2004 4:50 pm
Forum: Volume 106 (10600-10699)
Topic: 10685 - Nature
Replies: 41
Views: 18122
I thought I'd have some fun with hashing..I've tested it on my computer with no problems, but judge says Runtime error (SIGSEV) ?? [c] #include <stdio.h> #include <stdlib.h> #define MOD_PRIME 99991 typedef struct node node; struct node { node *cdr; node *end; int ind; char name[31]; }; int roots[500...
Mon Aug 09, 2004 2:00 pm
Forum: Volume 106 (10600-10699)
Topic: 10608 - Friends
Replies: 75
Views: 26986
There are two good ways I know of doing it. Both involve the same algorithm, but different data structures to represent sets. First data structure is linked list, but modified so that each element also has a pointer to the "root" (which will be the representative for the set). So whenever you start ...