## Search found 63 matches

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

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

- Tue Jan 18, 2005 9:22 am
- Forum: Volume 108 (10800-10899)
- Topic: 10808 - Rational Resistors
- Replies:
**19** - Views:
**9723**

- Mon Jan 17, 2005 7:50 pm
- Forum: Volume 108 (10800-10899)
- Topic: 10808 - Rational Resistors
- Replies:
**19** - Views:
**9723**

- Mon Jan 17, 2005 11:31 am
- Forum: Volume 108 (10800-10899)
- Topic: 10808 - Rational Resistors
- Replies:
**19** - Views:
**9723**

- Sun Jan 16, 2005 2:22 am
- Forum: Volume 107 (10700-10799)
- Topic: 10796 - Right Hand Rule
- Replies:
**7** - Views:
**4733**

- Thu Jan 13, 2005 6:25 pm
- Forum: Volume 107 (10700-10799)
- Topic: 10797 - Peaceful Sharing
- Replies:
**18** - Views:
**12810**

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

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

- 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?

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

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

- Mon Nov 11, 2002 7:32 pm
- Forum: Volume 104 (10400-10499)
- Topic: 10410 - Tree Reconstruction
- Replies:
**13** - Views:
**9079**

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

- Wed Nov 06, 2002 1:16 am
- Forum: Volume 103 (10300-10399)
- Topic: 10398 - The Golden Pentagon
- Replies:
**17** - Views:
**3776**