I Competed in the ICPC, Here is What I Learned

A few weeks ago I got the opportunity to compete in the ICPC(inter collegiate programming competition). I went into the experience with low expectations and a lack of enthusiasm. Having just started my algorithms curriculum I was unsure if I would be able to contribute to my team in a useful way. However at the end of the competition my team placed 14th in our region and had solved half of the available problems. We were by no means the top team but I was surprised at how much we had accomplished in the short 5 hours.

Having never done a programming competition before I didn’t really know what to expect but there were a number of easier problems that just required basic knowledge of modular arithmetic. One tip we got before the competition was to look at the leaderboard early on to see what easy questions were solvable quickly. The faster you solve problems the more points you get overall. In the first two hours we solved 4 problems. 2 that were fairly simple and 2 others that were more moderate in difficulty. This left 8 more problems available.

We spent the next two hours writing and debugging code for 3 other problems. I think this is where we initially went wrong. We had ideas for many of the problems and were trying to diversify and solve many on paper. With only one computer, we should’ve been focused on nailing down solutions to one or two more problems instead of reading a bunch of problem descriptions and trying to come up with ideas. I am going to talk about some of the problems we solved and our approaches. As well as, some problems we struggled with and why.

I’ll add the links to the problem descriptions as well so you can read along and try them for yourself if you’d like. You may want to read the prompts before reading my commentary on the approaches and solutions below. I also want to give a huge shoutout to my team members Aaron and Herb for competing with me.

For more informative graphics and resources check out the full article on my medium here.

This problem was solved by at least 8 teams so we knew it was possible to solve. Originally after reading the problem description I thought we would need to do a modified DFS to keep track of the cost of going through each road in a city and then returning the maximum cost of the paths. However after reading the problem again 30 minutes later after writing some dfs pseudo code my teammates pointed out that the graph might not be a DAG and could have negative edge weights. Meaning this problem needed to be solved using Bellman-fords algorithm. The problem stated that “there could be an edge from u to v and from v to u but the road could only be traverse in one direction” this caused some confusion and we ended up abandoning the problem altogether. Turns out bellman ford was the right approach. Branch Manager Description