Search found 63 matches

by Christian Schuster
Sun Feb 20, 2005 2:07 am
Forum: Volume 8 (800-899)
Topic: 868 - Numerical Maze
Replies: 21
Views: 14468

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
by Christian Schuster
Fri Feb 18, 2005 11:45 am
Forum: Volume 108 (10800-10899)
Topic: 10808 - Rational Resistors
Replies: 19
Views: 9720

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...
by Christian Schuster
Thu Feb 17, 2005 2:35 am
Forum: Volume 108 (10800-10899)
Topic: 10808 - Rational Resistors
Replies: 19
Views: 9720

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 ...
by Christian Schuster
Fri Feb 11, 2005 4:52 pm
Forum: Volume 108 (10800-10899)
Topic: 10810 - Ultra-QuickSort
Replies: 36
Views: 20485

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)
by Christian Schuster
Fri Feb 11, 2005 12:56 pm
Forum: Volume 4 (400-499)
Topic: 417 - Word Index
Replies: 15
Views: 1706

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...
by Christian Schuster
Fri Feb 11, 2005 11:01 am
Forum: Volume 4 (400-499)
Topic: 417 - Word Index
Replies: 15
Views: 1706

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
by Christian Schuster
Fri Feb 11, 2005 10:48 am
Forum: Volume 108 (10800-10899)
Topic: 10810 - Ultra-QuickSort
Replies: 36
Views: 20485

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
The answer should be 2, but your program prints 1.

Hint: Each time a number from R is inserted, you need to count the numbers from L that are greater than this number.
by Christian Schuster
Fri Feb 11, 2005 12:24 am
Forum: Volume 3 (300-399)
Topic: 359 - Sex Assignments And Breeding Experiments
Replies: 12
Views: 4849

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.
by Christian Schuster
Wed Feb 09, 2005 4:19 pm
Forum: Volume 108 (10800-10899)
Topic: 10809 - Great Circle
Replies: 17
Views: 6036

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...
by Christian Schuster
Wed Feb 09, 2005 1:20 pm
Forum: Volume 108 (10800-10899)
Topic: 10810 - Ultra-QuickSort
Replies: 36
Views: 20485

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.
by Christian Schuster
Wed Feb 09, 2005 12:10 am
Forum: Volume 108 (10800-10899)
Topic: 10809 - Great Circle
Replies: 17
Views: 6036

Another interesting case:

Code: Select all

90,0S 0,0W 90,0N 0,0W
by Christian Schuster
Sat Feb 05, 2005 10:41 pm
Forum: Volume 4 (400-499)
Topic: 473 - Raucous Rockers
Replies: 16
Views: 7409

Thanks, I just got AC with an O(n*m*t) DP algorithm.
by Christian Schuster
Fri Feb 04, 2005 11:20 pm
Forum: Volume 2 (200-299)
Topic: 247 - Calling Circles
Replies: 21
Views: 8443

I just found my (really stupid) mistake: I put the case number variable in the wrong line, making it a char. :oops: Both my Warshall and Tarjan implementations got AC when changing it to int. :)

Thanks for your replies!
by Christian Schuster
Fri Feb 04, 2005 5:31 pm
Forum: Volume 4 (400-499)
Topic: 473 - Raucous Rockers
Replies: 16
Views: 7409

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...
by Christian Schuster
Thu Feb 03, 2005 7:04 pm
Forum: Algorithms
Topic: Dominating Sets in grraphs
Replies: 2
Views: 1315

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

Go to advanced search