Problem Statement: We’re given a polynomial $a_n$ of degree $i$ with non-negative integer coefficients. $a_n$ can be expressed as followed:

\[ a_n = c_0 + c_1n + c_2n^2 + c_3n^3 + \cdots + c_in^i\]

We can construct a sequence from the given polynomial $a_n$ for different values of $n$. We denote this sequence as $ \{ a_n \} $. So it can be $\{a_1, a_2, a_3,\ldots\}$ for $ n = 1, 2, 3, \ldots$.

We’re also given two positive integers $d$ and $k$. Another sequence $\{b_m\}$ is constructed for $m = 1,2,3,\ldots$ where $b_m$ is the term $a_n$ repeated $n \times d$ times. So for example, when $d = 2$, $b_1$ will be two occurrences of $a_1$. $b_2$ will be four occurrences of $a_2$ and so on.

Given all this, we’re told to find the $k$-th integer in the sequence $\{b_m\}$.

Solution: We compute $a_n$ for increasing value of $n$. For each value of $n$, we know that $a_n$ will repeated $n \times d$ times. We add the number of occurrences to a variable called $\textrm{counter}$. When $\textrm{counter} \geq k$, we stop and print $a_n$ for that particular value of $n$.

Here’s the implementation in C++:

What is the worst case time complexity of the above program? To find that out, we only need to figure out the time complexity of the while loop block between line $27-38$.

In the worst case, the $\textrm{counter}$ variable increases as slowly as possible to catch up to $k$. So, we need to make $d$ as low as possible and $k$ as high as possible.

We have $d_{min} = 1$ and $k_{max} = 10^6$. How many times the while loop will iterate? $\textrm{counter}$ becomes $1$, $2$, $3$, and so on. Also, this sequence can’t go on forever otherwise the while loop won’t terminate. Let $p$ be the last term of this sequence. So we have,

\[ 1 + 2 + 3 + \ldots + p = k_{max} = 10^6\] \[ \implies \ddfrac{p(p + 1)}{2} = 10^6\] \[ \implies p \approx 1414 \]

So, the inner while loop will iterate at most $1414$ times. For highest degree, $i_{max} = 20$, the total iteration becomes $1414 \times 20 \approx 30000$. So, this is $\mathcal{O}(1414*\textrm{degree}$) solution per test case.

But we can get rid of the high constant value and get an $\mathcal{O}(\textrm{degree})$ solution. How? Instead of just iterating until we cross the value of $k$, we solve a quadratic equation to get the value in $\mathcal{O}(1)$ time. Taking the previous equation where $d$ can take any value, we have,

\begin{eqnarray} d + 2d + 3d + \ldots + pd & \geq & k \nonumber \newline \implies d (1 + 2 + 3 + \ldots + p) & = & k \nonumber \newline \implies \ddfrac{p(p + 1)}{2} & \geq & \ddfrac{k}{d} \nonumber \newline \label{uva927-eq1} \implies p^2 + p - \ddfrac{2k}{d} & \geq & 0 \end{eqnarray}

Now, we’ll calculate the $p$ value when $\eqref{uva927-eq1}$ is $0$. The outcome will either be a floating point number or an integer. Remember, we want the smallest value of $p$. So, if the outcome is an integer, no other value of $p$ can be lower than that and satisfy $\eqref{uva927-eq1}$ at the same time. If the outcome is a floating point number, we’ll take the ceil of $p$. Why ceil? Because $p$ must be an integer, and the smallest integer that can satisfy $\eqref{uva927-eq1}$ is the ceil of $p$ when $p$ is a floating point number. Either way, we’ll take the ceil of $p$ because if $p$ is an integer, then it’s ceil is itself.

When we let, $\eqref{uva927-eq1}$ to be $0$, we have the following quadratic equation:

\begin{equation} \label{uva927-eq2} p^2 + p - \ddfrac{2k}{d} = 0 \end{equation}

Now, solving $\eqref{uva927-eq2}$ we get,

\[ p = \ceil{\ddfrac{-1 + \sqrt{1 + \ddfrac{8k}{d}}}{2}} \]

Here’s the implementation in C++: