Indian National Olympiad in Informatics
Online Programming Contest, 6-7 November 2004
IARCS home > OLYMPIAD
Advanced Division
Solution to Problem 1: Draw Fixing
Suppose the ratings of the players of the Siruseri team are
S_1,..., S_n and those of the Navalur team are N_1,...N_n. The
task is to come up with a pairing (1,i1), (2,i2) ... (n,in),
where {i1,i2,...,in} is a permutation of {1,2,..,N}, such that
the size of the set { j | S_j > N_ij } is maximized.
Trying all possible pairing is ruled as there are N! possible
pairings.
So how do we proceed? Well, one simple idea that is appealing is
the following: if a Siruseri player P can beat a number of
players on the Navalur side we should pair him up with the best
player on the Navalur side that he can beat (so that other
Siruseri players don't have to play him and might have a better
chance at beating other Navalur players.) So take the highest
rated Siruseri player and pair him against the best Navalur
player who has a lower rating and pair him with him. Now consider
the next Siruseri player and from among the Navalur players left
do the same thing and so on. It turns out that this idea works.
Let us see why.
(By the way, this how you solve problems. First, think of
something to try. Then try to argue why it would work. You will
either succeed in solving the problem or find out why your idea
does not work and that will either tell you how to modify your
idea or suggest an altogether different idea to consider and so
on.)
We make the following fundamental observation:
----------------------------------------------
Consider any pairing. Suppose it uses pairs (j,ij) and (k,ik)
such that
1) S_j < S_k and N_ik < N_ij
2) Both pairs are wins for Siruseri
Then, we can delete (j,ij), (k,ik) and instead add (j,ik) and (k,ij)
and get a pairing that still has two wins for the Siruseri team.
S_j N_ik S_j --- N_ik
\ /
\ / is changed to
^ / \ ^ ^ ^
/ \
S_k N_ij S_k --- N_ij
Since S_j > N_ij and S_k > S_j, it follows that S_k > N_ij. Since
S_j > N_ij and N_ij > N_ik we have S_j > N_ik. Thus, we still
have two wins in the new pairing.
Thus, we have a optimal pairing in which none of the winning
pairs for Sirusri "cross" (i.e. satisfy condition 1 of the
Observation above).
Thus, if S_1 > S_2 > ... S_n and N_1 > N_2 > ... N_n then, if we
fix a optimal pairing and draw only the pairs that are winning
for Siruseri, it will look like (i.e. without any crossing).
S1 S2 ... Sj ... Sk ... Sl ... Sn
/ \ /
| \ /
| \ |
/ \ |
N1 N2 ... Nij ... Nik ... Nil ... Nn
In what follows, we assume that S_1 > S_2 ...S_n and N_1 > N_2
... N_n. We now show that we can slide each of these pairings as
much to the left as possible.
Sliding on the Siruseri side:
-----------------------------
First we claim that if there are k wins in a some pairing we can
find a pairing in which S_1, S_2, ... S_k win their pairings.
Thus, we may slide the winning pairs all the way to the left on
the Siruseri side.
Proof:
Suppose the given pairing already gives winning matchings for
S_1,S_2 ... S_{i-1} with i ≤ k and that S_i < N_ii. Since
there are k wins there is a S_j, j > i such that S_j >
N_ij. We drop the pairs (S_i,N_ii), (S_j, N_ij) and instead add
the pairs (S_i,N_ij) and (S_j, N_ii). Since S_i > S_j and S_j
> N_ij, it follows S_i > N_ij. Thus repeating this process
we can ensure that S1, S2, ... Sk all win their pairings.
Sliding on the Navalur Side:
----------------------------
Given any pairing with S_j > N_ij and S_{j-1} ≤ N_i{j-1} we
can modify the pairing by replacing these two pairs by pairs
(S_j, N_i{j-1}) and (S_{j-1},N_ij) and get a new pairing with at
least as many wins for Siruseri as the original pairing.
In proof simply note that S{j-1} > Sj > Nij.
Thus, we can produce the optimal pairing by doing the following:
We begin with S_1. Starting with N_1 find the first N_j such that
S_1 > N_j. (If there is no such N_j, of course, Siruseri is
doomed to scoring 0.) Assign S_1 to N_j. Now consider S2 and
starting with N_j+1 find the first N_k such that S_2 >
N_k. Pair S_2 with N_k and so on.
We now describe the algorithm that implements this idea:
(This assumes that the ELO ratings of the Siruseri team is stored
in the array S and that of Navalur in the array N. We assume that
S[1] > S[2] ... S[n] and N[1] > N[2] > ... N[n]. )
count = 0 /* Variable that counts the number of wins for
Siruseri in a optimal pairing */
s-index=1 /* The index in the Sirseri array whose pairing
we are searching for */
n-index=1 /* The next index to be considered for pairing
with player s-index of Siruseri. */
while (n-index ≤ n ) {
if (S[s-index] < N[n-index]) n-index=nindex+1
else { /* the pair for s-index has been found */
count=count+1
n-index=n-index+1
s-index=s-index+1
}
}
The above algorithm only takes time proportional to n.
What if S and N are not in descending order? Well, sort S and N.
That will take time proportional to n log n (if you use a good
sorting algorithm) and thus the overall solution will take time
of the order of n log n.
The problem also requires you to print out the indices that are
paired. That is left to you as an exercise (note that if you
sort S and N you will lose track of which player had which ELO
rating. So you must do a little bit of book-keeping to solve this
problem.)
Copyright (c) IARCS 2003-2024; Last Updated: 15 Mar 2005