Kattis Challenge: #include <scoring>

April 18th, 2019

SPOILER ALERT: This post contains an answer for an online programming challenge (https://open.kattis.com/problems/includescoring). Try it yourself first :)

So this one is pretty meta: We’re asked to write a library that calculates the scores for entrants into a programming contest, because if the jury of the contest could do that themselves, they’d have better jobs than judging a programming contest. The problem is straightforward enough: For each contestant, calculate his (or her) score using a table and provided ranking criteria.

We have two big challenges here:

• Find the rank of each contestant
• Write a tie-breaker algorithm

Alright, first up, let’s define a class to hold our lucky contestant:

class Contestant
{
    public int id;

    public int nSolved;
    public int timePenalty;
    public int submittedTime;
    public int bonus;
    public int score;

    public Contestant(int id, int nSolved, int timePenalty, int submittedTime, int bonus)
    {
        this.id = id;
        this.nSolved = nSolved;
        this.timePenalty = timePenalty;
        this.submittedTime = submittedTime;
        this.bonus = bonus;
        this.score = 0;
    }

    public void SetScore(int score)
    {
        this.score = score + bonus;
    }

}

Pretty basic stuff here - we’re just holding the data given to us as input. One addition is the id column: Remember that we have to display the results in the same order the contestants were entered into the program, so it’s helpful to keep track of this with a numerical id. Also, we make sure to apply the bonus after the final score is set.

Now, how to calculate their score? Well, ranking sounds a lot like sorting, so let’s sort them from best to worst (or in descending order as the cool kids like to call it). The “ACM Scoring” algorithm works a lot like alphabetizing a list of strings: If the first letter matches, compare the second, and so on… Let’s do that for our contestants:

class ScoreComparer : IComparer<Contestant>
{
    public int Compare(Contestant lhs, Contestant rhs)
    {
        if (lhs.nSolved != rhs.nSolved)
        {
            return lhs.nSolved.CompareTo(rhs.nSolved) * -1;
        }
        else
        {
            if (lhs.timePenalty != rhs.timePenalty)
            {
                return lhs.timePenalty.CompareTo(rhs.timePenalty);
            }
            else
            {
                return lhs.submittedTime.CompareTo(rhs.submittedTime);
            }
        }
    }
}

Again, pretty basic stuff. The only pitfall to watch out for here is that solving more problems than your friend is good, but having a higher time penalty or submitting later is bad. Therefore, we inverse the result of the nSolved comparison. We could have also just swapped lhs and rhs, but that seemed less explicit.

Now we just build a list of contestants and: contestantList.Sort(new ScoreComparer());

Feels good man.

Ok, so now for assigning scores to our ranked contestants. The important thing here is to watch out for ties: The scores for those ranks have to be averaged and distributed to everyone tied for that position. The good news is our contestants are already sorted! We can use a nested loop to sum the scores of adjacent contestants who compare equal, and then give each one that sum divided by the number of tied contestants:

while (idx < contestantList.Count)
{
    if (idx >= rankPoints.Length)
    {
        contestantList[idx++].SetScore(0);
        continue;
    }

    int j = idx;
    while (j < contestantList.Count && comparer.Compare(contestantList[idx], contestantList[j]) == 0)
    {
        j++;
    }

    int avg = AverageScore(rankPoints, idx, j - idx);
    for (int i = idx; i < j; i++)
    {
        contestantList[i].SetScore(avg);
    }

    idx = j;
}

So this funky bit of code initializes variable j to the current index in the contestant list, then increments j as long the contestant at index j is equal in rank to our initial index. This way [index, j[ gives us a nice interval of tied contestants, that we can feed into the AverageScore() function to calculate their score:

public static int AverageScore(int[] pointsTable, int startIdx, int n)
{
    double avg = 0;

    for (int i = startIdx; i < startIdx + n; i++)
    {
        avg += (i >= pointsTable.Length) ? 0 : pointsTable[i];
    }

    avg = avg / n;
    return (int)Math.Ceiling(avg);
}

Believe it or not, developing this part of the algorithm involved a lot of banging my head against the wall (the webpage?), because there’s a peculiar case to consider: What if the number of tied contestants goes beyond the table of 30 scores?

The answer involves reading between the lines a bit: Contestants with a worse rank than 30 get 0 points, so for each tied contestant that goes beyond rank 30, you add 0 to the sum for your average. This has an effect of diluting the score for everyone tied for that rank, which makes sense (I guess). It seems simple now, but it took me quite a while to figure that out! You can see this in action in the (i >= pointsTable.Length) ? 0 : pointsTable[i]; line.

Of course, we have to make sure to pick up where j left off, so we set idx = j and continue. What’s nifty is that this algorithm treats tied and untied contestants the same way: An untied contestant will just be the score divided by 1.

Alright, so we’ve got our contestants and our scores. Now we just need to print the output. Uh-oh, they have to be output in the order they appeared, and we just sorted them. Good thing we have that id field! This calls for…another comparator!

class IdComparer : IComparer<Contestant>
{
    public int Compare(Contestant lhs, Contestant rhs)
    {
        return lhs.id.CompareTo(rhs.id);
    }
}

and last but not least:

contestantList.Sort(new IdComparer());

foreach (var contestant in contestantList)
{
    Console.WriteLine(contestant.score);
}

god I love C#.

And there you go, we’ve solved the problem of how to kill a couple hours without reliable WiFi automatically judge programming contests.