DECEMBER 2008 CONTEST RESULTS
These are the final results of the USACO DECEMBER 2008 programming
competition.
The next unofficial USACO contest is scheduled for late December
-- watch your mailbox for the announcement. Like last year's holiday
contest, this one will be extremely challenging with a long (24-48
hour) participation time.
The next official USACO contest is scheduled for 9-12 January, the
January, 2009 USACO programming contest.
Our goal in these contests is to cultivate interest in computer
programming among pre-college students and recognize those who are
outstanding performers.
The elite contest had 708 competitors and 354 observers, a total
of 1,062 legal entrants! No Level One contest was offered.
GOLD SILVER BRONZE LEVEL1 TOTAL
Comp's Obsvrs Comp's Obsvrs Comp's Obsvrs Comp's Obsvrs Comp's Obsvrs Entries
APR 2003 257 39 104 9 -- -- -- -- 361 48 409
NOV 2003 300 106 166 31 -- -- -- -- 466 192 658
DEC 2003 284 76 141 24 -- -- -- -- 301 228 529
JAN 2004 313 69 153 31 108 38 -- -- 574 138 712
FEB 2004 236 45 174 36 69 23 -- -- 479 104 583
MAR 2004 207 42 194 41 91 17 -- -- 492 100 592
NOV 2004 657 205 --- -- -- -- -- -- 657 205 862
DEC 2004 163 54 132 25 339 127 -- -- 634 209 843
JAN 2005 150 34 166 36 390 148 -- -- 706 217 924
FEB 2005 165 41 206 42 398 122 -- -- 769 205 974
MAR 2005 178 39 221 43 359 104 -- -- 758 186 944
OCT 2005 253 53 235 41 266 89 -- -- 754 183 937
NOV 2005 149 50 149 33 309 121 -- -- 607 204 811
DEC 2005 136 35 180 35 280 95 65 33 629 198 859
JAN 2006 137 29 177 32 250 78 53 23 617 162 779
FEB 2006 179 41 168 19 242 83 43 11 632 154 786
MAR 2006 184 44 128 22 296 80 42 14 650 160 810
OPEN2006 161 35 144 18 237 52 35 10 577 115 692
OCT 2006 642 239 881
NOV 2006 238 93 181 63 207 82 130 56 767 283 1050
DEC 2006 220 83 153 45 225 91 89 34 687 253 940
JAN 2007 234 77 151 41 221 78 72 30 678 226 904
FEB 2007 213 67 137 39 159 62 59 33 568 201 769
MAR 2007 220 63 164 44 208 75 55 28 647 210 857
OPEN2007 161 57 141 29 118 30 18 6 438 122 560
OCT 2007 592 182 774
NOV 2007 208 108 133 36 327 122 -- -- 668 266 934
DEC 2007 203 79 156 40 316 121 -- -- 675 240 915
JAN 2008 175 61 151 52 263 98 -- -- 589 211 800
FEB 2008 171 52 204 67 313 151 -- -- 688 270 958
MAR 2008 199 77 232 70 274 137 -- -- 705 284 984
OPEN2008 161 49 172 31 158 53 -- -- 491 133 624
OCT 2008 143 81 216 90 396 157 -- -- 755 328 1083
NOV 2008 149 101 217 104 485 198 -- -- 851 403 1254
DEC 2008 177 100 226 101 305 153 -- -- 708 354 1062
Only 12 contestants were disqualified for not following the rules
-- the smallest number ever!
**********************************************************************
NOTE: Those with invalid email addresses will also lose their
credentials soon.
**********************************************************************
The 1,062 contestants and observers who successfully submitted at
least one solution came from these 68 countries:
1 ARE 39 CAN 4 ESP 18 IDN 3 LVA 48 ROM 11 TUR
9 ARG 1 CHL 7 EST 18 IND 10 MEX 7 RUS 14 TWN
6 ARM 210 CHN 3 FIN 22 IRN 1 MKD 10 SGP 14 UKR
6 AUS 6 COL 9 FRA 1 ISR 2 MNG 4 SVK 214 USA
1 AZE 9 CUB 2 GBR 4 ITA 1 NAM 4 SVN 1 VEN
12 BGD 2 CZE 32 GEO 2 JPN 5 NED 1 SWZ 22 VNM
60 BGR 9 DEU 8 GRC 17 KAZ 1 NZL 4 SYR 18 YUG
3 BIH 1 DOM 2 HKG 3 KGZ 2 PER 6 THA 12 ZAF
44 BLR 1 ECU 16 HRV 2 KOR 18 POL 1 TKM
7 BRA 13 EGY 2 HUN 9 LTU 6 POR 1 TTO
The grading system accepted 12.53 MB of text, a total of 7,793
submissions.
Here's a summary of how the final graded submissions looked (including
observers):
Program Subs C Pascal Java
GOLD treat 241 189/78% 45/19% 7/ 3%
: sec 223 176/79% 37/17% 10/ 4%
: winchk 101 75/74% 22/22% 4/ 4%
: fence 84 65/77% 18/21% 1/ 1%
SILVER hay4sale 320 203/63% 67/21% 50/16%
: patheads 301 193/64% 59/20% 49/16%
: jigsaw 90 57/63% 15/17% 18/20%
BRONZE hayexp 481 271/56% 116/24% 94/20%
: badgras 359 219/61% 88/25% 52/14%
: chkr 235 143/61% 56/24% 36/15%
Mechanically and logistically, the contest ran well with no real
interruptions or degradations.
The timings for JAVA are reported just as for C (et al.), though
JAVA runs slower, so all JAVA times are actually divided by 2.0.
If your JAVA program ran too slow -- perhaps you're using RandomAccess
input instead of BufferedReader input. The latter can be orders of
magnitude faster!
Test data and analyses are available at http://ace.delos.com/DEC08.htm
. Check out the new 'see submissions' options!
### GOLD Division ######################################################
MIT aces Jacob Steinhardt and David Benjamin directed the Gold
contest. Thanks to them for the fine effort. Be sure to email me
if you want to direct a contest!
The problem weightings were determined manually; task ratings were
old-IOI-style:
points weight 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k
-----------------------------------------------------------------------------
treat: 100 100.0 10 10 10 10 10 10 10 10 10 10
sec: 273 270.0 21 21 21 21 21 21 21 21 21 21 21 21 21
winchk: 336 330.0 28 28 28 28 28 28 28 28 28 28 28 28
fence: 400 400.0 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
This is the last real contest that will use the "best 3" scoring
algorithm. We'll be going back to 'sum of all submissions' next
time.
*Juniors* dominated this contest's entries, a reflection of the
number of promotions last month:
Distribution by grade:
Grde # Percent
2009 66 (37.3%) ****************************
2010 73 (41.2%) *******************************
2011 21 (11.9%) *********
2012 10 ( 5.6%) ****
2013 5 ( 2.8%) **
2014 2 ( 1.1%)
Another very challenging contest (that did a great job of separating
the top competitors but pushed a number of folks down to the sub-500
level) had this distribution:
===== Distribution of scores =====
951..1000 3 ***
901.. 950 2 **
851.. 900 3 ***
801.. 850 1 *
751.. 800 3 ***
701.. 750 1 *
651.. 700 1 *
601.. 650 6 ******
551.. 600 7 *******
501.. 550 3 ***
451.. 500 4 ****
401.. 450 12 ************
351.. 400 29 *****************************
301.. 350 9 *********
251.. 300 6 ******
201.. 250 7 *******
151.. 200 5 *****
101.. 150 25 *************************
51.. 100 32 ********************************
1.. 50 18 ******************
0.. 0 0
Of course, the curve is very much affected by the scoring algorithm
used. Other scoring algorithms push the curve lower.
The best way we know of to improve your score is still the USACO
training pages at http://train.usaco.org .
Nine folks scored above 800, with Polands's Michal Makarewicz as
the only perfect scorer! He is the contest's outright winner. USA's
Neal Wu achieved the second highest score missing only a single
test case:
2010 POL Michal Makarewicz 1000 *** WINNER ***
2010 USA Neal Wu 980 *** RUNNER UP ***
2009 CHN Biye Jiang 952 *** THIRD PLACE ***
2010 ROM Cosmin Gheorghe 925
2010 ROM Bogdan Cr. Tataroiu 918
2009 CAN Hanson Wang 880
2009 POL Robert Kozikowski 862
2012 BLR Gennady Korotkevich 860
2011 CHN Erjin Zhou 808
Here's the country breakdown:
1 BLR 1 CAN 2 CHN 2 POL 2 ROM 1 USA
The different style of problems from this set of directors exposed
the various training cultures from participating countries.
A great achievement for all concerned! Congratulations to all these
fine programmers.
## SILVER Division #####################################################
Rob Kolstad and the other coaches worked together to direct the
Silver contest.
These weights (and the scores below) use the normal USACO scoring
algorithm:
points weight 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q
-----------------------------------------------------------------------------------------------
hay4sale: 95 224.3 0 8 7 7 8 8 8 8 9 9 15 8
patheads: 99 375.7 0 4 4 4 4 4 9 12 9 13 12 11 13
jigsaw: 98 400.0 0 4 4 4 4 4 3 4 5 4 3 3 3 4 3 3 3 4 4 4 4 4 5 5 5 5
The recursive/data structure problem (jigsaw) was rated the most
difficult, despite the plan that the backpack algorithm would be
most challenging.
After mailing out the preliminary results, I added to hay4sale a
new test case from a nice Chinese student who pointed up a hole in
our testing.
===== Distribution of scores =====
Four competitors earned perfect scores; nine more achieved 800
points or more. Several perfect or very high scores took mid-contest
promotions and moved to the gold division; their scores are generally
not shown here or in the silver results below. Congratulations to
the four winners!
2011 CHN Caima Moon 1000 *** WINNER ***
2009 HRV Filip Barl 1000 *** WINNER ***
2010 TWN TingWei Chen 1000 *** WINNER ***
2010 TWN Skyly Yang 1000 *** WINNER ***
2009 DEU Oleg Yuschuk 981
2011 CHN yongxing deng 965
2012 CHN Yiqing Hua 965
2009 RUS Sergey Nizovtsev 965
2010 ROM Andrei Misarca 948
2010 USA Jesse Silliman 909
2009 FRA Lacroix Timothée 884
2009 EGY ahmed aly reda 857
2012 CHN Tommy Michael 804
The country breakdown for these hot programmers looks like this:
4 CHN 1 EGY 1 HRV 1 RUS 1 USA
1 DEU 1 FRA 1 ROM 2 TWN
The 14 competitors and observers above 900 points have been promoted
to the Gold division.
Bear in mind that programming contest scores are spread out across
hundreds of points instead of the usual 7 point spread for 93-100%
that so many student achieve in their academic pursuits. Congrats
to these hot scorers in a very difficult contest.
## BRONZE Division #####################################################
Rob Kolstad directed the Bronze contest.
Three problems this time with weightings from medium-low to high.
The scoring and ratings were determined by the standard USACO method.
points weight 1 2 3 4 5 6 7 8 9 a
-----------------------------------------------
chkr: 89 400.0 0 9 9 10 10 10 10 10 10 11
badgras: 52 384.0 0 7 7 7 8 8 15
hayexp: 83 216.0 0 9 9 9 9 9 9 9 10 10
The chkr task was targeted at recursion-aware programmers; the
badgras task could be solved by breadth-first search (or other
standard flood-fill attacks).
Juniors ruled with 38%, with seniors and sophomores at 21-22%:
Distribution by grade:
Grde # Percent
2009 68 (22.3%) *****************
2010 117 (38.4%) *****************************
2011 65 (21.3%) ****************
2012 25 ( 8.2%) ******
2013 11 ( 3.6%) **
2014 17 ( 5.6%) ****
2015 2 ( 0.7%)
The scores were distributed throughout the upper 80% of the spectrum
with local medians as shown below. The peak at 216 is for solving
the easiest task. The 889's are for those who missed the single new
test case for badgras. The 600s are for getting badgras and hayexp;
the 489s missed a single badgras case.
===== Distribution of scores =====
951..1000 27 ***************************
901.. 950 2 **
851.. 900 32 ********************************
801.. 850 4 ****
751.. 800 8 ********
701.. 750 9 *********
651.. 700 8 ********
601.. 650 9 *********
551.. 600 26 **************************
501.. 550 2 **
451.. 500 42 ******************************************
401.. 450 8 ********
351.. 400 11 ***********
301.. 350 8 ********
251.. 300 15 ***************
201.. 250 84 ************************************************************************************
151.. 200 2 **
101.. 150 0
51.. 100 6 ******
1.. 50 0
0.. 0 2 **
A total of 27 competitors (not counting those who moved up mid-contest)
earned perfect scores:
******** WINNERS *******
2010 BLR Michael Astashkevic 2010 KAZ Igor Prokopiyev
2010 TWN shik chen 2012 ROM Andrei Purice
2010 VNM Windy Flame 2010 BLR Dmitriy Sharkov
2012 BGR Alexander Gyorev 2010 THA Sira Songpolrojjana
2009 SVN Nace Hudobivnik 2014 BGR valeria staneva
2010 POR Francisco Huhn 2010 ARM Hayk Teanyan
2010 USA Actair Johnson 2009 UKR Marina Varlamova
2009 BLR Alexander Kulikovsk 2009 CHN yilun xie
2009 USA Watson Ladd 2011 USA Anthony Zhao
2010 ROM Ionescu Marius 2012 CHN Tom Zhao
2010 KAZ Abzal Orazaliyev 2010 CHN Revenge Zhu
2010 TWN oliver orz 2014 CHN tom zou
2010 RUS Dmitry Osmakov 2011 TUR Ahmet ÖGE
2014 ROM Silvia Pripoae
Here's the country breakdown:
1 ARM 4 CHN 4 ROM 1 THA 1 UKR
2 BGR 2 KAZ 1 RUS 1 TUR 3 USA
3 BLR 1 POR 1 SVN 2 TWN 1 VNM
Congrats to these winners.
114 promotions to Silver: everyone 750 points or above.
############################## GENERAL ###################################
## About the USACO Internet Programming Contests
These contests (the GOLD division in particular) are just incredibly
hard... really amazingly hard -- more so nowadays than even just a
year or two ago.
Winners must master not only algorithmic techniques like dynamic
programming but also the ability to write bug-free code quickly.
This requires practice and skill. Don't despair if you didn't get
a perfect score this time -- it is hard!
Furthermore, the scoring mechanism is set up so that a huge percentage
of finishers scores in the 0..500 range -- different from many
contests where everyone finishes in the 800..1000 range and the
0..800 range is empty. If we don't do this, we can't distinguish
among the top competitors.
## Want to Learn More?
Check out the USACO training pages at http://ace.delos.com/usacogate .
They provide practice challenges that can help you move up in the
rankings.
## How USACO Scoring Works
The score results are shown below. I used a program to determine
how much each problem was worth and how much each test case was
worth. Basically, it counts how many people got test cases and
problems wrong and uses that to estimate a difficulty and choose a
weight.
Each problem has a certain number of test cases along with a "weight"
that tells how many of the 1,000 points come from that program.
The test cases are also weighted; here is an example:
points weight 1 2 3 4 5 6
------------------------------
probname: 39 396.6 6 5 6 5 6 11
If you score full marks on cases 1, 2, 3, and 4, you'd have 6+5+6+5=22
out of 39 points for this problem and you receive:
22/39 * 396.6 = 223.7
total points out of 396.6 possible. The sum of each problem's
points is your total score.
## Closing (Thanks and Solicitation)
Thanks to the USACO coaches who helped bring this contest together.
Special thinks to our translators.
USACO accepts -- and uses -- problem submissions from anyone! You
have a real leg up in the contest if we use your problem. Feel
free to send programming tasks to me. We now have a staff of 20
coaches and assistant coaches who vet the problems and create
prototype solutions. This enables us to have many contests throughout
the year with at least some level of predictable quality.
====================================================================
((__)) Rob Kolstad USACO Head Coach
(00) kolstad@sage.org +1 719-481-6542
-nn--(o__o)--nn- http://www.usaco.org Colorado Springs, CO
====================================================================
RESULTS:
GOLD Division
SILVER Division
BRONZE Division