Intel® Software Network

The judges were pleasantly surprised with the variety of solution approaches submitted. These ranged from the straightforward backtracking algorithm to using graph properties to prune the search to using constraint programming. A variety of parallel decomposition approaches were exhibited.

Five different sets of data files were used to compute the execution score for this problem. Two had been given as examples by the judges within the ISN problem forum (NFC and ShortLeague), one was included as a test file from nickbes (City_1000_50_2000_700), the other two were constructed cases by the judges that have no routes (one had three nodes that, if removed, broke the graph into three separate components; and the other had all 34 teams with an away game on the 15th and 29th day of each data line).

All executions were timed. A maximum of 10 minutes (600 seconds) was allowed for each data set. If an application exceeded this limit or terminated with some form of runtime error, a time of 600 secods was recorded for the time on that data file. The total execution time of all five executions was summed and a a socre between 100 and 0 was awarded based on where the total fell within the range of the minimum and 3000 seconds.

Ten penalty points were decucted for each route that was not correct. Thus, all 20 points for a data set could be lost if both the firstroute.txt and lastroute.txt files held the incorrect routes or the program decalred no route existed when there were solutions.

There were 7 submissions of code solutions, 3 on Linux and 4 on Windows. One entry was in Java, one used Haskell, one used Cilk++, two used C#, and the final two were written in C/C++.

Point spread:

100
88 87
47 47
36
17

The write-up portion of each entry was read and scored by two judges. Each judge used the 10-30-10 breakdown of points for serial algorithm description, parallel algorithm description, and performance, respectively. One important component to the judging was to determine how close the submission was for publication on ISN. The assigned score was the average of the two judges scores.

Point spread:

50 50
42 42 41
25 23

Bonus points were given for contestant’s forum posts made before the problem entries were closed. Five points per post (maximum 25 points possible) were awarded.

The overall winner was akki, who had the fastest code execution, especially on the City_1000_50_2000_700 data set. The highest scored write-ups were submitted by BradleyKuszmaul and mdm100.