Where Has The Time Gone?
qubits Became TopCoder's First $100,000 Champion One Year Ago This Week

Wednesday, June 5, 2002
By Adam Loss,TopCoder Staff Writer

Powerball, "It's America's Game", and it's extremely popular. And to think of it, why wouldn't it be? Powerball is a lotto game, which is a combined large jackpot game and a cash game. Twice a week, drawings are held where participants must match five balls, plus the "red powerball" to balls that are randomly chosen, to win a jackpot which has many times exceeded $50 million. It only costs one dollar to play, so it's worth a shot, but the odds to win the jackpot are 1:80,089,128. Hardly a sure thing. Playing the lottery is more of a matter of luck rather than skill, although the people who constantly play the numbers of their birthday or their kids age's will tell you differently.

TopCoder, although not as widely known as Powerball, is becoming pretty popular itself, averaging close to 60 new members per day, and has also been known to pay out a pretty penny to its members. qubits was TopCoder's first big winner, rewarded with $100,000 for winning the 2001 TopCoder Collegiate Challenge. Although TopCoder's $100,000 grand prize is nowhere near a reward of $50 million from Powerball, qubits decided the odds of TopCoder were more in his favor, as he could use his skills, rather than rely on luck, to earn a big payday.

Educated and trained at MIT and armed with a Bachelors Degree in Computer Science and Mathematics and a Masters Degree in Engineering, qubits "knew that TopCoder was not yet widely known (when he joined in March 2001), and that the upcoming Collegiate Challenge would not draw the audience that it could (and later events have). As a result, I thought I might have decent odds at making it to the semifinals."

qubits was right. The odds to make the semifinals of the 2001 TopCoder Collegiate Challenge, where competitors were guaranteed to win $3,000, were 16:256 or 1:16. The worst odds in Powerball, just matching the "red powerball" are 1:74 and pay a miniscule $3. The odds to win $100,000 in Powerball (matching five balls) are 1:1,953,393, whereas the odds at winning the $100,000 grand prize at the Collegiate Challenge was 1:256. In Powerball, odds of 1:256 pay out $7.

Luck might pay a buck, but skills pay the bills.

1,2,3,4...A,B,C,C++?

Although stubborn and independent, four-year-old children have an uncanny desire to learn and explore. Parents know to never answer a question with a non-definitive word such as "because", as they are more than likely going to receive the extremely annoying "Why, Why, Why?!?!" until a direct answer is given.

qubits started to program at age four. "My father got me off to a good start." Like most children his age, qubits had queries, and of course asked why, but "he (his father) could answer most questions I had at a young age."

qubits father did such a good job at answering his questions, in fact, that "he convinced my mother that I had an aptitude for computers which should be encouraged At four, I wrote something along the lines of 'Hello, World'. I think I referred to a BASIC manual to see how to do certain things, and it undoubtedly started with a program like that. I would sometimes type the source code (BASIC) of games into a TI99/4A. On occasion, I would try to figure out what the program actually did and would use what I learned to write simple programs."

qubits desire to learn and explore then became more personal as, "soon after I drove myself, using computers to solve interesting problems I came across while growing programming related skills.

I have always liked CS/programming, but it is somewhat focused. My primary focus has been solving problems and I see computers as a tool to that end. Programming remained a hobby from my elementary years up through high school, while my primary focus was on mathematics and the physical sciences."

With that kind of background and youthful agenda, an education from MIT was naturally followed by a career in computer industry. "My primary focus is on solving interesting problems. I would flat out refuse most jobs that fall under the classification of 'programmer'. However, programming is a great tool for most problems, so I decided to specialize there."

A TopCoder First

qubits was introduced to a TopCoder, a place where he could sharpen those programming skills, weeks before the start of the 2001 TopCoder Collegiate Challenge.

"My bridge partner and friend told me about the site. He was a classmate at MIT and is now pursuing his PhD in Computer Science at Stanford. It (TopCoder) looked fun and I thought I might be able to get a slice of the $250,000 Collegiate Challenge prize purse."

After getting through the first three online elimination rounds, qubits was confident when he headed to San Francisco for the onsite finals.

"By the time the 16 semifinalists were known, my goal was to make it to the finals. Aleksey seemed to be the strongest competitor in my room, but his performance in SRM's leading up to the finals was far less strong than his qualifying rounds."

The following is qubits take on the semifinals, in his own words:

"Going with the strategy I decided on before the event, I opened the 500-point problem first, expecting to advance to the 1000-point problem if people seemed stuck on the 250-point problem, otherwise picking up the 250-point problem and ending with the 1000. Upon reading the 500-point problem, a dynamic programming solution immediately jumped out at me and led to a quick solution.

Seeing only one solution for the 250, I moved on to the 1000 (I think). I also saw a quick solution for this problem, and submitted it in twelve minutes. Seeing only two other submissions (both easy), I confidently attacked the 250-point problem and finished in just over 28 minutes total.

Upon walking off the competition platform in under 30 minutes, some of the other competitors were noticeably disturbed. I was feeling good and started to work on challenge test cases. My confidence improved further when I saw Aleksey skip the 500-point problem.

During the challenge phase, I quickly picked off all of the other easy submissions. I could taste victory as Aleksey challenged Orbus ' 500-point problem, leaving me over a 1000-point lead. That taste quickly turned bitter when I realized my 1000-point problem was flawed. My lead mentally collapsed to 200 points and I realized I would fail if I had another bug in my 500-point solution.

I waited intently for the results, hoping my solutions would stand. When it did, I was excited and relieved."

qubits confidence for the semifinals quickly faded when he got a look at the competition in the finals. "I didn't think I would have good odds in the finals, so I decided I'd just give it a shot for what it's worth if I made it."

A very intense qubits was able to drown out his nervousness on finals morning. "I remember bringing a couple bottles of water/juice with me to the terminal and had to ask for more during the competition. I don't ever remember ever needing to drink that much before."

qubits now takes us through the finals:

"Upon making it to the finals, I had done what I had set out to do and was actually quiet calm. I was a bit nervous upon reading the 500-point problem, however. Unlike the day before, I could not think of the dynamic programming approach. Not knowing what else to do, I brute forced it and found that it would execute in under six seconds in the worst case, so I submitted and moved on.

For the 1000-point problem, I encountered a severe compiler error that caused me to lose my calm demeanor minutes after regaining it. There was a syntax error that was reported in a nonsensical sense on another line. I remember calling Mike (admin) over, but there was nothing he could do. Eventually I discovered it and charged forward. Initially I thought of just keeping track of which vertices are traversed by the bounding path, but discovered that was not sufficient. After a bit more hacking I discovered it would be sufficient if I doubled the grid size. It took only a few minutes to implement the changes followed by some testing...submit.

The 250-point problem seemed like a complicated tangle of prioritized special cases. I tried to carefully get the cases right, but jonmac would eventually catch me on one I missed. I thought this would be a ripe area for challenges.

Thus, in the challenge phase I rushed to inspecting the easy problems, declining the chance to attack seacow 's last-minute 1000-point submission. However, like in the semifinals, I was able to defeat each of the other 250-point submissions, producing a 500-point swing (~200 + 3x100). I realized I might just have a chance, so I charged forward to increase my lead.

Then I noticed vulture was using the approach I abandoned on the hard problem. He tried to avoid the problem by omitting the last segment inspected. I didn't notice this, though, so had I challenged with something like "DRU", his code would have succeeded. However, a little voice inside me made the test case a bit wider (like "RRDLL"), forming a successful challenge.

When vulture exploited jonmac's corner-case in his 500-point solution and seacow's problems fell, things were looking pretty good. I tried to extend my lead by challenging jonmac's 1000-point solution, but failed. jonmac caught my 250-point bug and cheered with excitement, but I remained confident; after all, I had 300 points from challenges and his 500-point solution was down, giving me just over a 400-point lead.

The walls came crashing down when it was announced immediately after the challenge that I would lose two of my challenges on the 250-point problems. My 400-point lead vanished: 200 to lost challenge points and the another 200 or so to jonmac regaining credit for his 250-point solution. I panicked, realizing that only 206.76 points separated us and that jonmac could have scored that much on his 250-point problem (I had forgotten and the scores had not yet been updated). However, I was quickly reminded by my guests, who had been working through all the possible scenarios, that he received under 200 points: I had won."

qubits, now the inaugural TopCoder tournament champion, $100,000 richer, and arguably the top collegiate programmer in the country, almost needed someone to pinch him. "I almost didn't believe it at first." The media and spectator frenzy also caught qubits off guard. "I had a bunch of lights, cameras, and a microphone pointed at me...Wow!!!" When all of the attention died down for a bit, qubits finally got a chance to reflect on what had just taken place. "I was relieved. I had been looking forward to the semifinals for days, and then the finals. I could finally relax."

We've all heard of those stories about the person who took a tax-refund, invested it and is now a multi-millionaire. Unfortunately, we've also heard just as many, or more, stories of athletes and entertainers who've squandered the millions they've made with exurbanite expenditures.

qubits decided to take the approach of the former, and although he isn't a millionaire yet, his winnings have exhibited considerable growth over the year. "Eventually I hope to buy a house once I decide for sure where I want to live long-term."

Compete. Win. Repeat.

In the world of competition, winning successive major events is very difficult. Whereas in team events, the group as a whole can offset a poor performance by one member, individual events such as TopCoder major tournaments don't provide such a luxury. Many times sub-par displays are the result of pressure, which is exactly what qubits felt during the semifinals of the 2001 TopCoder Invitational, the next major tournament.

"I was nervous and rattled, the complete opposite of the Collegiate Challenge. Lately, I've been wondering if this is a curse of previous success. I barely made it through the online qualification rounds, bombing in the semifinals. If I was presented the set during an ordinary online match, I'm sure I would have done much better. I choked."

Though disappointed, qubits didn't let it affect him too much. "I had my moment in the spotlight, and not doing well in the Invitational wouldn't change that."

Professional Life

The rules change and your responsibilities increase when you leave school and enter the real world. The professional engagements in the life of qubits, who is currently a Senior Research and Design Engineer in California, have led to him competing in only two of the last 21 matches. Don't expect to see him quietly vanish from the TopCoder hierarchy and become another 'whatever happened to him?' case, however. qubits is still motivated to do well and has a sincere love of coding. "Competing is fun. Competition scares some people, but I think the more interaction there is, the better. I like working through the various types of problems that are used, and have a love of problem solving in general. I'll definitely compete more as the Invitational approaches."

qubits goals for competing in TopCoder competitions from when he was a student are now somewhat different. "While I was a student, match awards were great because I wasn't making a lot of money while at school. The problems were fun, but time was limited as I was cramming for the final leg of writing my thesis. Now the money is less important, but I have more time for competing."

Advice

Advice from your TopCoder peers is usually something to value. They are people who are just like you, and may be the best at understanding your needs, wants and concerns, so most likely listening and learning from them would be of tremendous benefit. Advice from qubits, however, is definitely something to value. Think about it. qubits is a TopCoder original, a two-time tournament semifinalist, and a $100,000 champion. He joined TopCoder when there were only 205 members, Single Round Matches had yet to start, and TopCoder was a virtual unknown in the developer community. TopCoder has now attracted well over 16,000 members, has run 94 Single Round Matches, held three major tournaments, paid out millions of dollars in prizes, and attracted major technology companies as sponsors. According to qubits, there is no need to worry about competing:

"Many people seem scared of competing, but they don't realize that most of the other people just starting out feel the same way. Even then, there's nothing to be really afraid of. No one knows who you are, and you'll compete against coders of similar ability. As you improve, so will your competition, at your own pace. Just do it!"

Future

It would be nice if we all had a Delorian, and once we hit 88 mph be sent into the future to see how our lives have unfolded. Well, since that's just a movie fantasy, and we have no idea of what the future holds, we must wish and hope. Personally, qubits hopes "to make it back into the top-10," and would "eventually like to solve an important problem facing society or design something to fill a need, although it's not clear what that problem or need is, though." As far as TopCoder goes, he would like to see more medium sized tournaments, perhaps encompassing a weekend, added to the TopCoder competition structure, and a "report card" added to the member profile, "which highlights areas of weakness and strengths as a coder and plots improvement.

Along with the increased quantity of coders who have helped TopCoder increase from the 205 members when qubits joined, to the current level of over 16,000, the quality of coders has also sky-rocketed. The battle during the next TopCoder tournament will produce the most competitive competition ever, making the odds of qubits becoming TopCoder's first multiple tournament champion extremely difficult. It's a good bet that he will be among the final sixteen, however, since he's two-for-two in that respect.

Would you like to write a weekly feature?