## Search found 63 matches

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

### 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...
Sat Jan 29, 2005 6:40 pm
Forum: Volume 107 (10700-10799)
Topic: 10745 - Dominant Strings
Replies: 38
Views: 17245

### 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...
Tue Jan 18, 2005 9:22 am
Forum: Volume 108 (10800-10899)
Topic: 10808 - Rational Resistors
Replies: 19
Views: 9796
I wrote a class and some operators which automatically simplified the fraction after each operation - and I used long long for numerator and denominator.
Mon Jan 17, 2005 7:50 pm
Forum: Volume 108 (10800-10899)
Topic: 10808 - Rational Resistors
Replies: 19
Views: 9796
I just got AC after a few (7) tries using that Node Voltage Method!
Mon Jan 17, 2005 11:31 am
Forum: Volume 108 (10800-10899)
Topic: 10808 - Rational Resistors
Replies: 19
Views: 9796
Is there a way other than solving a linear system of equations?
Sun Jan 16, 2005 2:22 am
Forum: Volume 107 (10700-10799)
Topic: 10796 - Right Hand Rule
Replies: 7
Views: 4780
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.
Thu Jan 13, 2005 6:25 pm
Forum: Volume 107 (10700-10799)
Topic: 10797 - Peaceful Sharing
Replies: 18
Views: 12895
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.
Thu Jan 13, 2005 4:08 pm
Forum: Volume 107 (10700-10799)
Topic: 10796 - Right Hand Rule
Replies: 7
Views: 4780
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 ...
Sat Jan 01, 2005 2:14 pm
Forum: Volume 2 (200-299)
Topic: 247 - Calling Circles
Replies: 21
Views: 8524
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...
Thu Dec 30, 2004 9:08 pm
Forum: Volume 2 (200-299)
Topic: 247 - Calling Circles
Replies: 21
Views: 8524

### 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?
Mon Dec 20, 2004 4:12 pm
Forum: Volume 107 (10700-10799)
Topic: 10744 - The Optimal Super-Highway
Replies: 29
Views: 14788
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...
Tue Nov 19, 2002 1:06 am
Forum: Volume 104 (10400-10499)
Topic: 10408 - Farey sequences
Replies: 9
Views: 6339
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...
Mon Nov 11, 2002 7:32 pm
Forum: Volume 104 (10400-10499)
Topic: 10410 - Tree Reconstruction
Replies: 13
Views: 9147
Thank You! There seemed to be a bug in my subtree finding algorithm - I'd better call it "hack". 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.
Mon Nov 11, 2002 1:24 pm
Forum: Volume 104 (10400-10499)
Topic: 10410 - Tree Reconstruction
Replies: 13
Views: 9147

### 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... ...
Wed Nov 06, 2002 1:16 am
Forum: Volume 103 (10300-10399)
Topic: 10398 - The Golden Pentagon
Replies: 17
Views: 3858
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.