doesn't state this clearly enough.The path consists of subsequences obeying to the following rule: 1; 1,2; 1,2,3; 1,2,3,4; and so on.

HTH,

Christian

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

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

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

- 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:
Your output is 1, although 2 swaps are necessary (2<->4, then 3<->2)

Code: Select all

```
4
1
3
4
2
```

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

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

HTH,

Christian

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

Christian

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

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:
**4849**

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

- Wed Feb 09, 2005 1:20 pm
- Forum: Volume 108 (10800-10899)
- Topic: 10810 - Ultra-QuickSort
- Replies:
**36** - Views:
**20485**

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

- Sat Feb 05, 2005 10:41 pm
- Forum: Volume 4 (400-499)
- Topic: 473 - Raucous Rockers
- Replies:
**16** - Views:
**7409**

- Fri Feb 04, 2005 11:20 pm
- Forum: Volume 2 (200-299)
- Topic: 247 - Calling Circles
- Replies:
**21** - Views:
**8443**

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

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