The Art of Problem Setting: Insights from TopCoder and CodeChef Contest Problems

As an experienced problem setter for prestigious programming contests like the Indias Informatics Olympiad and the International Online Programming Contest (IOPC), I have had the unique opportunity to explore the vast realm of problem creation. This article delves into the creative processes behind developing problems for competitive coding platforms such as TopCoder and CodeChef.

Origins of Problem Setting

There are varying methods one can use to generate programming problems, and typically, this includes either coming up with interesting and novel problems or creating a comprehensive problem set based on specific requirements. While the first approach is more fun and creative, the second method is crucial when conducting a large-scale contest like IOPC. Generating problem sets requires careful planning and ensuring that each problem is appropriately challenging and novel enough to engage regular participants.

Examples of Problem Creation

Spreadsheet Scrolling

One example of a challenging problem that originated from a practical observation is Spreadsheet Scrolling. Initially, I envisioned a two-dimensional version of the problem where the task was to move a rectangle with dimensions L × B to visit all N points on a 2D plane. However, this version turned out to be too difficult for our purposes. We opted for the one-dimensional version, choosing it as the easy problem, which eventually became a source of frustration for many participants. This example highlights the importance of balancing difficulty and ensuring the problem is accessible to a wide range of contestants.

Truly Magical Numbers

Another intriguing problem, Truly Magical Numbers, was inspired by the unique property of the number 142857, which, when multiplied by integers from 1 to 6, only permuted the digits. My fascination with this property led to an extended search for a similar number that would permute the digits upon multiplication by integers up to 9. After discovering one such number, I was eager to turn it into a contest problem, although the judge for this problem turned out to be a bit complex to design.

Triangle Equality

The problem Triangle Equality was born from my love for segment trees and Manhattan distance. After realizing that combining these two concepts could result in an interesting problem, I meticulously crafted it. This example illustrates how personal interests and existing knowledge can fertilize the ideation process, leading to the creation of engaging and challenging problems.

Artistic and Collaborative Problem Setting

Artistic and collaborative efforts often result in the synthesis of complex and diabolical problems. In the case of Partitioning the Plane, we faced a challenge as there were no geometry problems in the contest. This situation, coupled with a sense of desperation, led to an artificial and seemingly silly problem. However, the collective effort and ideas from the team helped to create a more engaging and challenging problem.

A similar story emerges with Progressive Progressions. This problem originated in a Physics lab, where I sampled points with increasingly distant coordinates to reduce effort yet maintain meaningful results. The idea of a progressive progression caught my attention, and this insight led to a problem that still resonates with those who enjoy logical thinking and pattern recognition.

From Nim to Real Complexity

Creating a game theory problem such as Move the Books was initially challenging since our only known game was Nim. To create a more engaging problem, we started with a simple Nim game and gradually made it more complex, transforming it into a game-theory problem that was both engaging and challenging. This example highlights the iterative and creative process involved in problem setting, where simplicity and complexity coexist.

Counting the Teams is another fascinating case study. The basic version of the problem was derived from permutation cycles and expectation values. However, after significant research and optimization by Utkarsh, we managed to increase the problem's constraints, resulting in a highly challenging and interesting problem.

A Personal Touch

Problems like Rubiks Cube and Crazy Texting have a personal element to them. The Rubiks Cube problem was inspired by my interest in group theory, while Crazy Texting was a result of the frustration of typing on an outdated T9 keypad. These problems exemplify how personal experiences and irritations can lead to innovative and interesting problems.

Lastly, GM Plants showcases the power of combining multiple segment trees to create a challenging and engaging 3D problem. This problem, inspired by a similar 2D problem set by Prateek for the IOITC, illustrates the importance of building upon existing ideas to create new and complex problems.

In conclusion, the process of generating problems for competitions like TopCoder and CodeChef involves a blend of creativity, logic, and teamwork. Through diverse approaches and personal insights, we can create a rich and engaging problem set that challenges and entertains participants.