Description

Although many people know of the BCS and that its rankings determine which teams get to compete in college football's most prestigious bowl games, few understand exactly how it produces its mysterious rankings. The BCS is a conglomeration of computer polls and human polls, each given certain weights. While much has been discussed of the human polls, for this problem we will consider the computer rankings.

In particular, we will examine the ranking algorithm known as the Colley Matrix method. Unlike most of the computer systems that produce rankings, this algorithm is publicly known and relatively simple. The author, Wesley Colley, published an in-depth paper called Colley's Bias Free College Football Ranking Method: The Colley Matrix Explained to explain the algorithm and mathematical underpinnings of this method [1].

The ratings for each team is defined by the following equation:

r = (1 + Nwins) / (2 + Ntotal)                              (Eqn. 1)

Where Nwins is the number of wins a team has, and Ntotal is the number of games played. Basically, this only takes into account the number of wins for each team. However, since beating up on lowly teams such as Boston College is not the same as beating top flight competition such as Florida, the Colley Method as an additional strength of schedule component [2].

Instead of just making Nwins just the number of wins a team has, the Colley Method uses the following equation to produce an adjusted Nwins value:

Nwins_adjusted = (Nwins - Nlosses) / 2 + Sum(Ropponents)    (Eqn. 2)

Where Sum(Ropponents) is the sum of the ratings of all of the team's opponents. As can been seen, this latter component is where the strength of schedule comes in, since we now account for the ratings of the other teams.

The final rating then, uses Nwins_adjusted from equation 2 in place of Nwins in equation 1:

r = (1 + Nwins_adjusted) / (2 + Ntotal)                     (Eqn. 3)

As you may notice, however, in order to compute Nwins_adjusted we must already know the ratings of the opposing teams, however, this depends on computing Nwins_adjusted for those teams, and so on. To get around this inter-dependency, the Colley Method employs matrices to solve a system of linear equations. Since this is out of the scope of our class, we will focus instead on an iterative approach.

In this iterative solution, you will use equation 1 to compute the initial ratings. Once this is done, you will use equation 2 and 3 to compute the adjusted ratings. If you repeat this computation you will notice the ratings oscillate until they converge at a final value. For this problem, perform 100 iterations.

Your mission for this problem then, is to compute the Colley ratings for a set of teams, and output the teams in order of highest Colley ranking to loweset.

Input

The first line of the input is the number of teams, followed by the team names. After this are the results of the head to head matchups in the following form: <team a> <score a> <team b> <score b>. Given this information, you are to compute the Colley ratings and output the teams in order by rank.

Sample input:

5
ND
USC
UM
MSU
UW
UW 16 USC 13
UW 20 MSU 21
ND 30 UW 24
UM 28 USC 31
UM 38 ND 34
ND 35 USC 21
USC 28 MSU 24

Output

The output should be <rank>. <team name>\t<team rating>.

Sample output:

1. ND       0.5870
2. UM       0.5217
3. USC      0.5000
4. MSU      0.4783
5. UW       0.4130

[1]	Colley argues that his method is bias free because it does not consider anything intangible such as conference prestige, tradition, history, is reproducible, and uses only a minimal amount of assumptions.

[2]	Note that running up the score will do you no good, since the Colley method does not factor in the point totals. Moreover, Colley does not include FCS (1-AA) opponents in his computations, so beating up on Youngstown State neither helps or hurts you in this ranking.

Approach

Do as the problem states: read in the teams, compute the rankings based on the Colley equations and then sort the teams based on the rankings.

Input/Output

• Final Input: problem010.input
• Final Output: problem010.output

Source Code

• Peter Bui's source code: pbui.cc
• Noah Franske's source code: nfranske.c
• Steve Lagree's source code: slagree.cpp