metfan4vr's Journal

ACM GNY Regional
The practice I've endured through (ok enjoyed) for the past 3 or so months came to culmination earlier today, and we were so close to success that I feel bad for only finding out about this entire world of competitive algorithmic programming so late into my academic career. Being I'm still on a high about how well I did at the start, I shall toot my own horn for a bit before exposing some gory details about how things could have gone differently. I had the first submission of any team in the entire contest at 9 minutes in, and yes, it was correct. This should have easily been a 5-6 minute submission, however having to create my own template file for the remainder of the match, I had mistakenly been writing the program to this template file, yet attempting to compile what I thought I was writing in. After much searching with help from both teammates, I had seen the careless mistake and thankfully the program ran as expected and it was rushed to submission. The secret to solving a problem in 5 minutes that has an introduction that can easily take 3+ minutes to read? Just skip the entire problem statement, look at the picture and input/output and go on pure faith (ok I had to glance back for specific details such as the radius of each ring of the bullseye, but it was a fairly safe guess as to what the program was supposed to do).

While I was finishing this up, my teammate Joe had figured out how to do the second problem so I begin looking through the problem set again, and I did not have to look far to find the next problem to attempt for it was problem C. This was an extremely simple DP problem, and with Joe needing a few minutes to get some cases straight made the excellent team decision to give the computer up while reviewing his printout of the code he had written. I wrote the solution quite quickly for the recursive part is very nice and compact if you do it right, however due to what I will refer to as, Halo 'til 2AM the night before and a bad case of the shits giving myself a whole 1.96 hours of sleep, I made a few careless mistakes such as the initial run case which cost us a few precious minutes. While looking for these mistakes I had given the CPU back to Joe who immediately finished the second problem and submitted(later deemed correct as well) and we were once again the first place team (not that any problems were being judged nor were the standings working at the moment). I saw my careless errors and fixed the program to another wonderfully working algorithm, but I did not test the large case where the result would be extremely large, specifically meaning it might not fit into the integer which I was forcing it into. The solution was incorrect for the exact reason, but because no submissions were being judged until over an hour into the contest, I had not known of the outcome for another 40 minutes. When finally receiving the result, I cursed myself and quickly made the necessary changes and a quick resubmission. Despite that delay we were still the second team to get the problem correct at 86 minutes. Though it was not marked as correct initially, the judges output data was wrong and it was telling everyone they had the wrong answer, so I actually spent another 15 minutes looking at my printout and another 5 on the computer testing cases before concluding that my program was in fact correct. At about the 3 hour mark the judges had recognized this, got the correct data, and re-checked all the submitted files.

Sadly, this is where my run ends, for I have turned into an extremely fast and accurate coder on trivial problems and easy DP problems which I have the pleasure of seeing. We had a few ideas for other programs, but due to tricky wording and not being sure on how many moves our algorithm made, we held off on solving a problem that was actually extremely simple, though we did get it on our first submission at the 255 minute mark.

The story not told is that one member of the team, who can actually solve a problem or two, writes very very shitty code. Meaning he has gargantuan amounts of compile errors and although his algorithm may very well work fine, he has some inabilty to code it bug-free. It's quite amazing actually. He'll sit there debugging this huge pile of steaming shit because instead of converting a card to its value, he keeps the string it was inputted as (playing card such as say 8H for the eight of hearts), and throws each ugly string hundreds of times into some sort of compare function. And given three cards, instead of ranking them and finding which order they are in, he has all 6 possible ways in one huge nested if-else block that has 2 arguments to each, which was only one of his hard to keep straight bugs that apparently wasn't the only god damn problem when I pointed out how wrong it was. On this one card problem, which is nothing more than basic simulation he had managed to sit in front of the screen debugging for an entire 150 minutes. Had there been two computers I would have solved this problem in parallel to him without his knowing and all would have been well.

The last problem in the set was obviously another DP problem that could be coded in approximately 15 lines (I did it after the event in 9 lines not including i/o and initialization functions), but I couldn't grasp exactly how to do it. Ben, the coach, had told me how to do it while trying to figure out which train would bring us to Penn Station and I was upset at how close I got, but not really too disappointed because this was quite a different way to break down a problem than I have seen in the past, and I'm not really an innovative person. I can bang my head on the wall as well as the next guy and figure something out, but a half hour wasn't going to be enough time, however I do have a pretty good memory apparently and I now have another little trick in my arsenal.

All in all the competition was great fun. It was totally amazing to compete against 60ish other teams from the NY/NJ area and come in 8th overall. Rutgers is well known for its shitty undergraduate CS program, almost nothing that is taught is actually useful for this type of problem solving, and when I say this type, I mean the very heart of Computer Science. It really is quite sad that we have exactly 1 algorithms course and it is rooted in essentially trivial algorithms such as shortest-path and minimum spanning trees, some sorting and basic proofs of the lower bounds to the big-Oh of any algorithm made give an answer to common questions(like sorting...). I'm extremely proud of the other two teams which came in 2nd place overall (and have "an excellent chance" of going to the World Finals in Shanghai, China...fucking China, this is big shit) and 16th. Rutgers, in my unofficial but scientifically acceptable opinion, was statistically the best school at the competition. Our top two teams(2nd and 8th) beat any pair of top two teams from any other school including last years champion Cornell(7th and 20th), Columbia(3rd and 22nd), Stony Brook(6th and 9th) and Stevens(4th and 23rd) of the notable mentions. Also despite Stony Brooks 3rd place team finishing higher than our 3rd (their 14th to our 16th) the total sum of the ranks puts us at a lower score, which in golf terms means we're also better on the top 3 teams between us. NYU wound up taking first place overall, a huge congratulations for them catching 2 problems in the last hour where all results were hidden from competitors (oh and their second place team was 12th). This was only Rutgers second year in the competition, and from what I know, last year there was no real coach, just 3 guys who wanted to give it a go. I'm totally fucking proud of what we did, we made a huge impact in the Greater New York Region, and although it seems many of the seniors will move onto graduate school or real jobs elsewhere, we have 2 incredibly strong candidates for upcoming years including one fucking amazing freshman named Adam who learned graphs and dfs'ing in a single day and correctly coded a program a senior on our 2nd place team could not. Also Siwei (a junior I believe, certainly not a senior) is an extremely promising candidate for computational geometry problems along with math and general ad hoc problems. Though a disappointing note is I'm not sure if these two are going to start practicing some more for next years contest than they did for this years.

The biggest reason for our success was our coaches Ben and Bin. Bin did all the bitch-work like getting us registered and getting people to the contest and judging our practice contests every week while Ben was the solution machine. He could solve almost any problem we ran across. He's one fucking amazing guy and without his ability to answer all the questions we came to him with, we never would have got to where we were (well maybe Chris and team 1 might have...though I'm not sure if Ben and the practice was the reason he warmed up to the beautiful simple solutions given by recursion, or he just took his head out of his ass!) Ben and Bin put some serious hours working with us and I like to think we made them proud. We may have had 2 all senior teams, but for 5 of us it was our first time doing the contest, and all 5 had been practicing since about July at the earliest. Had we been training since freshman year, I wouldn't have been surprised at all if both of our teams came in 1,2 with 7 out of 9 problems.

As far as upcoming years, it seems as if Ben is going to get his PhD and rightfully get on with his life outside of Rutgers. Bin I'm unsure about but I certainly would love to help coach and keep our students motivated. It would be a learning process for everybody, but eventually I like to think with enough work I could at least figure out most of the problems within a day or two on my own, and I'm sure Ben wouldn't ignore an email for a little help here and there.

As this post is coming to a close, I'd like to say that at the start, I was rather intimidated by the competition. As schools were rolling in, one school seemed to attract more attention than any other. When Stony Brook entered with their 3-4 teams or so, other people in the ACM hierarchy that overlook the competition had said, and here they are, the Stony Brook team, and had immediately made their way to the coaches and shook each of their hands. Stony Brook is a school I heard a lot about recently and even just yesterday I had went to their website and looked at the courses offered in their CS department. The list was astounding, offering approximately 50 level 300 classes. One of the teachers at Stony Brook, Steven Skiena, even wrote Programming Challenges specifically for a class that is in all respects aimed teaching how to excel in these exact sort of programming competitions. This book was actually outlawed last year on books that were allowed into the testing area, however this year it was not(we had a copy, but did not even think to look at it, and it was most likely not even useful for this anyways). In fact I do plan on receiving my own copy by the New Year. In any event, Stony Brook apparently has earned much respect in this whole aspect of competitive programming, and I think it's fair to say that our out-of-nowhere attack on this event has shown that Rutgers is in fact, if not a quality school, has a few students that are of the highest quality and probably deserve better. In any case though, hopefully next year, if we can put together a determined group, we will be the ones everybody is talking about...were we a bunch of fluke ringers that learned about this wonderful contest too late in our years, or has Rutgers given rise to a new elite class of super-programmers that will only get better and perhaps compete consistently at the World Class level. Today might be remembered as the day that gave rise to Rutgers being respectable not only in CS faculty, but in raw CS and all around problem-solving undergraduate talent.

Oh yea forgot to mention, I single handedly beat all of Yale university, TCNJ and Columbia/Cornell Team 2.

Advertisement