Search found 63 matches

by Christian Schuster
Sun Jan 30, 2005 8:52 pm
Forum: Volume 107 (10700-10799)
Topic: 10745 - Dominant Strings
Replies: 38
Views: 16975

Re: What's wrong with my algorithm

Do you do the inner check (that with mat[i][k]) for all k? i dominates j iff mat[i][k] >= mat[j][k] for all k from 0 to 25. Theoretically, there must also be at least one k with mat[i][k] > mat[j][k], but since all strings are different, there is no need to check this. Remember to skip string i in t...
by Christian Schuster
Sat Jan 29, 2005 6:40 pm
Forum: Volume 107 (10700-10799)
Topic: 10745 - Dominant Strings
Replies: 38
Views: 16975

Re: another way

I just give each char with a prim,eg: a(2) b(3) c(5)... so you can change each string to a long long int ,and use % to check! This is not (completely) correct, since the 26th prime is 101, and "zzzzzzzzzz" would be 101^10, which is a bit too large for 63 or even 64 bits. However, I split the charac...
by Christian Schuster
Tue Jan 18, 2005 9:22 am
Forum: Volume 108 (10800-10899)
Topic: 10808 - Rational Resistors
Replies: 19
Views: 9723

I wrote a class and some operators which automatically simplified the fraction after each operation - and I used long long for numerator and denominator.
by Christian Schuster
Mon Jan 17, 2005 7:50 pm
Forum: Volume 108 (10800-10899)
Topic: 10808 - Rational Resistors
Replies: 19
Views: 9723

I just got AC after a few (7) tries using that Node Voltage Method! :D
by Christian Schuster
Mon Jan 17, 2005 11:31 am
Forum: Volume 108 (10800-10899)
Topic: 10808 - Rational Resistors
Replies: 19
Views: 9723

Is there a way other than solving a linear system of equations?
by Christian Schuster
Sun Jan 16, 2005 2:22 am
Forum: Volume 107 (10700-10799)
Topic: 10796 - Right Hand Rule
Replies: 7
Views: 4733

Thank you. I missed a rare case in my automaton for the agent, making it run into an adjacent wall. Just fixed it and got AC. :wink:
by Christian Schuster
Thu Jan 13, 2005 6:25 pm
Forum: Volume 107 (10700-10799)
Topic: 10797 - Peaceful Sharing
Replies: 18
Views: 12810

My solution has about 100 lines and uses a tiny bit of STL. I use an iterative approach, improving the selected mines in an alternating manner... And it seems to be quite fast. :D
by Christian Schuster
Thu Jan 13, 2005 4:08 pm
Forum: Volume 107 (10700-10799)
Topic: 10796 - Right Hand Rule
Replies: 7
Views: 4733

I just tried to solve this one with BFS, but got WA many times. I skipped the "states" where ME and K are in the same field or just exchanged positions. My program gives the correct answers for all inputs above, but here is another tricky case: 1 2 3 0 0 0 2 0 1 R ... ### Should the answer be -1 or ...
by Christian Schuster
Sat Jan 01, 2005 2:14 pm
Forum: Volume 2 (200-299)
Topic: 247 - Calling Circles
Replies: 21
Views: 8443

I'll describe some theoretical thoughts: Let R be the relation given by the phone calls. I use Warshall's algorithm to find its transitive closure R'. Let S be the relation with xSy iff (xR'y and yR'x). S is an equivalence relation (reflexive, symmetric and transitive) and the equivalence classes ar...
by Christian Schuster
Thu Dec 30, 2004 9:08 pm
Forum: Volume 2 (200-299)
Topic: 247 - Calling Circles
Replies: 21
Views: 8443

247 - Calling Circles

If I understood the problem statement correctly, a calling circle is a strongly connected component of the call graph. I tried to determine these, but got WA with Tarjan's as well as with Warshall's algorithm. Is there anything I missed?
by Christian Schuster
Mon Dec 20, 2004 4:12 pm
Forum: Volume 107 (10700-10799)
Topic: 10744 - The Optimal Super-Highway
Replies: 29
Views: 14624

It indeed is possible to determine the k-th smallest value of a set S in O(|S|) time without using counting sort: select(S, k) { if |S| <= LIMIT { sort S return k-th element of S } split S into groups of 5 (possibly creating one group with less than 5) B = medians of these groups (each in constant t...
by Christian Schuster
Tue Nov 19, 2002 1:06 am
Forum: Volume 104 (10400-10499)
Topic: 10408 - Farey sequences
Replies: 9
Views: 6293

I used something like Larry, but I didn't check the gcd (too slow), I only did if ((i|j)&1) store(i,j) this excludes pairs where both numbers are divisible by two. Afterwards I sorted the result with qsort and threw the duplicates away. The linear search remained the same. I reviewed my code and fou...
by Christian Schuster
Mon Nov 11, 2002 7:32 pm
Forum: Volume 104 (10400-10499)
Topic: 10410 - Tree Reconstruction
Replies: 13
Views: 9079

Thank You! There seemed to be a bug in my subtree finding algorithm - I'd better call it "hack". :roll: I threw it away, wrote something totally new and got AC. Thanks for the test cases, my original program gave wrong answer on the first.
by Christian Schuster
Mon Nov 11, 2002 1:24 pm
Forum: Volume 104 (10400-10499)
Topic: 10410 - Tree Reconstruction
Replies: 13
Views: 9079

10410 - Tree Reconstruction

Hello! I tried to solve that problem, and got WA with 0.00x seconds. So I thought there might be multiple sets of input. There _ARE_ numbers after the first set of data. I tried and tried and ... still got WA. I try to build the tree recursively, making some weird comparisons between BFS and DFS... ...
by Christian Schuster
Wed Nov 06, 2002 1:16 am
Forum: Volume 103 (10300-10399)
Topic: 10398 - The Golden Pentagon
Replies: 17
Views: 3776

I just tried my luck on this one, too. After getting WA multiple times I finally found out a rounding error in the 15th fractional digit of my value for r (should be 6,not 5). The main problem is (as always in floating point problems) precision.

Go to advanced search