Aug 8, 2024
Note: This page is a rough translation from a '99 paper: 隐蔽化、多维化、开放化──论当今信息学竞赛中数学建模的灵活性.
Modern competitive programming competitions increasingly pursue complexity in the solution models. Three strategies are commonly used to increase the complexity: obfuscation, expansion, and diversity. This paper explores these three strategies and the corresponding problem-solving methods.
Obfuscation means to conceal the original model using complex real-world scenarios. With this strategy, the problem setter uses new stories to hide well-known models. For example, Perfect Tour (NOI'97) and New Missile are such cases. On the surface, these problems appear to be unrelated, one describing a street grid and the other a missile. However, both problems are essentially about finding the maximum substring sum in a one-dimensional array. That is, for some \[A=(a_1,a_2,\ldots,a_n),\] find \[\operatorname{max-sum}=\max_{1\le i\le j\le n}\left(\sum_{k=i}^{j}a_k\right).\]
These problems illustrate how the mathematical model may not be directly presented but hidden within complex real-world scenarios.
To deal with these problems, we need to peel off the obfuscation and recover the original model.
Consider Perfect Tour. While this problem looks two-dimensional, we need to notice that
Therefore, we only need to consider the highest value given any column of landscape streets. Then, the problem degrades to maximum substring sum, which we can solve easily.
Often in times we see an expansion of certain aspects in various solutions models. We will take a look at both concrete dimensional expansions and abstract concept expansions.
In dimensional expansions, we have literal expansions of 1D objects into 2D and 2D into 3D. For example, consider this case:
We can see that Model 2 is an expansion of Model 1. In fact, these model expansions are incredibly common in competitive programmings.
The dimensional expansions introduce more spatial factors, increasing the complexity of the models.
When solving such problems, we often need to start with lower-dimensional problems and, after finding suitable solutions for these, extend and generalize them to higher-dimensional problems. This approach is known as "reducing the dimensions," and simplifies complex problems into easier ones while pertaining interesting properties. After we find a solution to the lower-dimensional case, we can easily trace back to the higher-dimensional solution.
This line of thought has various applications, which we will examine below.
Let's take the problem Satellite Coverage as an example. The first major obstacle in analyzing this problem is the spatial complexity. However, the two-dimensional model of this problem, which involves finding the total area covered by several rectangles, has already appeared in IOI'93. Here is the algorithm:
By analogy, we can derive the solution method for the corresponding three-dimensional model:
The solution for the three-dimensional model is similar to that of the two-dimensional model. Thus, by reducing the dimension, we can easily solve the three-dimensional model as well.
This example shows that multidimensional models often inherit certain features from lower-dimensional models, making it possible to apply the solution patterns of lower-dimensional models to more complex multidimensional problems.
Other times, slashing off dimensions can help us transform a 3D problem to a 2D problem, and a 2D problem into a 1D problem. The most famous example is probably the high-dimensional partial order problem, an example being Ispiti.
By doing divide and conquer, we are able to essentially eliminate one dimension from the problem, and repeat until we have a 1D problem which is solved trivially.
Compared to dimensional expansions, concept expansions involve adding stage parameters or state variables to mathematical models. The most typical example of this is in dynamic programming models, e.g. Shopping Offers from IOI'95, Building Game from NOI'97, and Roger's Game from CTSC'98.
To illustrate this point, let's examine Roger's Game. First, consider this well-known model:
There is a 2D grid of size \(A \times B\), where each cell is assigned an integer value that is either \(-1\) or \([0, 255]\). Starting from cell \((x_1, y_1)\), you need to reach cell \((x_2, y_2)\) without passing through any cell with a value of \(-1\). The cost of a path is the sum of the values of all the cells along the way. Find the minimum cost of all possible paths.
As we know, this model is a classic dynamic programming problem. We can represent the initial state and transition with \[ \begin{align*} \operatorname{min-cost}[x_1, y_1]&=\operatorname{map}[x_1, y_1] \\ \operatorname{min-cost}[i, j]&=\min_{\Delta i, \Delta j}(\operatorname{min-cost}[i - \Delta i, j - \Delta j]) + \mathrm{map}[i, j]. \end{align*} \]
Now, let's look at how Roger's Game expands the aforementioned model into a multidimensional one.
In Roger's Game, just like in the first model, we start from cell \((x_1, y_1)\) and move to cell \((x_2, y_2)\). However, unlike the first model, Roger's Game introduces 720 different states due to the different positions of numbers on Roger's six faces. To account for these states, the new dynamic programming equation must introduce new parameters: \[ \begin{align*} \operatorname{min-cost}[x_1, y_1, 0]&=\operatorname{dice}[0]\times \operatorname{map}[x_1, y_1] \\ \operatorname{min-cost}[i, j, k]&=\min_{\Delta i, \Delta j}(\operatorname{min-cost}[i - \Delta i, j - \Delta j, \operatorname{t}[\Delta i, \Delta j, k]]) + \operatorname{dice}[k]\times \mathrm{map}[i, j]. \end{align*} \]
Diversity represents alternative models that are not common in competitive programming. For example, the problem Resistor Network from CTSC'98 is derived from electrical physics with no prior models to draw from. The algorithm involves using basic physical formulas for simple series and parallel circuits to merge resistors until only one remains. Then, we trace back to the original resistor network, calculating the current and voltage across all resistors.
The biggest challenge is the lack of a data structure specifically designed to describe circuits. Therefore, we need to design one to represent this complex resistor network efficiently. Such challenge provides ample room for creativity and imagination, and needs flexibility from the participant to succeed.
The concepts of obfuscation, expansion, and diversity are the three major strategies to increase complexity in competitive programming. However, it is important to recognize that these three aspects do not exist independently of each other.
For example, in Perfect Tour, the model is obfuscated by describing a one-dimensional model using a two-dimensional scenario. While this type of dimensionality differs from dimensional expansion discussed earlier (since the two dimensions here are not the same), it still consists of the idea of a dimensional expansion.
Therefore, we should view these aspects as interconnected rather than isolated. It is often the seamless integration of these three elements that brings more creative problems.