Solving IEEEXtreme 15.0 Hard Problems

October 31, 2021 6 minute read

This post will be updated if I have more time to fill in the details or I solved more problem.

Problem are sorted from least solves to most solves with the exception of Beautiful Summation, because it is beautiful, the problem the caught my eye, the first problem I solved and I like this problem the most.

It is worth noticing that number of solves doesn’t correlates with the difficulty that based on my judgement. A very good example is a hard math derivation problem, can have more solves than a straightforward bitwise optimization problem and a straightforward Rabin-Karp string matching problem. Another example is a DFS problem is having less solves than a HLD problem and a non-trivial meet in the middle optimization problem.

The collection of problems are available at here and the collection of my solutions are available at here.

Beautiful Summation

Problem Statement: CS Academy (18 solves as of 1 Nov 21)

This is the first problem that caught my eye and I am very interested in solving it because of the math nature and how straight forward the problem is.

The first thing that I noticed was \(N\) is very huge, so I know that I need some solution that have at most \(\log(N)\) time complexity. So it is either an \(O(1)\) formula solution or \(O(\log(n))\) divide and conquer solution. I searched through the internet and tried many idea like FFT, \(O(\log(n))\) fast matrix exponentiation, arithmetic progression like formula derivation, and setting up recurrence relation but all leads to dead end.

When I almost gave up and searching the internet for one last time, I used the search term “algorithm for computing power sum” and found this paper that shed some light on the potential solution. The method 2 of the paper seem to suggest a recurrence relation that halving the \(N\) is possible, and if that is possible, there is a high chance that I will have my solution.

I did the math on paper and finally I got my recurrence relation.

Side Note: When working on the math, I found out that the recurrence ralation in method 2 given by the paper is WRONG #faceplam

Solution: Math + Divide and Conquer + DP (Code)

Let \(P\) be constant and \(S(N, Q)\) be our desired sum to obtain.

\[S(n, q) = \sum_{k=1}^{n}{P^k k^q} = P^1 1^q + P^2 2^q + \cdots + P^n n^q \tag{1}\] \[\begin{aligned} S(2n, q) &= P^1 1^q + P^2 2^q + \cdots + P^{2n} (2n)^q \\ &= S(n, q) + P^{n+1} (n+1)^q + \cdots + P^{n+n} (n+n)^q \\ &= S(n, q) + P^n \left( P^1 (n+1)^q + \cdots + P^n (n+n)^q \right) \\ \end{aligned}\]

Lets take a closer look on the following sum

\[x = P^1 (n+1)^q + P^2 (n+2)^q + \cdots + P^n (n+n)^q\]

do a binomial expansion and then factorize

\[\begin{aligned} x &= \textcolor{lightseagreen}{P^1} \left[ \textcolor{violet}{ {q \choose 0} n^q}\textcolor{lightseagreen}{1^0} + \textcolor{violet}{ { q \choose 1} n^{q-1}}\textcolor{lightseagreen}{1^1} + \cdots + \textcolor{violet}{ {q \choose q} n^0}\textcolor{lightseagreen}{1^q} \right] \\ &+ \textcolor{lightseagreen}{P^2} \left[ \textcolor{violet}{ {q \choose 0} n^q}\textcolor{lightseagreen}{2^0} + \textcolor{violet}{ { q \choose 1} n^{q-1}}\textcolor{lightseagreen}{2^1} + \cdots + \textcolor{violet}{ {q \choose q} n^0}\textcolor{lightseagreen}{2^q} \right] \\ &\ \ \vdots \\ &+ \textcolor{lightseagreen}{P^n} \left[ \textcolor{violet}{ {q \choose 0} n^q}\textcolor{lightseagreen}{n^0} + \textcolor{violet}{ { q \choose 1} n^{q-1}}\textcolor{lightseagreen}{n^1} + \cdots + \textcolor{violet}{ {q \choose q} n^0}\textcolor{lightseagreen}{n^q} \right] \\[10px] x &= \textcolor{violet}{ {q \choose 0} n^q} \left( \textcolor{lightseagreen}{P^1 1^0} + \textcolor{lightseagreen}{P^2 2^0} + \cdots + \textcolor{lightseagreen}{P^n n^0} \right) \\ &+ \textcolor{violet}{ {q \choose 1} n^{q-1}} \left( \textcolor{lightseagreen}{P^1 1^1} + \textcolor{lightseagreen}{P^2 2^1} + \cdots + \textcolor{lightseagreen}{P^n n^1} \right) \\ &\ \ \vdots \\ &+ \textcolor{violet}{ {q \choose q} n^0} \left( \textcolor{lightseagreen}{P^1 1^q} + \textcolor{lightseagreen}{P^2 2^q} + \cdots + \textcolor{lightseagreen}{P^n n^q} \right) \\[10px] x &= \textcolor{lightseagreen}{S(n, 0)}\textcolor{violet}{ {q \choose 0} n^q} + \textcolor{lightseagreen}{S(n, 1)}\textcolor{violet}{ {q \choose 1} n^{q-1}} + \cdots + \textcolor{lightseagreen}{S(n, q)}\textcolor{violet}{ {q \choose q} n^0} \end{aligned}\]

finally, a recurrence ralation that halves \(n\)

\[S(2n, q) = S(n, q) + P^n \sum_{i = 0}^{q} \textcolor{lightseagreen}{S(n, i)}\textcolor{violet}{ {q \choose i} n^{q-i}}\]

for completeness of the recurrence relation, we also have

\[\begin{align*} S(0, q) &= 0 \\ S(1, q) &= P \\ S(2n+1, q) &= S(2n, q) + P^{2n+1}(2n+1)^q \\ \end{align*}\]

That is almost but still not the end of the story, we still have some minor details like the final time and space complexity to fill in, lets analyse that.

\(P^n\) can be computed in \(O(\log(n))\) time with fast exponentiation technique.
The binomial coefficient \(\textcolor{violet}{q \choose i}\) can be precomputed with pascal triangle technique with \(O(Q^2)\) time and space. Once the pascal triangle is precomputed we can obtain the binomial coefficient in \(O(1)\) time.
The summation \(\sum_{i = 0}^{q} \textcolor{lightseagreen}{S(n, i)}\textcolor{violet}{ {q \choose i} n^q}\) can be computed in \(O(q\log(q))\) time.
Assuming that \(S(n, 0), S(n, 1), \ldots, S(n, q)\) is computed, \(S(2n, q)\) can be compute in \(O(q\log(q) + \log(n))\) time.
We need to use DP to store the value of computed \(S(n, q)\) because there are overlapping subproblems.
There is total of \(O(2\log(N) \times Q) = O(Q\log(N))\) possible values of \(n\) and \(q\) for which we need to computed the value of \(S(n, q)\).

Hence, the total time complexity will be

\[\begin{align*} & O(Q\log(N) \times (Q\log(Q) + \log(N)) + Q^2) \\ &= O(Q^2\log(Q)\log(N) + Q\log^2(N) + Q^2) \\ &= O(Q^2\log(Q)\log(N)) \qquad \because Q \ll N \\ \end{align*}\]

and total space complexity will be

\[O(Q^2 + Q\log(N))\]

Given \(Q \leq 1000\) and \(N \leq 10^9\), the time complexity should be just enough to solve the problem. My implementation runs in 1989ms on the largest test case which barely passed the time limit of 2000ms.

Image Convolution

Problem Statement: CS Academy (8 solves as of 1 Nov 21)
Solution: Optimization - Bitwise Operation (Code)