ICPC Regionals

Today I competed in the International Collegiate Programming Contest (ICPC) Rocky Mountain Regionals at Colorado State University (CSU).

ICPC is the International Collegiate Programming Contest. It’s an algorithmic competition for college students. I’ve competed in ICPC three times now, but today was the best my team has ever done. But I’m getting ahead of myself. Some background on what we did.

It all started Friday afternoon. I’d just finished up my phone interview with Google at about 15:15, so I went downstairs to ALAMODE to find Jack Garner. Then we headed in to Denver to pick us Sam Sartor who was at his job. Sidenote, driving in downtown Denver is terrible. We had to go around the block multiple times just to find him. Anyway, we finally caught up to him and drove up to Fort Collins (specifically the Best Western near the CSU campus). On the way, we stopped to get some Qdoba (we had some leftover catering trays from an event that had happened at school a couple of months back, and when you bring them in to Qdoba, they give you a free burrito).

We arrived to the hotel right behind Dr. Paone and CPW who had driven up in two vans with most of the other people from Mines. We checked in to our rooms (I was rooming with Jack and Easton) and then headed over to the campus for the practice competition.

At the practice competition, we were able to get everything set up properly so that we knew how the development environment worked. The practice competition had three fairly trivial problems, and then an impossibly hard problem (9.5 on Kattis, the highest of any problem on there).

After the practice, we walked back to the hotel. However, some of us made a slight detour to a nearby Cold Stone. That was a great move. As we were walking back from the Cold Stone to the hotel, we got blasted with some terrible wind. I was carrying a whiteboard that I had brought to the practice competition, and I almost lost it a couple of times.

At the hotel, some of us hung out in Kieran and Jake’s room. After a little while, we decided it was a good idea to go to bed because we had an entire programming competition the next day.

That brings us to today. After waking up at 7:30 and taking a quick shower, I went to grab some food at the hotel. Then we drove the 3 minutes over to the CSU campus.

My team (Sam Sartor and Jack Garner) and I had brought the house. We had two whiteboards, 8 whiteboard markers, volumes 1-4A of Donald Knuth’s Art of Computer Programming, my mechanical keyboard, and (most importantly) a rubber duck.

There was some sort of “opening ceremonies/info session” and then the competition started.

The Competition

The competition itself went very well. To start out, Sam and Jack found and implemented the easiest problem (Problem A) in 3 minutes. We were just seconds behind Three Slythery Bois (Jack Rosenthal, Adam Frick, Billy Brickner) who were the first to solve a problem in the entire competition.

By this time, I’d identified the next easiest problem (Problem D) for them to solve. They submitted it at 24 minutes.

As they were solving that problem, I went through all the problems in the competition (there were 12) and determined what types of problems they were. My initial pass got me the following:

• A: Quality-Adjusted Life-Year - trivial
• B: Gwen’s Gift - some sort of combinatorics math
• C: Forest for the Trees - a geometry/ray-tracing question
• D: H-Index - trivial (list processing)
• E: Driving Lanes - DP-esque (I learned at the end that it could be solved with a simple Dijkstra’s shortest path graph traversal through a DAG)
• F: Treasure Spotting - another geometry/ray-tracing problem
• G: Neighborhood Watch - DP path counting (it ended up being some very simple math)
• H: Small Schedule - DP scheduling (it ended up being one just being a fairly simple math problem)
• I: Mr. Plow King - Maximal MST (I thought it might be DP, but it didn’t end up being DP which was nice)
• J: Rainbow Road Race - Graph craziness

I was kinda off the mark on some of them (many turned out to be much easier than I thought they would be).

I’d started thinking about problem C, and then when Sam finished D, we paired up and coded C while Jack worked on G (we saw a few teams completing it on the standings, so we figured it must be a fairly easy one). Our first solution to C failed on a Time Limit Exceeded error. but we were able to fix that and submit a correct solution on 54 minutes. That brought us to 2nd place of the teams competing at CSU with 3 problems completed.

In the middle of us coding up C, Jack had figured out a formula for G. I told him to write up the code which we needed to use on a whiteboard (we fully utilized both whiteboards during the entire competition) so that Sam and I could finish ironing out the bugs in C.

By the time that we finished C, Jack had code on the board, and I quickly typed it into a Python file. Jack’s code had just a couple bugs which were easy to fix (it was basically flawless considering he coded it up on a whiteboard). We submitted G 11 minutes later which bumped our ranking regionally, and helped solidify our second-place spot at CSU with 4 problems solved in the first 65 minutes of the competition and a total time of 186 minutes (including penalty) minutes.

Meanwhile, Sam had started working on F because it was a ray-tracing problem which is his thing. He’d reduced the bulk of the problem to solving a matrix equation, but was having a hard time. I don’t remember exactly what order things happened from here, but I think that he started up coding up some of it while Jack worked out a solution to H. I bounced between helping both of them. It took us a total of 27 minutes to finish H (unfortunately we had a slight snafu with calculating the area of a rectangle… maybe some things are better left unwritten…). At this point, it was the 92nd minute of the competition and we had 5 problems solved. I think we were close to second in the region at this point (definitely second on site at CSU).

At this point, Jack and I started working on E. We figured out the recursive formulation for it (it is very similar to the DP project which I did for Algorithms), figured out how to calculate everything, and then wrote up some code on the whiteboard so we could be just copy from there to the computer. Sam continued working on F while we were doing this, but unfortunately he missed some edge case and his solution failed with a wrong answer.

At this point, Jack and I went to actually implement E, and we left one-half of the monitor for Sam to look at his code (we were using i3 which made this super easy). We wrote it in Python 3 initially, but it gave us a Time Limit Exceeded! We should have just converted it to Python 2 right then and there, but we decided that it may be our algorithm that was actually too slow (wrong assumption, \(\mathcal{O}(nm^2)\) was perfectly fine). We spent over an hour trying to optimize, and then in a last ditch effort, we converted it to Python 2 and our original algorithm worked. We probably could have solved another problem and beaten the team ahead of us in the region on time if we hadn’t wasted ~2 man-hours on that problem, which was kinda annoying.

By this time, Sam had given up for the time being on F and started on I. He solved it, we coded it up, and it worked first time!

Sam tried to work through F, and got extremely close (one or two edge cases away from getting it right). Unfortunately time expired before he was able to finish it.

Both our submissions on E and I happened in the last hour of the competition while the scoreboard was frozen bringing us to seven problems solved. Going in to the last hour, we were in 6th place regionally, 2nd on-site at CSU. The final standings were not announced until 3:30 (30 minutes after the competition ended) so the suspense was real! After time expired, we went around to talk to other teams so that we could see if anyone had solved any problems in the last hour of the competition.

Competition Results

Full standings can be found here: https://rmc18.kattis.com/standings

Then (finally) the announcement of the winners came. He first announced the finalists for the region. Two CSU teams placed 5th and 4th, then Three Slythery Bois placed third, Dream Team 2.0 (Sam Sartor, Jack Garner, me) placed second, and ((+)(((+)s)m)j) (Sam Reinehr, Matt Baldin, Joseph McKinsey) placed first! The Mines teams had managed to hold off the other schools to take all three podium spots on-location at CSU!

Then he announced the winners regionally. He said “we had two top-five finishers at this site”! That meant that we got at least fifth! In fact, we’d done better than that, we finished fourth-place regionally! Sam Reinehr’s team took first-place regionally.

Sam Reinehr’s team went into the last hour with one problem left and managed to finish it. They were able to do that to beat out Utah Arches (University of Utah). That secured them a first place finish regionally, and earned them a repeat trip to ICPC World Finals which will be hosted in Porto, Portugal this spring.

My team went into the last hour at 6th place, and managed to leapfrog Utah Canyonlands and Alberta Gold on time to get 4th place regionally.

A couple of other cool things that happened:

• NP = No Problem (Easton Bornemeier, Kristin Farris, and Matt Iverson) did well with 5 problems solved.
• Mines teams were first to solve all problems except for D (Alberta White was first). Seven firsts were due to ((+)(((+)s)m)j). But on location, Mines teams were first to solve all problems.
• All Mines teams solved at least one problem.
• The Open Sourcerers, a team of all freshmen (Jake Vossen, Kieran Lewis, and Nick Redhorse) completed 4 problems for a 28th-place finish regionally and a 10th-place finish on-location.
• Six of the top 25 teams in the region were from Mines.
• Four of the top 20 teams in the region were from Mines.
• Seven of the top 10 teams on-location were from Mines.
• CU Boulder did not even send any teams (maybe they are still reeling after how badly we beat them at HackCU…)

For me, the second-place finish on-location, fourth-place regionally was the best that my team and I had ever gotten (the previous two years, Sam and I were on a team with Robbie Merillat and we got 3rd on-site, 13th regionally in 2016; and 6th on-site, 15th regionally in 2017).

All in all, the competition was a great success for my team, Sam Reinehr’s team, and all of Mines. Sam and Jack were amazing teammates, and I’m really proud of how well we worked together.