Get Time
statistics_w  Match Editorial
2004 TopCoder Open
Qualification Problem Set 2

September 7-8, 2004


This set contained a rather straightforward, but long hard problem. Antimatter, known for his impressive speed, won this set handily, though perhaps because he got to warm up on set 1. He beat out two yellow coders oldbig, and Olexiy, who took second and third, each over 100 points behind.

The Problems

FileFilter discuss it
Used as: Division One - Level One:
Value 250
Submission Rate 204 / 216 (94.44%)
Success Rate 152 / 204 (74.51%)
High Score Im2Good for 248.02 points (2 mins 2 secs)
Average Score 204.98 (for 152 correct submissions)

As always, knowledge of the libraries in your language of choice makes solving problems much easier. In this problem, all you needed was the .endsWith() (or its equivalent) method, and you were pretty much set. Even if you didn't know about that one, it only takes a single loop to check of one string ends with another.

ResultsTable discuss it
Used as: Division One - Level Three:
Value 1000
Submission Rate 52 / 216 (24.07%)
Success Rate 28 / 52 (53.85%)
High Score antimatter for 657.55 points (18 mins 34 secs)
Average Score 427.99 (for 28 correct submissions)

In this problem, I think that its best to make some sort of a class or struct for each competitor. If you do this, you can write a method to compare two instances of the class or struct, and I think it makes your code more elegant, and hence less error prone. Also, if you have a class for competitors, you only need to write a comparator, and the built in sorting functions will do the rest.

Whatever approach you took, however, there weren't really any subtleties that you needed to think much about. When you parse the data, you should throw out all the irrelevant entries with lower COUNT's. Next, assuming you have a class for your competitors, you should write a comparator. The comparator should simply loop through the elements of sort, and make the necessary comparisons. There is a decent amount of logic here, as you need to consider a number of different cases, but none of them are that tricky. If you get the comparator right, you're home free, as you just need to call Arrays.sort() in Java or whatever the equivalent is in your favorite language, and then convert each competitor to a single string.

All told, there wasn't anything tricky, but it required a pretty good sized chunk of code, and ended up having the second fewest submissions of all the hards.

import java.util.*;
public class ResultsTable{
   int[] sort;
   String order;
   class Rec implements Comparable{
      int[] score;
      int[] cnt;
      String t;
      public Rec(int n){
         score = new int[n];
         cnt = new int[n];
      public String toString(){
         String ret = t;
         for(int i = 0; i<cnt.length ;i++){
            if(cnt[i] == -1)ret += " -";
            else ret += " "+score[i];
         return ret;
      public int compareTo(Object o){
         Rec r = (Rec)o;
         for(int i = 0; i<sort.length; i++){
            if(Math.abs(sort[i]) == 1){
               return t.compareTo(r.t)*sort[i];
            int idx = Math.abs(sort[i])-2;
            if(cnt[idx] == -1 && r.cnt[idx] == -1)continue;
            else if (cnt[idx] == -1) return sort[i];
            else if (r.cnt[idx] == -1) return -sort[i];
            else if(r.score[idx] != score[idx])return (r.score[idx] - score[idx])*(order.charAt(idx)=='H'?1:-1)*sort[i];
         return 0;
   public String[] generateTable(String[] results, int[] sort, String order){
      this.sort = sort;
      this.order = order;
      HashMap hm = new HashMap();
      for(int i = 0; i<results.length; i++){
         String[] sp = results[i].split(" ");
         int met = Integer.parseInt(sp[1])-1;
         int cnt = Integer.parseInt(sp[2]);
         int score = Integer.parseInt(sp[3]);
         Rec r = (Rec)hm.get(sp[0]);
         if(r == null)r = new Rec(order.length());
         if(cnt > r.cnt[met]){
            r.cnt[met] = cnt;
            r.score[met] = score;
         r.t = sp[0];
      Rec[] recs = (Rec[])hm.values().toArray(new Rec[0]);
      String[] ret = new String[recs.length];
      for(int i = 0; i<ret.length; i++)ret[i] = recs[i].toString();
      return ret;

By lbackstrom
TopCoder Member