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-2020; Last Updated: 15 Mar 2005