2012 Google Code Jam, Qualification Round

TL;DR version: Once again, I've qualified this year!

Here's last year's Qualification Round post for details on how the Google Code Jam works.

I was incredibly busy during the 25 hours Qualifcation round, and in fact for the third consecutive year I was out of town during the round. The cutoff was 20 points, achievable by solving the small and large inputs for one of the problems. My strategy was thus to log in shortly after the start, about 7pm Friday, and let the ideas roll around in my head all day Saturday so that I could spend a very short time coding during a brief break Saturday afternoon. Since the feedback from the codejam website doesn't reveal success or failure on the large input version until the contest is over, too late to try for more points. Even so, I was in a time crunch and so decided to trust I could get it right. Since I waited until near the end and solved the minimum, my rank was 15,158 out of the 15,193 that qualified. That's way more than the 9000+ that qualified last year. It feels like I just made it, but anyone who could earn enough points could make it. 17,803 earned at least some points, but 2,610 didn't get the 20 required.

I chose Problem B, Dancing With the Googlers, worth a total of 20 points, figuring it's the easiest one that had enough points to allow me to advance.
You're watching a show where Googlers (employees of Google) dance, and then each dancer is given a triplet of scores by three judges. Each triplet of scores consists of three integer scores from 0 to 10 inclusive. The judges have very similar standards, so it's surprising if a triplet of scores contains two scores that are 2 apart. No triplet of scores contains scores that are more than 2 apart. 
For example: (8, 8, 8) and (7, 8, 7) are not surprising. (6, 7, 8) and (6, 8, 8) are surprising. (7, 6, 9) will never happen. 
The total points for a Googler is the sum of the three scores in that Googler's triplet of scores. The best result for a Googler is the maximum of the three scores in that Googler's triplet of scores. Given the total points for each Googler, as well as the number of surprising triplets of scores, what is the maximum number of Googlers that could have had a best result of at least p? 
For example, suppose there were 6 Googlers, and they had the following total points: 29, 20, 8, 18, 18, 21. You remember that there were 2 surprising triplets of scores, and you want to know how many Googlers could have gotten a best result of 8 or better. 
With those total points, and knowing that two of the triplets were surprising, the triplets of scores could have been: 
10 9 10
6 6 8 (*)
2 3 3
6 6 6
6 6 6
6 7 8 (*) 
The cases marked with a (*) are the surprising cases. This gives us 3 Googlers who got at least one score of 8 or better. There's no series of triplets of scores that would give us a higher number than 3, so the answer is 3. 
The first line of the input gives the number of test cases, TT test cases follow. Each test case consists of a single line containing integers separated by single spaces. The first integer will be N, the number of Googlers, and the second integer will be S, the number of surprising triplets of scores. The third integer will be p, as described above. Next will be Nintegers ti: the total points of the Googlers.
I found this one rather easy, as it was just a quick math problem once I thought about it. In the regular case, seeking a best score of p would mean that the worst possible set of scores is p, p-1, p-1, and in the surprising case, p, p-2, p-2. Since scores couldn't be negative, I had to account for p being 0 or 1 as a special case. So the total for the regular case had to be at least 3p-2, and at least 0. In the surprising case, the total had to be at least 3p-4, and again, at least 0 (realistically, at least 2, with scores 2, 0, 0, or else it wouldn't be surprising).

I simply looped over the listed values, and if one was at least the regular total, it counted. If it wasn't, and S was still at least 1, and it was at least the surprising case total, it counted, and I subtracted 1 from S.

So, for the case of:
3 1 5 15 13 11
N S p t0 t1 t2

There were 3 Dancers to score. 1 had surprising scores (a spread of 2). I was to find how many could have a best score of at least 5. The regular target was 13 (5+4+4), and the surprising target was 11 (5+3+3). So, t0 and t1 qualified as regular, and t2 was the surprising case, and the answer was 4.

Rinse and Repeat for 100 cases and 1 to 100 competitors per case, and I solved the easy and hard versions rather quickly.

I'll post about Round 1A and if necessary, 1B and 1C later.


eBay Wins #24

I decided to splurge a little and spend 6 cents apiece on these two cards.

1992 Studio #61 Bobby Bonilla
 Fun fact: The Mets are paying Bobby until 2035.

1990 Score #405 Rafael Palmeiro
I may eventually try to put together a 1990 Score set. The cards are usually dirt cheap, so it'll be fun and easy on the wallet.

eBay Bargain Tracker
Total Cards Bought1887
Total Spent$35.03
Per Card1.86 cents


A Braves Contest at a Pirates Blog?

There's a contest going on from now until the first pitch of the Pirates-Braves series going on now at Pirates Treasure Room. Go comment with a "Let's go Bucs" to enter, and on the off chance the Pirates can at least split the series, you could win these cards:

2002 Upper Deck Diamond Connection - Diamond Collection #AJ Andruw Jones #166/775

2004 Topps Clubhouse Collection #JSM John Smoltz

2003 Fleer Ultra - Moonshots Memorabilia #CJ Chipper Jones

And if they manage to sweep, this card goes into the mix as well:
2008 Just Minors - Dual Signatures Silver Jason Heyward/Andrew McCutchen

What are you waiting for? Go enter now!


eBay Wins #23

I was feeling random, so I bid on and won 62 "Random 1990s" cards, most of which were from the 1980s, so all the better. Most of the cards are commons of course, but there were a few Cardinals and stars as well.

1983 Fleer #596Charlie Leibrandt
The lone 83 Fleer in the bunch.

1986 Topps #422 Mike Jorgensen
9 years later Mike would take over for a fired Joe Torre as Cardinals manager long enough for us to bring in Tony LaRussa for the next season.

1986 Topps
24 Len Barker
66 Cardinals Leaders (2)
112 Bill Campbell
114 Mike Brown
134 Carney Lansford
140 John Candelaria
150 Joaquin Andujar
161 Lee Tunnell
167 Zane Smith
216 A's Leaders
252 Bobby Castillo
304 Mike Gallego
404 Frank Robinson
422 Mike Jorgensen
433 Chris Codiroli
437 Rick Mahler
439 Rick Honeycutt
543 Jerry Narron
549 Bob Welch
566 Alfredo Griffin
583 Al Bumbry
602 Mariano Duncan (2)
731 Don Robinson
758 Dave Anderson
766 Rick Langford

1988 Topps #170 Rich Gossage
Hey look, a Hall-of-Famer. Junk wax or not, that's cool.

1988 Topps
170 Rich Gossage
564 Frank Lucchesi

1989 Donruss #119 Bert Blyleven
Another (recent) Hall-of-Famer.

1989 Donruss
47 Alex Sanchez
85 Frank White
102 Dave Martinez
109 Henry Cotto
110 Mike Marshall
114 Brook Jacoby
115 Keith Brown
119 Bert Blyleven
121 Tommy Gregg
125 Eric Plunk
131 Jose Uribe
318 Greg Gagne
336 Randy Myers
430 Bob Dernier
447 Glenn Wilson
492 Willie Upshaw
499 Zane Smith
568 Glenn Hubbard
575 Juan Nieves
578 Luis Rivera

1991 Fleer Joe Oliver
The streak had to end sometime. Here's the lone bright yellow 91 Fleer.

1991 Score #164 Jeff Reardon
1991 Score
151 Roy Smith
162 Brook Jacoby
164 Jeff Reardon
167 Gary Mielke

1992 Donruss #376 Bernard Gilkey
I don't remember much of Bernard Gilkey as a Cardinals player, as he never seemed to stand out much. He was a local guy though, and a consistent starter.

1992 Donruss
164 Alan Trammell
347 Dante Bichette
353 Mitch Williams
359 Scott Leius
365 Vicente Palacios
370 Pat Kelly
376 Bernard Gilkey

eBay Bargain Tracker
Total Cards Bought1885
Total Spent$34.91
Per Card1.85 cents


Spring Training Giveaway, part 4

[Part 1]
[Part 2]
[Part 3]

I won another contest at Number 5 Type Collection. After ranking the 5 teams I wanted from what he had to offer, I tied another reader and so wound up with half the Tigers and Red Sox.

I left just two cards for the finale, and they're my favorites of the lot.
2001 Leaf Rookies and Stars #5 Nomar Garciaparra

2004 Opening Day #70 Nomar Garciaparra
Nomar's one of my favorite players, and the main focus of my non-Cardinal collecting.  Thanks again to Matt at Number Five 5 Collection for the great giveaway!


Spring Training Giveaway, part 3

[Part 1]
[Part 2]

I won another contest at Number 5 Type Collection. After ranking the 5 teams I wanted from what he had to offer, I tied another reader and so wound up with half the Tigers and Red Sox.

Let's start with some minor leaguers we may never hear from:
2007 Tristar Prospects Plus #99 Cale Iorg
 I actually recognized this last name and sure enough, he's the nephew of former Cardinal Dane Iorg. Of course, Dane is from too far back for me to remember.
2007 Tristar Prospects Plus #8 Ryan Dent

2007 Tristar Prospects Plus #76 Brock Huntzinger

2007 Tristar Prospects Plus #85 Anthony Rizzo

2007 Tristar Prospects Plus #94 David Mailman

2007 Upper Deck #574 Matt Clement
 Matt Clement was technically a Cardinal for a bit, but he never saw the majors after an injury and some minor league rehab.

2007 Upper Deck #581 Mike Timlin
 I mostly remember that we had Timlin during 2001 because he was on the team when Bud Smith thew a No-Hitter. My neurons seem to connect in odd ways.
2007 Upper Deck #591 Manny Ramirez
 This would have been a much more exciting card a few years ago. PED suspensions really put a damper on my excitement.
2008 Topps Updates and Highlights #UH123 Matt Joyce

2008 Topps Updates and Highlights #UH153 Armando Galarraga
 Mr. Almost-Perfect himself.

2008 Topps Updates and Highlights #UH195 Chris Carter
I'm a little tired or I'd make a Minnesota Vikings/X-Files reference, and it'd be hilarious.

2008 Topps Updates and Highlights #UH221 J.D. Drew
 Ah J.D. Drew, my first experience in having to root for an outwardly greedy player. I remember thinking he wasn't so great to Philadelphia for refusing to sign and playing in an independent league. Then the Cardinals drafted him the following year. I was a bit conflicted, and I'm still not sure what my opinion would be if he had been drafted by someone else instead.

2008 Upper Deck Timeline #41 Justin Verlander

2010 Upper Deck #99 George Kottaras

2010 Upper Deck #192 Edwin Jackson
Even though he and Colby Rasmus are both gone now, I think this deal worked out pretty nicely for the Cardinals in their 2011 World Series run.

2010 Upper Deck #207 Ryan Perry

Well, I've saved the best for last in part 4. You might be able to guess what's coming based on the teams I chose that I consider it the best.


Spring Training Giveaway, part 2

[Part 1]
I won another contest at Number 5 Type Collection. After ranking the 5 teams I wanted from what he had to offer, I tied another reader and so wound up with half the Tigers and Red Sox.
1981 Fleer Stickers #13 Carl Yastrzemski

1981 Fleer Stickers #34 Dennis Eckersley

1981 Fleer Stickers #53 Jim Rice

1981 Fleer Stickers #58 Carlton Fisk
All 4 of these Fleer Stickers have Hall of Famers on them. That's pretty awesome.

1982 Donruss #5 Alan Trammell

1983 Donruss #5 Jack Morris
It's kind of crazy that Donruss used the same Diamond King design in 1982 and 1983. I never knew that before just now.
1986 Sports Design Products Tigers #5 Mickey Cochrane
It took me awhile to track down what set this one was from. The confusion came in that the back just says 1986 Sports Design Products, but there was a league-wide set that year by that name as well.

1989 Bowman #26 Roger Clemens
This card doesn't fit in a regular sleeve. Between these and Topps Big, I need to find some more accommodating supplies.

1992 Denny's #5 Jack Clark
I'd never seen these Denny's cards before, I must have started collecting after they came out that year. I have several from later years.

2005 Fleer Tradition #141 Bobby Higginson

2005 Fleer Tradition #121 Johnny Damon

2006 Tristar Prospects Plus #21 Jason Place

2007 Topps #28 Brandon Inge

2007 Topps #87 Alexis Gomez

2007 Topps #280 Curt Schilling

2007 Topps #294 Mike Rabelo

2007 Topps #304 Kenny Rogers


Spring Training Giveaway, part 1

I won another contest at Number 5 Type Collection. After ranking the 5 teams I wanted from what he had to offer, I tied another reader and so wound up with half the Tigers and Red Sox. Here's part 1 of what he sent me (because of my previously mentioned obsession with tagging the sets).

1993 Stadium Club #5 Tony Phillips

2000 Topps #60 Pedro Martinez

2001 Topps Chrome - Before There Was Topps #BT5 Ty Cobb

2004 Upper Deck #107 A.J. Hinch

2005 Topps Total #395 Jeremy Bonderman

2005 Topps Update #UH33 Placido Polanco

2007 Upper Deck Future Stars #14 Curt Schilling

2007 Upper Deck Future Stars #11 David Ortiz

2008 Allen and Ginter - Mini Black Border #204 Julio Lugo

2008 Allen and Ginter - Mini #338 Placido Polanco

2008 Allen and Ginter - Mini A&G Back #333 Coco Crisp

2008 Upper Deck #494 Joel Zumaya