Search found 63 matches

Sun Feb 20, 2005 2:07 am
Forum: Volume 8 (800-899)
Topic: 868 - Numerical Maze
Replies: 21
Views: 14648
Hi there, just got it AC after several submissions. And yes, the last subsequence of the path must be complete, but I think the phrase
The path consists of subsequences obeying to the following rule: 1; 1,2; 1,2,3; 1,2,3,4; and so on.
doesn't state this clearly enough.

HTH,
Christian
Fri Feb 18, 2005 11:45 am
Forum: Volume 108 (10800-10899)
Topic: 10808 - Rational Resistors
Replies: 19
Views: 9796
I just saw that it is possible to do the calculation with a single (m+n)x(m+n) matrix, when using the RHS as you described it. I did it with a (m+n+2)x(m+n+1) matrix, adding two rows for a "voltage source" setting V(P)=0 and V(Q)=1, and a column for the current through the voltage source. The RHS is...
Thu Feb 17, 2005 2:35 am
Forum: Volume 108 (10800-10899)
Topic: 10808 - Rational Resistors
Replies: 19
Views: 9796
Yes, int64 may be enough for some algorithms, for others it may not. Luckily, my solution belongs to the ones for which int64 suffices. ;) But I don't understand how it is possible to perform Gauss only once, because the currents depend on the two queried nodes. That is, you have to modify the rows ...
Fri Feb 11, 2005 4:52 pm
Forum: Volume 108 (10800-10899)
Topic: 10810 - Ultra-QuickSort
Replies: 36
Views: 20746
Sorry, I didn't read the problem description again. Here is a correct case where your program fails:

Code: Select all

``````4
1
3
4
2``````
Your output is 1, although 2 swaps are necessary (2<->4, then 3<->2)
Fri Feb 11, 2005 12:56 pm
Forum: Volume 4 (400-499)
Topic: 417 - Word Index
Replies: 15
Views: 1803
I found two things: Your "words" array needs to be of size 83682, because you write to words[83681] in makeindex. Don't compare the result of strcmp to 1 and -1, but check if it is greater or less than zero. Due to that mistake, your program gave negative values on my (and probably the judge's) mach...
Fri Feb 11, 2005 11:01 am
Forum: Volume 4 (400-499)
Topic: 417 - Word Index
Replies: 15
Views: 1803
My AC program's output:

Code: Select all

``````51
52
75
76
77
98
349
350
351
352
353
375
376
399
648
650
651
652
653
927
928
929
2949
2950
2951
2952
2953
5251
5252
7275
17886
17900
17901
17902
30551
30552
7452
83680
83681``````
HTH,
Christian
Fri Feb 11, 2005 10:48 am
Forum: Volume 108 (10800-10899)
Topic: 10810 - Ultra-QuickSort
Replies: 36
Views: 20746
It seems you only add to the result if you arrived at the end of the right half during merging. Try the case

Code: Select all

``````4
1
2
3
1``````

Hint: Each time a number from R is inserted, you need to count the numbers from L that are greater than this number.
Fri Feb 11, 2005 12:24 am
Forum: Volume 3 (300-399)
Topic: 359 - Sex Assignments And Breeding Experiments
Replies: 12
Views: 4906
The original directed "parent graph" does not need to be bipartite (or bicolorable, however you call it), but the undirected "mate graph" must be, since no two mates may be of the same sex.

The mate graph for Larry's example contains only the edges AB and AC, and it is bipartite.
Wed Feb 09, 2005 4:19 pm
Forum: Volume 108 (10800-10899)
Topic: 10809 - Great Circle
Replies: 17
Views: 6101
I think it depends on the definition of "arc": If a point is a degenerate arc, then the shortest arc between two identical points clearly is a point-shaped arc. As a result, the most northerly latitude reached on this arc is the latitude of the point, which should be the answer. On the other hand, i...
Wed Feb 09, 2005 1:20 pm
Forum: Volume 108 (10800-10899)
Topic: 10810 - Ultra-QuickSort
Replies: 36
Views: 20746
I implemented the same algorithm, but changed to bubblesort for small n. Merging is done with pointers, which speeds up the process a bit. And I must admit that I wrote a small function for parsing an integer from a string, which is a lot faster than scanf.
Wed Feb 09, 2005 12:10 am
Forum: Volume 108 (10800-10899)
Topic: 10809 - Great Circle
Replies: 17
Views: 6101
Another interesting case:

Code: Select all

``90,0S 0,0W 90,0N 0,0W``
Sat Feb 05, 2005 10:41 pm
Forum: Volume 4 (400-499)
Topic: 473 - Raucous Rockers
Replies: 16
Views: 7498
Thanks, I just got AC with an O(n*m*t) DP algorithm.
Fri Feb 04, 2005 11:20 pm
Forum: Volume 2 (200-299)
Topic: 247 - Calling Circles
Replies: 21
Views: 8524
I just found my (really stupid) mistake: I put the case number variable in the wrong line, making it a char. Both my Warshall and Tarjan implementations got AC when changing it to int.

Fri Feb 04, 2005 5:31 pm
Forum: Volume 4 (400-499)
Topic: 473 - Raucous Rockers
Replies: 16
Views: 7498

473 - Raucous Rockers

Hello, I tried to solve problem 473 by a greedy algorithm: 1. S := sequence of song lengths (as given in input) 2. determine number of disks needed for the songs in S 3. if disks <= m return |S| 4. otherwise remove longest song from S and go to 2. I assumed that the song order given in the input mus...
Thu Feb 03, 2005 7:04 pm
Forum: Algorithms
Topic: Dominating Sets in grraphs
Replies: 2
Views: 1350
Yes, MDS is known to be NP-complete. If you find a polynomial time algorithm, please let me know. :wink: Some things to speed up testing quite a bit: 1. Split the graph into its connected components and determine the MDS for these. The graph's MDS is the union of the component's MDS. 2. When using b...