NOVEMBER 2008 CONTEST RESULTS
These are the final results of the USACO NOVEMBER 2008 programming
competition.
The next official USACO contest is scheduled for 5-8 December, the
December, 2008 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 850 competitors and 402 observers, a total
of 1,253 legal entrants, the largest turnout ever! 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 216 104 485 198 -- -- 850 403 1253
114 contestants were disqualified for not following the rules; 40
had an unacceptable name (potentially among other infractions).
**********************************************************************
NOTE: Those with invalid email addresses will also lose their
credentials soon.
**********************************************************************
The 1,253 contestants and observers who successfully submitted at
least one solution came from these 65 countries:
2 ARG 351 CHN 2 FIN 12 IND 2 MDA 65 ROM 244 USA
3 ARM 4 COL 10 FRA 25 IRN 14 MEX 6 RUS 1 VEN
6 AUS 10 CUB 2 GBR 2 ISR 2 MKD 8 SGP 34 VNM
2 AZE 1 CZE 32 GEO 5 ITA 1 MNG 4 SVK 21 YUG
6 BGD 8 DEU 1 GHA 2 JPN 1 NAM 3 SVN 11 ZAF
50 BGR 1 DOM 7 GRC 11 KAZ 6 NED 4 SYR
1 BIH 1 ECU 1 HKG 1 KGZ 2 NZL 7 THA
48 BLR 9 EGY 17 HRV 3 KOR 1 PER 22 TUR
11 BRA 4 ESP 2 HUN 7 LTU 12 POL 13 TWN
40 CAN 11 EST 34 IDN 3 LVA 4 POR 17 UKR
The grading system accepted 15.59 MB of text, a total of 10,848
submissions.
Here's a summary of how the final graded submissions looked (including
observers):
Program Subs C Pascal Java
GOLD mixup2 216 160/74% 51/24% 5/ 2%
: lites 202 154/76% 41/20% 7/ 3%
: cheer 149 116/78% 30/20% 3/ 2%
: toy 85 59/69% 25/29% 1/ 1%
SILVER buyhay 330 194/59% 104/32% 32/10%
: mtime 309 182/59% 98/32% 29/ 9%
: guardian 304 177/58% 96/32% 31/10%
BRONZE swtch 731 356/49% 239/33% 136/19%
: auction 674 322/48% 221/33% 131/19%
: guard 497 253/51% 167/34% 77/15%
Mechanically and logistically, the contest ran well. It appears
that test data has been exported erroneously for years -- and no
one's program caught it until this time. The old bug was repaired
and all wrong test cases regraded. JAVA timing was messed up (again).
I've gone back to the inconsistent timing that often reports times
as much as 4x faster.
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/NOV08.htm .
Check out the new 'see submissions' options!
### GOLD Division ######################################################
Richard Peng directed the Gold contest. Thanks to him for the fine
effort. Be sure to email me if you want to direct a contest!
Click for full GOLD Division results.
The problem weightings were determined manually:
points weight 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k
------------------------------------------------------------------------------
mixup2: 200 200.0 20 20 20 20 20 20 20 20 20 20
cheer: 300 300.0 30 30 30 30 30 30 30 30 30 30
lites: 300 300.0 30 30 30 30 30 30 30 30 30 30
toy: 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 first real contest that used the "best 3" scoring
algorithm. If you have comments about it, please email me.
Seniors dominated this contest's entries, a reflection on the growing
difficult and elitism of the tasks:
Distribution by grade:
Grde # Percent
2009 63 (42.3%) ********************************
2010 60 (40.3%) ******************************
2011 13 ( 8.7%) ******
2012 9 ( 6.0%) ****
2013 2 ( 1.3%) *
2014 2 ( 1.3%) *
A super-challenging problem relegated a number of people to a score
of 800:
===== Distribution of scores =====
951..1000 1 *
901.. 950 0
851.. 900 1 *
801.. 850 0
751.. 800 26 **************************
701.. 750 3 ***
651.. 700 0
601.. 650 6 ******
551.. 600 9 *********
501.. 550 9 *********
451.. 500 6 ******
401.. 450 6 ******
351.. 400 2 **
301.. 350 14 **************
251.. 300 20 ********************
201.. 250 9 *********
151.. 200 15 ***************
101.. 150 11 ***********
51.. 100 4 ****
1.. 50 7 *******
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 .
Two folks scored above 800, with China's Yi Wu getting all but one
test correct! He is the contest's outright winner. Shang Jingbo
achieved the second highest score with a partially correct submission
for the 'toy' task. A total of 26 others solved three tasks perfectly:
2010 CHN Yi Wu 980 WINNER
2010 CHN Shang Jingbo 880 RUNNER-UP
2009 BGR Stefan Avramov 800
2009 BLR Dima Bohdanov 800
2011 USA Wenyu Cao 800
2009 RUS Alexey Cherepanov 800
2009 IRN Soheil Ehsani 800
2009 CHN Zhanpeng Fang 800
2010 ROM Cosmin Gheorghe 800
2009 CHN Town Hall 800
2010 USA Brian Hamrick 800
2012 BGR Rumen Hristov 800
2009 POL Adam Karczmarz 800
2012 BLR Gennady Korotkevich 800
2010 CHN Weicong Lu 800
2010 CHN Huai Mao 800
2010 BGR Petar Minchev 800
2009 AUS Jack Murray 800
2009 JPN Akira Nanase 800
2010 ROM Bogdan Cr. Tataroiu 800
2010 CHN Lee Tommas 800
2009 BGR Momchil Tomov 800
2009 NED Jelle van den Hooff 800
2009 GEO Levan Varamashvili 800
2009 CAN Hanson Wang 800
2010 USA Neal Wu 800
2010 CHN Wuyong Zhang 800
2011 CHN Erjin Zhou 800
Here's the breakdown of countries for these winners:
9 CHN 3 USA 2 BLR 1 POL 1 JPN 1 GEO 1 AUS
4 BGR 2 ROM 1 RUS 1 NED 1 IRN 1 CAN
A great achievement for all concerned! Congratulations to all these
fine programmers.
## SILVER Division #####################################################
Richard Peng and the others coaches worked together to direct the
Silver contest.
Click for full SILVER Division results.
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
--------------------------------------------------------------
buyhay: 96 317.2 0 8 10 10 10 8 12 12 13 13
guardian: 96 400.0 0 6 6 6 6 7 8 9 9 9 5 6 6 6 7
mtime: 94 282.8 0 11 9 10 11 11 11 10 10 11
The flood fill problem was rated most difficult while the greedy
scheduling algorithm was rated easiest.
===== Distribution of scores =====
Thirty-nine (!) competitors earned perfect scores. Several more
with 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.
**** WINNERS ****
2010 USA Jason Chow 2010 COL Andrés Mejía-Posada
2009 GBR Joel Colledge 2010 YUG Luka Milicevic
2010 ROM Palianos Cristian 2009 ESP Félix Miravé
2011 USA Andrew Das Sarma 2010 YUG Nikola Mrksic
2010 CHN Rundong Fan 2010 VNM Khanh Nguyen Xuan
2010 USA Andy Fang 2010 BRA Andre Pereira
2009 CAN Daniel Galperin 2011 SGP Mister Poe
2010 CHN Xiang Gao 2009 HRV Bruno Rahle
2012 CHN Xizhi Han 2010 CHN linbo Shao
2010 IDN Christianto Handojo 2010 GHA Ren Shen
2010 USA Tony Ho 2010 CAN Tong Shu Li
2013 USA Johnny Ho 2009 IDN Reinardus Surya Pra
2010 CHN Sheyn Hu 2009 VNM Nguyen Thanh An
2013 BGR Simeon Ivanov 2010 VNM Đại Thàn
2010 CHN Chen Jian Fei 2011 CHN Ming Wei
2010 BLR Evgeni Kostukevich 2009 USA Alex Wein
2011 CHN Hye Kyo Song 2010 CHN Li Yuliang
2010 CHN Sinya Lee 2009 ZAF Kosie van der Merwe
2009 CHN Xiaoxiao Li 2009 CHN He Zijian
2009 USA Matthew Mayers
The country breakdown for these hot programmers looks like this:
1 BGR 2 CAN 1 ESP 1 HRV 1 SGP 2 YUG
1 BLR 12 CHN 1 GBR 2 IDN 7 USA 1 ZAF
1 BRA 1 COL 1 GHA 1 ROM 3 VNM
The 85 competitors and observers above 875 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.
Click for full BRONZE Division results.
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
-----------------------------------------------
swtch: 90 277.1 0 10 10 10 10 10 10 10 10 10
guard: 96 400.0 0 8 10 11 10 11 12 11 11 12
auction: 96 322.9 0 10 10 10 11 11 10 11 11 12
Huge turnout this time! Lots of juniors, plenty of seniors. Sophomores
and younger folks also participated:
Distribution by grade:
Grde # Percent
2009 130 (26.8%) ********************
2010 196 (40.4%) *******************************
2011 88 (18.1%) *************
2012 36 ( 7.4%) *****
2013 13 ( 2.7%) **
2014 18 ( 3.7%) **
2015 4 ( 0.8%)
The scores were distributed throughout the spectrum with local
medians at perfect and the 600 range (which is the points one would
earn for getting two of three tasks perfect). The peak at 277 is
for solving the easiest task:
===== Distribution of scores =====
951..1000 87 ***************************************************************************************
901.. 950 13 *************
851.. 900 8 ********
801.. 850 4 ****
751.. 800 8 ********
701.. 750 14 **************
651.. 700 15 ***************
601.. 650 32 ********************************
551.. 600 121 *************************************************************************************************************************
501.. 550 6 ******
451.. 500 30 ******************************
401.. 450 11 ***********
351.. 400 17 *****************
301.. 350 21 *********************
251.. 300 58 **********************************************************
201.. 250 12 ************
151.. 200 2 **
101.. 150 6 ******
51.. 100 2 **
1.. 50 1 *
0.. 0 17 *****************
The scores were distributed mostly through the upper part of the
range with 86 (!) perfect scores (many folks moved up to the Silver
division during the contest; their results are not reported in the
Bronze division). This is not unusual for the first contest of the
year as folks are still being 'seeded' into their proper division.
Here's a list of the 86 perfect scores, each of whom is a winner
of this Bronze level competition:
******** WINNERS *******
2010 IDN Alham Fikri Aji 2009 CHN Cong Liu
2010 CAN tyson andre 2010 CHN Xun Lou
2010 BLR Ivan Artukhov 2011 ARM Alexandr Mamedov
2009 KGZ Bekturov Astar 2012 CHN Tommy Michael
2009 CAN alex bedley 2011 USA Doug Miller
2009 FRA Ismael BELGHITI 2010 BLR Vladimir Miranovich
2010 USA Mark Benjamin 2011 CHN Caima Moon
2009 AUS Daniel Berger 2010 USA Daniel Negulescu
2012 CHN wu bin 2011 BLR Sergey Nichiporchik
2012 BGR Simona Boiadjiiska 2010 USA Pavel Panchekha
2010 TWN TingWei Chen 2010 ROM Mihail Poasca
2012 CHN yichen chen 2013 BLR Vlad Podtelkin
2009 USA Oliver Daniels 2010 ROM Andrei Poenaru
2009 CHN Brad Dog 2011 ROM Marius Popescu
2009 CAN Eddie Du 2009 SGP Nathaniel Say
2009 IDN James Edward 2010 TWN fei shao
2010 CHN yi feng 2011 CHN Zhu Shuofei
2010 BRA Atol Fortin 2010 DEU Oliver Siebert
2009 CHN Cadillac Free 2010 USA Jesse Silliman
2010 IDN Ashar Fuadi 2011 CHN Frank Smith
2009 BLR Ivan Grishchenko 2010 ROM Ada-Mihaela Solcan
2010 CHN Yangzhou He 2010 HRV Toni Soldo
2009 IDN Thomas Hendy 2013 ROM Iulia Tamas
2012 FRA Todd Hijo 2009 YUG Vanja Petrovic Tank
2009 USA Charley Ho 2015 BLR Artem Volhin
2010 CHN Chen Hu 2009 CHN Zhaokang Wang
2010 IDN Edwin Hutomo 2010 CHN Liuyang Wang
2009 FIN Toni Huttunen 2010 CHN lei wang
2011 CHN Lee Jung Hyun 2010 USA Kevin Wang
2009 BGR George Iliev 2011 USA Zixiao Wang
2011 CHN Feifei Ji 2010 CHN vikey well
2009 CHN chen Jiecao 2011 USA Willis Wendler
2011 USA Daniel Kang 2009 IDN Bagus Seto Wiguno
2010 TUR ruken kaplan 2010 USA michael wintermeyer
2009 POL Tomasz Kleczek 2009 USA Yongzuan Wu
2012 USA Frederic Koehler 2010 BGR Wyand Wyand
2010 BLR Alexey Kolesov 2010 USA David Xiao
2010 BLR Sergey Konoplich 2011 CHN Rommy Xu
2010 USA Gregory Kronmiller 2010 CHN Huang Xuangui
2012 CHN Freepascal Lazarus 2010 TWN Skyly Yang
2009 VNM Ngocson Le 2009 CHN Zhao Yilong
2009 CAN Ke Li 2011 CHN Biany Zhang
2012 CHN xun lin 2012 CHN Xunkai Zhang
Here's the country breakdown:
1 ARM 8 BLR 27 CHN 2 FRA 1 KGZ 1 SGP 16 USA
1 AUS 1 BRA 1 DEU 1 HRV 1 POL 1 TUR 1 VNM
3 BGR 4 CAN 1 FIN 6 IDN 5 ROM 3 TWN 1 YUG
Congrats to these winners.
179 promotions to Silver: everyone over 800 points.
############################## 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