 |
| 2010 Topps Chrome - Refractor #19 John Lackey |
| eBay Bargain Tracker | |
| Total Cards Bought | 1899 |
| Total Spent | $36.71 |
| Per Card | 1.933 cents |
2012-05-31
eBay Wins #30
Topps Chrome is shiny. Refractors are shiny, but in a little bit different way. Chrome Refractors are therefore the ultimate in shiny. So, how could I afford not to drop 16 cents on this card?
2012-05-30
2012 Google Code Jam, Round 1B
In the second part of Round 1, with 1000 of the qualifiers ineligible due to already advancing, 3273 people scored points. Only the top 1000 would advance. This put the cutoff at 27 points in 1 hour 19 minutes, or 28 points or more.
I first attempted Problem A: Safety in Numbers.This problem is framed as a reality show that is apparently similar to Dancing with the Stars. Here are the bare facts, with a longer description available at the link.
I first attempted Problem A: Safety in Numbers.This problem is framed as a reality show that is apparently similar to Dancing with the Stars. Here are the bare facts, with a longer description available at the link.
- There are N contestants
- Each contestant gets a score from the judges from 0 to 100
- Based on audience voting, the second part of the score is determined by multiplying the percentage of audience votes received by the total points awarded by the judges.
- For example, if there are 2 contestants, scored 20 and 10 by the judges, they will split an additional 30 points based on the share of audience votes, so the final score may fall anywhere from 50-10 to 20-40.
- In case of a tie for the lowest score, no one is eliminated that week, otherwise the lowest is eliminated.
33.33 66.67
because if the first contestant gets 1/3 of the vote, they'll get 10 more points for a total of 30, and the second contestant can't beat him, but can only tie him. The same logic applies for contestant 2. a 2/3 vote would give him 30 and make him unbeatable (but tie-able, this is important to remember but I'll stop saying it now).
I struggled for awhile with this problem, first thinking I just needed to split the audience vote between the each contestant and the worst judged contestant, which works in the 2 contestant case. Another sample set was:
24 30 21
with a stated answer of
34.666667 26.666667 38.666667
This one flustered me because my algorithm said that giving 34.6% of the 75 audience points to #1 yielded a total of 50 points, and giving the other 65.3% to #3 yielded a total of 70, meaning #1 would lose. After a few minutes, I smacked myself in the forehead and realized #1 would be safe, because #2 would be stuck at 30 in that case. This led me to a closer solution, that each contestant needed enough audience votes to get to 1/N of the total points. So for this case with 75 judge points (and 75 audience points), that meant percentages that led to 50 total points would be the correct answer.
There was one more subtlety, what if a contestant already had more than their 1/N share without any audience votes at all? For example:
45 1 1 1
In this case, there are 96 total points, so each one would need 24 based on the previous assumption. But giving 25% to #2 would yield for him 13 total points, over the required 1/N, but #3 and #4 could each get 37.5% and beat him. I modified my algorithm again to ignore any contestants, and their points, if they were already over the 1/N threshold. The rest of the contestants would need to reach, in this case
1/(N-1) * (96 - 45) = 17 points
This yielded an answer of
0 33.3 33.3 33.3
which makes sense. Contestant #1 is already safe, and the others are on even footing, so splitting the points 3 ways keeps them all safe.
I used this algorithm to solve the easy problem, but as it turns out, it wasn't exactly correct. There were more subtleties around having lots of point values near the 1/N cutoff, and still more that were higher than the new cutoff of 1/(N-1) of a lesser value. As a result, my large solution failed. The problem author suggested using a binary search in the post-contest analysis, which was way off from what I did.
I spent lots of time on Problem A, so then decided to go straight for Problem C: Equal Sums, as it was worth a few more points than problem B if solved in full, and I thought I might need them.
This problem has a very simple setup, and a very complex answer. Given a set of integers, find two subsets with the same sum. The small input would be a set of 20 positive integers under 10,000. I actually iterated over all subsets, at least until I found an answer. This meant for each set, I could loop over up to 2^20, or 1,048,576 subsets if none had a matching sum. I wasn't sure that was feasible in the 4 minutes allowed, but it wound up working.
For the large input, the set had 500 integers under 1,000,000,000,000. This meant using the same algorithm was likely not an option, as 2^500 is a very large number of subsets to loop over, and I certainly wouldn't be able to store all of the sums in the case that I had to get all the way to the end and find there were no matches. I did some searching online and found that this is roughly equivalent to an NP-complete problem, the Subset Sum problem. I was very low on time by this point so I just modified my original code to loop over all 2^500 solutions, after all, I had 8 minutes. I ran it, and it finished very quickly, causing me to question if it really did what it was supposed to. I had no time to check as the clock was winding down, so I submitted the large input without looking at it.
Just a minute or so later I found out it was wrong. There was another bug in my code that reads the input, as it can't handle numbers greater than 32 bits. Once again, at least I've found something to fix for next year. If you want an in-depth explanation of the solution to this problem, I highly suggest reading the contest analysis for it, but in a nutshell, because of the size of the numbers and the sheer numbers of available subsets, there must be matching sum subsets, and lots of them. It is actually sufficient to choose random 6-number subsets until two with matching sums are found. It seems crazy, but that's math for you. I've actually gone back to read the "Rigorous proof" section of the analysis several times, and each time it makes a little more sense to me.
In the end, I finished with a paltry 16 points, putting me in 2262nd place for this round. Round 1C was the next day at 4am local time, since the Code Jam tries to scatter the start times to be fair to the whole world. I opted not to wake up for that one, so that ends my Code Jam journey this year.
I struggled for awhile with this problem, first thinking I just needed to split the audience vote between the each contestant and the worst judged contestant, which works in the 2 contestant case. Another sample set was:
24 30 21
with a stated answer of
34.666667 26.666667 38.666667
This one flustered me because my algorithm said that giving 34.6% of the 75 audience points to #1 yielded a total of 50 points, and giving the other 65.3% to #3 yielded a total of 70, meaning #1 would lose. After a few minutes, I smacked myself in the forehead and realized #1 would be safe, because #2 would be stuck at 30 in that case. This led me to a closer solution, that each contestant needed enough audience votes to get to 1/N of the total points. So for this case with 75 judge points (and 75 audience points), that meant percentages that led to 50 total points would be the correct answer.
There was one more subtlety, what if a contestant already had more than their 1/N share without any audience votes at all? For example:
45 1 1 1
In this case, there are 96 total points, so each one would need 24 based on the previous assumption. But giving 25% to #2 would yield for him 13 total points, over the required 1/N, but #3 and #4 could each get 37.5% and beat him. I modified my algorithm again to ignore any contestants, and their points, if they were already over the 1/N threshold. The rest of the contestants would need to reach, in this case
1/(N-1) * (96 - 45) = 17 points
This yielded an answer of
0 33.3 33.3 33.3
which makes sense. Contestant #1 is already safe, and the others are on even footing, so splitting the points 3 ways keeps them all safe.
I used this algorithm to solve the easy problem, but as it turns out, it wasn't exactly correct. There were more subtleties around having lots of point values near the 1/N cutoff, and still more that were higher than the new cutoff of 1/(N-1) of a lesser value. As a result, my large solution failed. The problem author suggested using a binary search in the post-contest analysis, which was way off from what I did.
I spent lots of time on Problem A, so then decided to go straight for Problem C: Equal Sums, as it was worth a few more points than problem B if solved in full, and I thought I might need them.
This problem has a very simple setup, and a very complex answer. Given a set of integers, find two subsets with the same sum. The small input would be a set of 20 positive integers under 10,000. I actually iterated over all subsets, at least until I found an answer. This meant for each set, I could loop over up to 2^20, or 1,048,576 subsets if none had a matching sum. I wasn't sure that was feasible in the 4 minutes allowed, but it wound up working.
For the large input, the set had 500 integers under 1,000,000,000,000. This meant using the same algorithm was likely not an option, as 2^500 is a very large number of subsets to loop over, and I certainly wouldn't be able to store all of the sums in the case that I had to get all the way to the end and find there were no matches. I did some searching online and found that this is roughly equivalent to an NP-complete problem, the Subset Sum problem. I was very low on time by this point so I just modified my original code to loop over all 2^500 solutions, after all, I had 8 minutes. I ran it, and it finished very quickly, causing me to question if it really did what it was supposed to. I had no time to check as the clock was winding down, so I submitted the large input without looking at it.
Just a minute or so later I found out it was wrong. There was another bug in my code that reads the input, as it can't handle numbers greater than 32 bits. Once again, at least I've found something to fix for next year. If you want an in-depth explanation of the solution to this problem, I highly suggest reading the contest analysis for it, but in a nutshell, because of the size of the numbers and the sheer numbers of available subsets, there must be matching sum subsets, and lots of them. It is actually sufficient to choose random 6-number subsets until two with matching sums are found. It seems crazy, but that's math for you. I've actually gone back to read the "Rigorous proof" section of the analysis several times, and each time it makes a little more sense to me.
In the end, I finished with a paltry 16 points, putting me in 2262nd place for this round. Round 1C was the next day at 4am local time, since the Code Jam tries to scatter the start times to be fair to the whole world. I opted not to wake up for that one, so that ends my Code Jam journey this year.
2012-05-29
Yet Another Contest Win from Sports Card Info
If you've never been to Sports Card Info, I highly suggest you add it to your daily blog reading, as Ross generously has a contest every week, and sometimes even two at once. This is the third contest of his I've won, and oddly enough all 3 have been for hockey cards. First there was a Rip Card with a Taylor Hall autograph inside, and next a relic card of Niklas Backstrom. Let's see what came in the mail this time:
It's another relic, from this contest. From the disclaimer on the the back I see these aren't NHL/NHLPA licensed products, which explains the lack of any Ducks logo on the card.
Thanks yet again to Ross for giving away so much great stuff!
 |
| 2011-12 ITG Captain C - Game Used Jersey #M-48 Ryan Getzlaf |
Thanks yet again to Ross for giving away so much great stuff!
2012-05-28
A Zack Greinke contest and College World Series
I recently started following Baseball Cards, Sports, and Life, I think by following a link from someone's trade post. Well I found it just in time, because now there's a contest going on for a Zack Greinke relic card.
I haven't jumped on the 2012 Archives bandwagon myself, but I know lots of others have. Of course, I wouldn't mind a free card to start me off. Go leave a comment on the contest post and follow his blog to enter, and good luck to you!
The second contest going on is the Third Annual College World Series Contest at Autographed Cards. For the first step, just pick the final 8 from the 64 currently in the tournament. And of course, promote it like I am for a bonus point. I didn't do too well last year, but I'll give it another shot this year.
 |
| 2012 Topps Archives - 1956 Topps Relics #56R-ZG Zack Greinke |
The second contest going on is the Third Annual College World Series Contest at Autographed Cards. For the first step, just pick the final 8 from the 64 currently in the tournament. And of course, promote it like I am for a bonus point. I didn't do too well last year, but I'll give it another shot this year.
2012-05-27
eBay Wins #29
I haven't dug through my unorganized cards enough to find any more of these, but I bet I have at least a half-dozen Denny's cards from each year they offered them. Either I was really good at convincing my parents to change their dining habits, or my dad secretly really liked Denny's and went along with it, because I think we probably went their every Sunday morning for the duration of the card promotions.
I had been bidding on several of these unopened packs, but the prices kept getting too high and felt like too much for 1 single card. I landed this one for 15 cents, and ripped it open right away.
Well, it's not Ozzie, but a surefire Hall of Famer will do. Based on reading online it looks like there were 28 cards in the set, 1 from each team.
I had been bidding on several of these unopened packs, but the prices kept getting too high and felt like too much for 1 single card. I landed this one for 15 cents, and ripped it open right away.
 |
| 1995 Denny's Pack |
 |
| 1995 Denny's #14 Greg Maddux |
| eBay Bargain Tracker | |
| Total Cards Bought | 1898 |
| Total Spent | $36.55 |
| Per Card | 1.926 cents |
2012-05-25
Big Pile, part 4
[Part 1]
[Part 2]
[Part 3]
Josh at Royals and Randoms had a draft-style contest called Big Pile way back in late 2011, and I misplaced the envelope until this week.
You don't see a lot of guys wearing #77 on cards.
Fun fact: Adam Wainwright is on my fantasy baseball team this year, and threw a Complete Game Shutout this week. We have both CG and SHO as categories, and 1 will usually win it for you for the week. I forgot to put him in, and left him on the bench. D'oh!
The Dan Haren-Mark Mulder trade was really unwise in retrospect. It made me nervous at the time, but I thought we'd get a few solid years of All-Star pitching. Of course, I'd be a heck of a GM with the benefit of hindsight in all trades.
Come back, Chris!
I like the Black and White look of this card, and all things Heritage, so I had to draft this Edmonds.
As he's the reigning World Series (and NLCS) MVP, I'll consider this the best card of the bunch. Hopefully he's got a lot of his career story left to write, though.
That's it for the Big Pile. A big thanks to Josh for giving away 360 or so cards to 12 lucky readers.
[Part 2]
[Part 3]
Josh at Royals and Randoms had a draft-style contest called Big Pile way back in late 2011, and I misplaced the envelope until this week.
 |
| 2011 Topps #212 Pedro Feliz |
 |
| 2007 Fleer Ultra #152 Adam Wainwright |
 |
| 2006 Bowman #183 Mark Mulder |
 |
| 2006 Bowman #44 Chris Carpenter |
 |
| 2001 Bowman Heritage #17 Jim Edmonds |
 |
| 2009 O-Pee-Chee #579 David Freese |
That's it for the Big Pile. A big thanks to Josh for giving away 360 or so cards to 12 lucky readers.
2012-05-24
Big Pile, part 3
[Part 1]
[Part 2]
Josh at Royals and Randoms had a draft-style contest called Big Pile way back in late 2011, and I misplaced the envelope until this week.
I remember when these came out in 1997, thinking they'd be really cool, then seeing a rather high price and never buying any. It probably didn't help that I was 14 with no job.
How could I resist a shiny, diecut card like this?
Junk wax but a star player. It seems like these are a little hard to find, so I went ahead and picked this card.
I had Jason Kendall on a lot of fantasy baseball teams in the early 2000s, which caused me to follow his career a little closer than I might have otherwise for another team's catcher.
Oooh shiny.
Former Cardinal Jason Marquis.
A Cub?! No matter the team, I appreciate a player who plays the game right and has fun doing it. For example, during a pitching appearance in a blowout during his time in Arizona, he imitated Mike Fetters' idiosyncrasies.
[Part 2]
Josh at Royals and Randoms had a draft-style contest called Big Pile way back in late 2011, and I misplaced the envelope until this week.
 |
| 1997 PowerDeck #11 Scott Rolen |
 |
| 1997 Upper Deck - Star Attractions #SA10 Kenny Lofton |
 |
| 1990 Fleer #461 Barry Bonds |
 |
| 1996 Fleer Ultra #533 Jason Kendall |
 |
| 2006 Bowman Chrome - Prospects #BC109 Leonard Davis |
 |
| 1997 Bowman #401 Jason Marquis |
 |
| 1993 Studio #42 Mark Grace |
2012-05-23
Big Pile, part 2
[Part 1]
Josh at Royals and Randoms had a draft-style contest called Big Pile way back in late 2011, and I misplaced the envelope until this week.
Pedro was finishing his career in MLB when I first started paying attention to baseball in 1992, but I still remember him as being quite a power hitter.
This is what checklist cards should be, with a nice full color photo of a player on the front. Also, this is an Ozzie that would evade my searches of internet checklists, as it's listed as a Cardinals Checklist only.
I think I might have been missing this one when I picked it, but I've since acquired another copy for my Heritage set, so this one goes in the duplicates.
I really like these Turkey Red cards, even though the first time I saw them was in the 2010 Update set as inserts. I'll probably put these sets on my wantlist eventually. I also had to pick the J.D. Drew card as a former Cardinal, so I figured I might as well grab the rest of the available cards from the set as well.
Josh at Royals and Randoms had a draft-style contest called Big Pile way back in late 2011, and I misplaced the envelope until this week.
 |
| 1991 Classic Game #21 Pedro Guerrero |
 |
| 1996 Collector's Choice #404 St. Louis Cardinals Checklist |
 |
| 2011 Heritage #304 Brett Myers |
 |
| 2005 Turkey Red #238 David Dellucci |
 |
| 2005 Turkey Red #235 Scott Podsednik |
 |
| 2005 Turkey Red #234 Mike Lowell |
 |
| 2005 Turkey Red #159 J.D. Drew |
 |
| 2005 Turkey Red #82 Ramon Ortiz |
 |
| 2005 Turkey Red #31 Nick Johnson |
2012-05-22
Big Pile, part 1
Have you ever set a bubble mailer aside and totally lost track of it, then found it months later? That's what I did with the Big Pile contest at Royals and Randoms. Based on his blog posting about when he sent it out, and being extremely conservative with postal delivery times, I'll say I've had these for a full 4 months. Oops.
Well, I figure I'm better late than never in posting the cards and sending him a big thanks, so here's part 1.
I don't remember Andy Van Slyke as a Cardinal, but he does to the Fox Sports Midwest studio commentary for the Cardinals now. Of course, his son just helped the Dodgers finish off a sweep of us the other night with a late-inning pinch hit HR.
Oooh, shiny.
At first I thought this was a Fleer Tradition card, but the back is numbered 8 of 12 and has a subtle Twizzlers logo.
I'm no Alex Gordon fan per se, I just happen to really like both Turkey Red and Goudey.
Former Cardinal John Smoltz, I don't care if it was only 7 appearances, that's what he'll always be to me.
Well, I figure I'm better late than never in posting the cards and sending him a big thanks, so here's part 1.
 |
| 1992 Pinnacle #9 Andy Van Slyke |
 |
| 2005 Topps Chrome #16 Chad Tracy |
 |
| 2000 Fleer Twizzlers #8 Sammy Sosa |
 |
| 2010 Allen and Ginter #235 Carlos Guillen |
 |
| 2009 Goudy #85 Alex Gordon |
 |
| 2007 Turkey Red #29 Alex Gordon |
 |
| 1990 Topps Mini League Leaders #56 Mike Scott |
 |
| 1990 Topps Mini League Leaders #47 John Smoltz |
2012-05-20
eBay Wins #28
There's just one card in this post, but I think it's a great one.
An old Ozzie Diamond King for just 20 cents, I couldn't pass up that deal. I think I'm in somewhat of a minority in that I like cards of any player who has even been a Cardinal, even if that card doesn't picture them as a Cardinal. Although, I haven't exactly gone out of my way to find any Angels Pujols cards, so maybe there's a line drawn between the pre-Cardinal teams and the post-Cardinal teams.
A little about this tracker: My goal is not simply to get the most cards possible, or the cheapest cards possible, but cards that I like. However, I find statistics interesting, so I'm just keeping score.
 |
| 1982 Donruss #21 Ozzie Smith |
| eBay Bargain Tracker | |
| Total Cards Bought | 1897 |
| Total Spent | $36.40 |
| Per Card | 1.919 cents |
2012-05-18
2010 Upper Deck Value Pack
When taking another look through Target's $1.59 pack box, where I found my last 3 2006 Topps packs, I found a 2010 Upper Deck. Since I won some 2010 UD not once but twice from Number 5 Type Collection, I decided I'd go ahead and pick up the pack. Here's what I found.
I mostly remember Weaver for kicking a batted ball while pitching in the World Series, because the following Sunday I pulled almost the same move (on accident) while pitching in slow pitch softball.
Buehrle grew up in the St. Louis area, and long talked about finishing up with the Cardinals, but that seems unlikely after he signed his contract with Miami this year. My dad actually worked with his uncle for awhile, and so I'd get to hear about his progress through the minors, even in the days before obsessive team bloggers and 3 or 4 ESPNs to cover every detail.
And here are all the base cards contained in the pack.
34 Matt Garza
97 Jed Lowrie
126 Carlos Quentin
144 Laynce Nix
146 Joey Votto
167 Kerry Wood
232 Wesley Wright
282 Jeff Weaver
358 Rajai Davis
393 Ramon Vazquez
408 Tony Gwynn (Jr.)
410 Edgar Gonzalez
454 Felix Hernandez
479 Gabe Gross
537 Ross Detwiler
594 San Francisco Checklist
18 cards for $1.59 wasn't bad, even if almost every pitcher is shot like Weaver above, to obscure the logos. Although, I'm surprised Upper Deck got away with as much as they did being unlicensed in 2010, like the SOX and SF logos on Buehrle's and Lincecum's hats.
 |
| 2010 Upper Deck #282 Jeff Weaver |
 |
| 2010 Upper Deck - Season Biography #SB-96 Tim Lincecum |
 |
| 2010 Upper Deck - Supreme Green #S-11 Mark Buehrle |
And here are all the base cards contained in the pack.
34 Matt Garza
97 Jed Lowrie
126 Carlos Quentin
144 Laynce Nix
146 Joey Votto
167 Kerry Wood
232 Wesley Wright
282 Jeff Weaver
358 Rajai Davis
393 Ramon Vazquez
408 Tony Gwynn (Jr.)
410 Edgar Gonzalez
454 Felix Hernandez
479 Gabe Gross
537 Ross Detwiler
594 San Francisco Checklist
18 cards for $1.59 wasn't bad, even if almost every pitcher is shot like Weaver above, to obscure the logos. Although, I'm surprised Upper Deck got away with as much as they did being unlicensed in 2010, like the SOX and SF logos on Buehrle's and Lincecum's hats.
2012-05-17
A Vintage Contest at ARPSmith's
There's a contest going on over at the relatively new ARPSmith's Sportscard Obession blog. Of course, I'm getting a bonus entry by linking you to it, and you can too. Here's my favorite prize of the bunch:
Hopefully I'll add that Cardinals patch to my collection. Go enter, and good luck.
Hopefully I'll add that Cardinals patch to my collection. Go enter, and good luck.
2012-05-16
2012 Google Code Jam, Round 1A
In the next round of the Google Code Jam this year, 3686 people scored at least some points. Only the top 1000 would advance, though, which took at least 53/100 points and a fast enough time.
I first attacked Problem B. Kingdom Rush. It has a long explanation you can see at the link, but here's a short summary:
One sample input is:
0 2
0 1
meaning that there are 2 levels, and the first level has a pre-req of 0 for 1 star, and 2 for 2 stars. One example run could be finishing level 2 with 1 star (now you have 1 star), then finishing level 2 with with 2 stars (now you have 2 stars), then finishing level 1 with 2 stars in one single run because the pre-req is only 2 stars, for a total of 3 runs.
An impossible input would be
1 1
1 1
1 1
because, starting with 0 stars, there's no way to finish any level first.
Also impossible would be
0 0
0 0
0 6
because you couldn't get 6 stars before attempting 2 stars on the last level.
My first approach was to try to finish the first possible 2-star level, and if one wasn't reachable with the current level of stars, try the first possible 1 star level. This solved the test data, but my submissions for the small input kept getting rejected, so I knew there must be an additional trick. I tried to come up with solutions that broke my algorithm, and discovered one.
0 1
0 3
With this input, first I'd try all the 2-star values, and fail. Then I'd take the first 1-star value, leaving:
0 1
0 3
The next run would take the first possible 2-star value, at 1.
0 1
0 3
Next, the 2 star search would fail again, and it would take the next 0.
0 1
0 3
Then the 3, for a total of 4 runs.
0 1
0 3
But, I can see a faster way. First, take the last 0
0 1
0 3
Now that I have 1 star, I can complete the first level all at once
0 1
0 3
And with 3 stars, I can complete the second level, for a total of 3 runs
0 1
0 3
Adding the run for the final level lets this one get finished in 3 runs instead of the previous 4. So the flaw in the algorithm was in taking the first available 1-star, when instead I needed to take the 1-star associated with the highest possible 2-star value, in order to leave the others available to possibly finish both stars in one single run. I fixed my algorithm and submitted the small input, which was then correct. I submitted the large input and had to wait until the end to find out it if it was right, which it was.
Next, I attempted Problem A. Password Problem. Again, it has a long explanation, I'll try to boil down to some bullet points.
The object is to choose the strategy to minimize the expected number of keystrokes.
Side note: I don't usually like expected value that much.
Here was the contest example:
Suppose my password is "guest" and I have already typed the first two characters, but I had a 40% chance of making a mistake when typing each of them. Then there are four cases:
I don't know how many mistakes I actually made, but for any strategy, I can calculate the expected number of keys required to use it. This is shown in the table below:
My first thought here was that I would need to calculate the 2^A possibilities, so if I got character 1 right or wrong, combined with if I got character 2 right or wrong, etc. Since A could be up to 99999 in the problem statement, I knew that wouldn't be feasible. Then I realized it only mattered what the odds were of typing the first x characters correct, and anything after the first wrong character didn't effect the answer to the problem. that is why the columns under "Xu" and "XX" look the same
I treated the "keep typing" case as pressing backspace 0 times, so that it fit more nicely in my code. Now there were only 2 cases to check. Pressing enter right away was easy, the answer was always the same, so the expected value was always B+2, for the first enter, the B characters of the password, and the final enter.
Since the probability could be different for each letter, I stored them in a vector with the intent to multiply the ones I needed. Then I realized that what I really needed was the cumulative probability of getting all letters right up to any given letter, so I stored the values as
Now I could figure out the answer in linear time. Letting the number of backspaces be C, and looping over C from 0 to A, the expected value with C backspaces was the product of all of the probabilities of typing characters 0 to A-C correct, times 2C+B-A+1 (C backspaces, C replacement characters, the rest of the password, plus the enter key), plus 1 minus that product times 2C+2B-A+2 ( The 2C+B-A+1 from before, plus another B characters when it is rejected, and the final enter).
So the answer to each case, given A, B, and the vector of p's is:
(I really need to get LaTeX working for Blogger to write fancier equations.)
I thought I had cleverly solved this one, and submitted the small input. Unfortunately, the large was wrong because I had not planned on reading in 900,000 characters from the input file on a single line, and some code I wrote several years ago broke. This is because each case was input as:
A B
p1 p2 p3 ... pA
Where px is the probability of getting character x correct. The probabilities were in the form x.xxxxxx, so a total of 9 characters each including numbers, decimal point, and space. With A up to 99999, there were nearly 900k characters on one of the lines.
So the takeaway from this round was to fix my input reader. I finished with 43 points, placing at #1463.
On to Round 1B!
I first attacked Problem B. Kingdom Rush. It has a long explanation you can see at the link, but here's a short summary:
- There are N levels to finish
- Each level can be completed with a 1 star or 2 star rating; if it is previously completed with 1 star, completing it with 2 stars only earns one additional star, and completing it with 1 star is meaningless. Thus, the maximum possible stars to earn is 2N
- There is a prerequisite number of stars to get a 1 star rating on a level, and a greater or equal prerequisite to finish the level with 2 stars.
One sample input is:
0 2
0 1
meaning that there are 2 levels, and the first level has a pre-req of 0 for 1 star, and 2 for 2 stars. One example run could be finishing level 2 with 1 star (now you have 1 star), then finishing level 2 with with 2 stars (now you have 2 stars), then finishing level 1 with 2 stars in one single run because the pre-req is only 2 stars, for a total of 3 runs.
An impossible input would be
1 1
1 1
1 1
because, starting with 0 stars, there's no way to finish any level first.
Also impossible would be
0 0
0 0
0 6
because you couldn't get 6 stars before attempting 2 stars on the last level.
My first approach was to try to finish the first possible 2-star level, and if one wasn't reachable with the current level of stars, try the first possible 1 star level. This solved the test data, but my submissions for the small input kept getting rejected, so I knew there must be an additional trick. I tried to come up with solutions that broke my algorithm, and discovered one.
0 1
0 3
With this input, first I'd try all the 2-star values, and fail. Then I'd take the first 1-star value, leaving:
0 1
0 3
The next run would take the first possible 2-star value, at 1.
0 1
0 3
Next, the 2 star search would fail again, and it would take the next 0.
0 1
0 3
Then the 3, for a total of 4 runs.
0 1
0 3
But, I can see a faster way. First, take the last 0
0 1
0 3
Now that I have 1 star, I can complete the first level all at once
0 1
0 3
And with 3 stars, I can complete the second level, for a total of 3 runs
0 1
0 3
Adding the run for the final level lets this one get finished in 3 runs instead of the previous 4. So the flaw in the algorithm was in taking the first available 1-star, when instead I needed to take the 1-star associated with the highest possible 2-star value, in order to leave the others available to possibly finish both stars in one single run. I fixed my algorithm and submitted the small input, which was then correct. I submitted the large input and had to wait until the end to find out it if it was right, which it was.
Next, I attempted Problem A. Password Problem. Again, it has a long explanation, I'll try to boil down to some bullet points.
- I have already typed A characters of my password, which is B characters wrong.
- The chances I typed each of the A previous characters correctly are given
- All future characters will be typed correctly
- My choices are
- keep typing
- backspace 1 to A characters and continue typing
- hit enter and start over.
The object is to choose the strategy to minimize the expected number of keystrokes.
Side note: I don't usually like expected value that much.
Here was the contest example:
Suppose my password is "guest" and I have already typed the first two characters, but I had a 40% chance of making a mistake when typing each of them. Then there are four cases:
- I typed "gu" without error. This occurs with probability 0.6 * 0.6 = 0.36.
- I typed the 'g' correctly but I made a mistake typing the 'u'. Then I have two letters typed still, but the second one is wrong: "gX". (Here, the 'X' character represents a mistyped letter.) This occurs with probability 0.6 * 0.4 = 0.24.
- I typed the 'u' correctly but I made a mistake typing the 'g': "Xu". This occurs with probability 0.4 * 0.6 = 0.24.
- I made a mistake typing both letters, so I have two incorrect letters: "XX". This occurs with probability 0.4 * 0.4 = 0.16.
I don't know how many mistakes I actually made, but for any strategy, I can calculate the expected number of keys required to use it. This is shown in the table below:
"gu" "gX" "Xu" "XX" Expected
Probability 0.36 0.24 0.24 0.16 -
Keystrokes if I keep typing 4 10 10 10 7.84
Keystrokes if I press backspace once 6 6 12 12 8.4
Keystrokes if I press backspace twice 8 8 8 8 8
Keystrokes if I press enter right away 7 7 7 7 7
My first thought here was that I would need to calculate the 2^A possibilities, so if I got character 1 right or wrong, combined with if I got character 2 right or wrong, etc. Since A could be up to 99999 in the problem statement, I knew that wouldn't be feasible. Then I realized it only mattered what the odds were of typing the first x characters correct, and anything after the first wrong character didn't effect the answer to the problem. that is why the columns under "Xu" and "XX" look the same
I treated the "keep typing" case as pressing backspace 0 times, so that it fit more nicely in my code. Now there were only 2 cases to check. Pressing enter right away was easy, the answer was always the same, so the expected value was always B+2, for the first enter, the B characters of the password, and the final enter.
Since the probability could be different for each letter, I stored them in a vector with the intent to multiply the ones I needed. Then I realized that what I really needed was the cumulative probability of getting all letters right up to any given letter, so I stored the values as
p1, p1*p2, p1*p2*p3,...
resulting in a new vector
P(0), P(1), P(2), P(3)...
Now I could figure out the answer in linear time. Letting the number of backspaces be C, and looping over C from 0 to A, the expected value with C backspaces was the product of all of the probabilities of typing characters 0 to A-C correct, times 2C+B-A+1 (C backspaces, C replacement characters, the rest of the password, plus the enter key), plus 1 minus that product times 2C+2B-A+2 ( The 2C+B-A+1 from before, plus another B characters when it is rejected, and the final enter).
So the answer to each case, given A, B, and the vector of p's is:
min(B+2,P(A-C)(2C+B-A+1),(1-P(A-C))(2C+2B-A+2))
for all C 0 to A
I thought I had cleverly solved this one, and submitted the small input. Unfortunately, the large was wrong because I had not planned on reading in 900,000 characters from the input file on a single line, and some code I wrote several years ago broke. This is because each case was input as:
A B
p1 p2 p3 ... pA
Where px is the probability of getting character x correct. The probabilities were in the form x.xxxxxx, so a total of 9 characters each including numbers, decimal point, and space. With A up to 99999, there were nearly 900k characters on one of the lines.
So the takeaway from this round was to fix my input reader. I finished with 43 points, placing at #1463.
On to Round 1B!
2012-05-15
eBay Wins #27
My next eBay purchase came in the form of 6 cards over 3 auctions from the same seller, all for 2011 Lineage cards.
Auction 1: Willie McCovey - 2 base cards for $0.25
Auction 2: Zach Britton - Base card and Rookie insert card for $0.35
Auction 3: Mel Ott - Base card and 1975 Mini parallel for $0.36
Overall, under a buck for 4 base cards and 2 inserts isn't bad. I'm hoping to complete this set soon along with the small insert sets, and the 75 mini set eventually.
Auction 1: Willie McCovey - 2 base cards for $0.25
 |
| 2011 Topps Lineage #192 Willie McCovey |
 |
| 2011 Topps Lineage #57 Willie McCovey |
 |
| 2011 Topps Lineage #61 Zach Britton |
 |
| 2011 Topps Lineage - Topps Rookies #10 Zach Britton |
 |
| 2011 Topps Lineage #186 Mel Ott |
 |
| 2011 Topps Lineage - 1975 Mini #186 Mel Ott |
| eBay Bargain Tracker | |
| Total Cards Bought | 1896 |
| Total Spent | 36.2 |
| Per Card | 1.909 cents |
2012-05-10
2006 Topps Value Pack #3
[Pack 1]
[Pack 2]
Oddly enough, on another trip to Kansas City, I found yet another 2006 Topps pack at Target in the $1.59 bin. Here's the good stuff:
Wait a minute, this looks familiar.
So does this one.
There we go, one that wasn't in that last pack. I was starting to worry.
This is a decent looking card, but it appears all of them in the set look the same on the front except the number in the upper left.
When I saw this I thought maybe there wasn't an Opening Day set for 2006, but there is.
Here is the full base card listing:
344 Doug Davis
354 Grady Sizemore
356 Luis Matos
363 Jermaine Dye
429 Francisco Cordero
432 Brett Myers
436 Keith Foulke
449 Jason LaRue
452 Jake Westbrook
454 Bobby Jenks
461 Placido Polanco
469 Josh Willingham
569 Mike Jacobs
580 Frank Thomas
610 Cincinnati Reds
651 Jose Reyes/Kaz Matsui
Series 2 Checklist 2 of 3
I really wonder how much longer I'll keep finding single packs of the product at Target. I like what I've been getting, so I'll keep picking them up.
[Pack 2]
Oddly enough, on another trip to Kansas City, I found yet another 2006 Topps pack at Target in the $1.59 bin. Here's the good stuff:
 |
| 2006 Topps #461 Placido Polanco |
 |
| 2006 Topps #452 Jake Westbrook |
 |
| 2006 Topps #449 Jason LaRue |
 |
| 2006 Topps - Mantle Homerun History #MHR2 |
 |
| 2006 Topps - Opening Day Team vs Team #OD-BP Brewers vs Pirates |
If you recall, these packs had 3 Vintage cards in them, so far all from 1985-90 for me
I've got the 1989 set, so this will go in the trade list.
1986 is just old enough to not be part of the overproduction era, I think. At least, I don't have a ton of these sitting around.
There we go, a Hall-of-Famer. I'm glad to see one guy I recognize among the 80s cards.
 |
| 1989 Topps #253 Jose Alvarez |
 |
| 1986 Topps #266 Keith Moreland |
 |
| 1986 Topps #205 Tony Perez |
Here is the full base card listing:
344 Doug Davis
354 Grady Sizemore
356 Luis Matos
363 Jermaine Dye
429 Francisco Cordero
432 Brett Myers
436 Keith Foulke
449 Jason LaRue
452 Jake Westbrook
454 Bobby Jenks
461 Placido Polanco
469 Josh Willingham
569 Mike Jacobs
580 Frank Thomas
610 Cincinnati Reds
651 Jose Reyes/Kaz Matsui
Series 2 Checklist 2 of 3
I really wonder how much longer I'll keep finding single packs of the product at Target. I like what I've been getting, so I'll keep picking them up.
Subscribe to:
Posts (Atom)