Can you fight zombies with mathematical precision? Could a hungry fish benefit from dynamic programming? These are the questions that inspire the developers who craft the questions for Facebook’s annual Hacker Cup.
Today is the grand finals for the competition, now in its ninth year. The programming contest is open to the public and attracted over 6,000 participants this year. The final 25 contestants, who passed through four qualifying rounds with the highest scores, will try to solve their way to victory starting at 9:30am PST - 12:30pmEST -5:30pm Dublin time. You can catch the live stream here.
Since Stack Overflow is all about asking and answering programming questions, we thought it would be interesting to sit down with some of the developers who write the questions for Hacker Cup and learn how they craft their problems. And while most of the questions on SO are a little more practical in nature, Stack Exchange has its own community of Code Golfers who enjoy devising the most efficient solutions to programming problems in their spare time.
So, what makes for a great Hacker Cup problem? We chatted with Jacob Plachta and Wesley May, Hacker Cup contributors who have written most of the problems used over the last few years. The pair met while studying at the University of Toronto, and have been working together on Hacker Cup since 2014.
Along with sharing some insights into how they approach the process of crafting these problems, Plachta and May also shared a problem that was designed for the 2018 season but ultimately not included in the competition. You can find it here, and we look forward to seeing our community take a crack at this puzzle.
Striking the right balance
The challenge of crafting a great Hacker Cup problem set, say May and Plachta, is managing problem difficulty, variety, and originality. The goals of every round are to narrow the field for the next round, and to ensure that everybody has an enjoyable and educational experience.
“In the final round, it’s ideal if every problem gets solved, everybody solves at least one problem, but nobody solves every problem,” says May. “In earlier rounds we want the overall difficulty to be such that everybody who solves every problem advances, but you don’t need to solve every problem to advance.”
Problems need to have variety while remaining within the scope of the contest. The solution to every problem should be attainable from first principles or combinations of well-known algorithms. No one should be stumped by a question because it relies on some unusually specialized knowledge. That said, nobody wants to solve the same problems every contest, so the problems also need to be original.
Plachta thinks of there being two general approaches to creating problems. The first involves starting with some aspect of the solution then working backwards to come up with a problem. “This approach can work, but it can also easily lead to problems that end up feeling more standard, less original,” says Plachta. The second approach, which Plachta uses more often today, starts with a problem where the solution is unknown.
“I basically spend a lot of time sitting around thinking of rough ideas which could possibly turn into problems,” says Plachta. "Any given idea is very unlikely to work out, definitely less than a 10% chance. Maybe it'll feel uninteresting after all, or maybe upon trying to solve the resulting problem, it'll turn out too easy, too cumbersome, or unsolvable. Unfortunately, you often can't tell until you've thought it through much of the way. But, upon trying enough different ideas or variations of them, I'll happen across one that actually turns into a great problem. That's always really exciting!"
Finding Inspiration From The Everyday World
Sometimes a problem comes out of experiences in the real world. May and Plachta run across something that gets them thinking, then slowly find a way to form those ideas into a coding problem. “I helped write a problem for the third round of the 2015 season called Broken Bits,” says May. “It was based on my actual observations of a digital clock that was broken, meaning some of the LED segments just didn’t work. I remember staring at that for a while and thinking, well, you can look at this clock, and maybe you can't tell what time it is because some of the segments are missing, and that makes it ambiguous. But if you watch this clock for long enough, eventually you may have enough information to figure out what time it must have actually been.”
Problem ideas can also arise from games. “I was playing a bunch of Pathfinder Adventure Card Game with friends,” recalls May. “You get to choose different items for your attacks, which means using different dice to determine how much damage you'll do. Maybe I have one attack that has a higher average damage, but I might prefer a different one that has a lower average yet higher variance. That turned into a problem called Fighting the Zombie, which appeared in the qualification round for 2017.”
“Sometimes we’ll use the same characters and themes across multiple problems each year. The problems can feel like thematically they ought to be similar even though they might be very different,” says May. “Last year we had a series of problems about a struggling computer science student who’s never quite able to code things correctly.” Once they have a theme in mind, Plachta and May try to develop it further to see what other problems might come out of it.
This is a computer programming challenge, but sometimes inspiration comes from nature, for example watching a tuskfish smash clams against rocks on Planet Earth. “This concept seemed cool, so I thought about how to expand on it. Maybe there could be multiple clams and rocks with different hardnesses, such that clams would need to be smashed against harder rocks,” says Plachta. “I considered a bunch of variations, including what context to place these clams and rocks in and what the goal should be. As it turned out, the simple concept of arranging them on a number line and asking for the minimum travel distance to go around opening all of the clams worked out just right, resulting in the final problem in the 2019's second round, Seafood."
“It's the sort of problem which might seem infeasible at first, given the exponential number of possible routes the tuskfish might take, which is ideal. It's only upon further thought that you can narrow down the possibly-optimal routes to a more manageable set of patterns. From there, it boils down to a problem solvable using dynamic programming -- that's a general approach for efficiently solving optimization problems by recursively solving smaller subproblems, which is often useful in contests. Though in this case, a further, more advanced technique often called the 'convex hull trick' was required to arrive at an efficient-enough time complexity.”
Regardless of inspiration, they make a problem interesting by wrapping it in a narrative. “There's a layer of varnish at the end which is the story. Like you certainly don't have to have this, but it's a lot more fun.” A problem about placing blocks on a grid is presented as a rivalry between two pizza delivery guys. A problem about moving around the nodes on a tree becomes a tale of marital strife for a family of moles.
Ever-Evolving Complexity
If you look at the winning routines from Olympic gymnasts a few decades ago, they seem incredibly simplistic when compared with the complexity of top performances today. The same is true for the kind of problems completed during the Hacker Cup, which has been running since 2011, and comes out of a much older lineage of competitions like the ICPC, which has been active since the 1970s. The problems have only gotten harder since the days when May started. “If I look at World Finals problems from ICPC back in like 2008, I can knock out quite a lot of those problems now. Whereas if I look at a problem set from today, on my own, I’m probably solving at most three of 11 problems.”
The final rounds from the 1970s and 80s would be considered middling difficulty today. “Earlier problems were pretty explicit about what you had to do, and most of the challenge was in the implementation and not the actual problem solving. These sorts of problems are generally considered trivial and tedious nowadays,” says May. “The focus has shifted towards finding interesting applications of core algorithms and data structures. So for example, figuring out which tools are best for the situation -- binary search, depth first search, segment trees, dynamic programming, etc. and putting those to work.”
Because many of the contestants have been solving these sorts of problems throughout high school and college, and come armed with pre-written algorithms, Hacker Cup problems need to be about more than just identifying the right tools. “What we try to get into our problems nowadays are interesting transformations,” says May. “Maybe you get some game that's not explicitly played on a graph, but if you think about it in the right way you can see that is actually has some graph structure abstractly. A hard problem should be hard because it takes a series of interesting insights to come up with a feasible solution, not because the actual coding work is long and finicky.”
As the ability of contestants improves, it’s sometimes the contestants that surprise the problem authors. “Contestants' submissions can sometimes turn out more elegant than what we could come up with ourselves,” explains Plachta. “A good example was with a problem called Integers as a Service in this year's third round. I intended for the solution to involve prime factorization and handling different primes independently, a pretty typical way of dealing with GCDs and LCMs, as was required in this problem. And, that is how many people went about it. But some top contestants came up with a simpler approach taking advantage of how GCDs and LCMs interact with one another and using them more directly. It's really cool and impressive seeing these kinds of thought processes materialize even in the short timespan of a contest!”
While the broader world of competitive programming has evolved, so has Hacker Cup. For the first few years, every round had three problems including the finals. Now every online round has four problems and the final has gone from three hours for three problems to four hours for six problems. “Not only have we added problems, we’ve also strived to keep improving the quality and originality. We want every year to be better than the last,” says May. Some aspects of the overall philosophy have also changed over time. “We used to be meaner regarding the example test cases that are given for each problem. Because you only get one chance to submit each problem in Hacker Cup, we try to be more generous nowadays. If you’re correct on the sample data, chances are you have the right solution. We’re trying to test your ability to solve interesting problems, and not trying to catch you on an off-by-one error.”
By Hackers, for Hackers, Open to All
Both May and Plachta are former ICPC World Final competitors. They originally met in 2011 at the tryouts for the University of Toronto ICPC team, and they ended up going to the World Finals together. The next year, May could no longer compete in the ICPC as there’s a two-appearance limit in the World Finals, so he took over coaching duties at U of T while Plachta and his team made another World Finals run. Since then, they have written problems for a variety of contests, including high school-level ones such as the Canadian Computing Olympiad and Woburn Challenge.
More remarkably, while May became a competitive programmer while studying CS, Plachta was studying music. “My first World Finals team had a statistics major who did most of the problem solving while the other two of us did all the coding,” says May. “You don’t need to be doing a traditional ‘tech’ subject to enjoy and be successful at algorithmic competitions. Neither of my two best teammates were focused on CS or engineering.”
Over the years, Hacker Cup participants have gone on to work at Facebook, many of whom were still in college or high school when they took part. “While competitive programming tests only a very specific subset of skills, taking part shows a certain level of enthusiasm for coding,” says May. “I did my undergrad at Simon Fraser University which isn’t particularly well-known in the States. My competitive programming activities are what put me on Facebook’s radar in the first place.”
During the early years, Facebook always held the final phase of the tournament at their headquarters in Menlo Park. As part of trying to expand the reach and accessibility of the contest, Facebook began choosing new locations from around the globe to host the live event. This year the Hacker Cup is taking place in Dublin, and you can catch a live stream of the finals beginning at 8:30am EST. And if you want to read more about Plachta, check out a profile here. Last but not least, if you feel like some puzzling this morning, don’t forget to check out the question the Hacker Cup team shared on Code Golf.
The Stack Overflow blog is committed to publishing interesting articles by developers, for developers. From time to time that means working with companies that are also clients of Stack Overflow’s through our advertising, talent, or teams business. When we publish work from clients, we’ll identify it as Partner Content with tags and by including this disclaimer at the bottom.