From time to time, I’ll run across a UVa problem description that makes liberal use of mathematical notation. UVa 927, the first starred problem in uHunt Chapter 3, is one of those. uHunt classifies it as a Level 4 problem, but most of the challenge is in interpreting the problem description. Once you figure out what it’s asking for, the problem itself is straightforward.
One of the first steps in my puzzle-solving process is to read the problem statement and takes notes on it. For many uHunt starred problems, I can finish this step in a few minutes. The more complicated problems, including those with a lot of math notation, can take quite a bit longer. But it’s worth spending the time. There’s no point in starting to solve a problem without having a good understanding of what it’s asking for.
Take a look at the original UVa 927 problem statement. Try reading it through at a moderate pace, at the speed you would use to read the textbook for a technical subject. After reading through it once, do you have a clear idea of what steps would be required to solve the problem? If so, you’re in reasonable shape when it comes to basic competitive programming math notation.
In my case, I had to read through the description several times before I got it. The notation is not complicated. I know how to represent sets and elements of sets, and how to write a polynomial equation without using specific numbers for the coefficients. Nevertheless, I found that it required a lot of thinking to interpret this problem statement.
If I was writing my own version of the UVa 927 problem statement with the goal of making it more understandable, it would be longer than the original. Someone who reads math notation fluently might find that this actually slowed them down. And it’s likely that these problem statements are intentionally written less clearly than they could be, so that competitors have an incentive to practice reading complicated technical texts, learn standard mathematical notation, and figure things out for themselves.
To highlight how much of this problem’s difficulty is just in interpreting the description, I’m going to attempt to write it more clearly. Here we go:
UVa 927 Problem Statement: The Long But Easy To Read Version
Problem Description
A sequence is a collection of objects in a particular order. In this problem, we’ll be working with sequences of integers. The goal of the problem is to calculate the integer that occurs at a specified position in a sequence.
This problem involves two integer sequences. The first sequence consists of the terms $a_1, a_2, a_3, …$, where each term is an integer. If we want to refer to the entire sequence, we use the notation $\lbrace{a_n}\rbrace$. The $n$th element of the sequence is $a_n$. To calculate the value of a term for a particular value of $n$, we will use the following polynomial function:
$$ a_n = c_0 + c_1n + c_2n^2 + c_3n^2 + … + c_in^i $$
The coefficients $c_0, c_1, …, c_i$ are provided in the problem test cases.
The second sequence used in this problem is constructed using $\lbrace a_n \rbrace$. We’ll refer to this sequence as $\lbrace b_m \rbrace$. Like $\lbrace a_n \rbrace$, the sequence $\lbrace b_m \rbrace$ also consists of integers. The terms of $\lbrace b_m \rbrace$ are $b_1, b_2, b_3, …$. For a particular term of $\lbrace b_m \rbrace$, we’ll use the notation $b_m$. Unlike $a_n$, the term $b_m$ may contain more than one integer. Here’s how that works:
Each test case for this problem has an input value $d$, a positive integer. Each term $b_m$ of the sequence $\lbrace b_m \rbrace$ consists of $n \times d$ copies of the term $a_n$ of the sequence $\lbrace a_n \rbrace$, where $n = m$. For example, if $d = 2$ then:
- $b_1 = a_1, a_1$ ($1 \times 2=2$ copies of $a_1$)
- $b_2 = a_1, a_1, a_1, a_1$ ($2 \times 2=4$ copies of $a_1$)
- $b_3 = a_1, a_1, a_1, a_1, a_1, a_1$ ($2 \times 3=6$ copies of $a_1$)
- …
The goal of the problem is to find and print the $k$th term of $\lbrace b_m \rbrace$, where $k$ is a positive integer provided for each test case.
Example
Set $c_1 = 1$ and set the remaining coefficients to $0$. Then $a_n = n$. In this case, the sequence $\lbrace a_n \rbrace$ is just $1, 2, 3, …$. If $d=1$ then the sequence $\lbrace b_m \rbrace$ is:
$$ \underbrace{1, }_{b_1} $$
$$ \underbrace{2, 2, }_{b_2} $$
$$ \underbrace{3, 3, 3, }_{b_3} $$
$$ \underbrace{4, 4, 4, 4, }_{b_4} $$
$$ … $$
If $k=6$ then the result is the $6$th element of that sequence, which is $3$.
If $d=2$, then ${b_m} = 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, …$. In that case, the $6$th element would be $2$.
Input and output description, and sample input/output
These are relatively clear in the original, so I won’t rewrite them here.
Finding $n$
To solve a UVa 927 test case, we only need to calculate and print one $a_n$ term. Evaluating the $a_n$ polynomial is straightforward, so the only challenge is how to find the value of $n$ that corresponds to the $k$th term of $\lbrace b_m \rbrace$.
This is all it takes:
int findn(int d, int k)
int p = 0;
for (int n=1; ; n++)
int previousp = p;
p += n*d;
if (previousp < k && k <= p) return n;
$d$ and $k$ are provided in the test case, so we can just pass those to the function. $n$ is the index into the $\lbrace a_n \rbrace$ sequence. $p$ is an identifier that doesn’t appear in the problem statement. You can think of it as a candidate $k$ value. Here’s why it’s required:
The $m$ index into $\lbrace b_m \rbrace$ can point to multiple values. For example, in the $\lbrace b_m \rbrace$ sequence shown in the problem statement, $m=3$ refers to $3,3,3$. That’s not very useful, since the $k$ provided by the test case only refers to a single value. That’s where $p$ comes in. In the example sequence $1,2,2,3,3,3,4,4,4,4,…$, $p=1$ refers to $1$, $p=2$ refers to $2$, $p=3$ also refers to $2$, $p=4$ refers to $3$, and so on. Each $p$ value refers to only one integer.
Each $m$ index into $\lbrace b_m \rbrace$ refers to one or more copies of particular $\lbrace a_n \rbrace$ elements. For each $n$ value, we can move $p$ ahead by $n \times d$ positions in $\lbrace b_m \rbrace$. When our target $k$ value falls between the previous $p$ value and the current $p$ value, we have found the correct $n$ index.
$n$ is just an index. Once we have it, we have to find the actual value of $a_n$, which is what the problem asks for. The coefficients $c_0, c_1, …, c_i$ come from the test case. Now we have to calculate $ a_n = c_0 + c_1n + c_2n^2 + c_3n^2 + … + c_in^i $. That’s just a matter of addition, multiplication, and exponentiation. And exponentiation is just repeated multiplication, so we can avoid it by remembering the value of each $n^j$ and using it to calculate $n^{j+1}$. The code to do this is simple:
long poly(int[] c, int n)
long a = 0;
long currentn = 1;
for (int i=0; i<c.length; i++)
a += c[i] * currentn;
currentn *= n;
return a;
Notice that we need to use long integers for the calculation, since the result can be as high as $2^{63}-1$.
Math Fluency
If the original UVa 927 problem statement was perfectly understandable to you the first time you read it, then my revised description may seem redundant or overly wordy. It’s true that math writing often doesn’t spell things out in that level of detail. But that’s the level of detail that you’ll have to be able to extract from a mathematical description in order to make use of it.
I have written in the past about coding fluency. Though reading code and writing math are both useful skills, competitive programming puts more emphasis on writing code and reading math. Problem writers don’t expect participants to be slowed down by math notation, so they make use of it when required.
One challenge with developing math fluency is that people who are fluent in math may find it hard to remember what it was like not to be fluent. This is similar to other types of language fluency. The goal of being fluent is that you don’t have to think about using the language. Once you stop thinking about using math notation, you may not realize that other people struggle with it.
The Quora question How does it feel to finally be red at TopCoder after years of hard work? has some examples of this phenomenon. Here’s how Bohdan Pryshchenko puts it in his answer: “The more you practice&compete, the better you understand that this red color does not mean anything significant.” In other words, once you have enough experience that achieving a red rating is easy, it’s no longer a big deal. So enjoy the journey on the way there.
(Image credit: Yann Duarte)