11293 - Tournament

[sclo]

How do you prove the greedy is always correct?

Left as an exercise
Here's one of the step of the proof:
Suppose A<B<C<D, we have matching between A-C and B-D, then we can always get better matching if we have A-B and C-D instead.
It follows that the matchings do not cross each other

Now, suppose we have matching between A-D and B-C, then A-B and C-D is a better matching. (follows from (x+y)^2>=x^2+y^2)
It follows that the matching do not overlap each other

If the matchings don't cross or overlap each other, then we can make then as close as possible, and the closest possible is between consecutive elements.

Now, you have to prove that the greedy choice is correct i.e. how to iteratively construct the solution.

[goodwill]

Thanks. I got it.

[atariman486]

Has anyone got an interesting set of test data I can run through my program? It works for the ones I come up with, but I keep getting WA.

Here's one set I tried:
6
a 3
b 4
c 15
d 20
e 21
f 24
14
a 3
b 6
c 8
d 9
e 15
f 16
g 17
h 70
i 77
j 83
k 88
l 100
m 107
n 120
0

Output:
c
f

g
n

Thanks!
-Chris-

[Jan]

Your cases are correct. Thy the case below:

Input:

Code: Select all

9
a 3
b 8
c 15
d 20
e 21
f 24
g 24
h 30
i 31
0

Output:

Code: Select all

a
b
c
d
e
h
i

Hope it helps.

[atariman486]

Thanks for the test case. I got the correct output. I don't know why I keep getting WA.