Editorial for SAC '22 Code Challenge 1 P4 - That Problem

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: wleung_bvg

Subtask 1

We can check all \binom N 4 tuples of (i, j, k, l) where i < j < k < l, check if A_i + A_j + A_k = A_l, and increment our total.

Time Complexity: \mathcal{O}(N^4)

Subtask 2

Suppose we had an array \text{cnt} such that \text{cnt}[x][y] was equal to the number of indices l such that x < l and A[l] = y. We can then iterate through all \binom N 3 tuples of (i, j, k), and add \text{cnt}[k][A_i + A_j + A_k] to our total. We can compute \text{cnt}[x][y] using suffix sums.

Time Complexity: \mathcal{O}(N^3 + N \cdot \max A_i)

Subtask 3

Welcome to another wleung_bvg editorial. As usual, he still does not know how to do dynamic programming and is bad at grammar, so please continue to bear with him. Note that it is possible to solve this problem without dynamic programming.

Suppose we processed elements from left to right and maintained an array \text{dp} with \text{dp}[i][y][z] equal to the number of increasing subsequences ending at or before index i with a length of y and a sum of z. Then for each element, we can add \text{dp}[i - 1][3][A_i] to our total and update the \text{dp} array appropriately. We can update the \text{dp} array with the following recurrence:

\text{dp}[i][y][z] = \begin{cases} \text{dp}[i - 1][y][z] + \text{dp}[i - 1][y - 1][z - A_i] & y \ge 1, z \ge A_i \\ \text{dp}[i - 1][y][z] & \text{otherwise} \end{cases}

The initial state of the \text{dp} array is all elements equal to 0 with \text{dp}[0][0][0] = 1. Note that we only need to consider y \le 3 and z \le 100 for this problem. While using this recurrence directly uses \mathcal{O}(N \cdot \max A_i) memory, it is possible to reduce it to \mathcal{O}(\max A_i).

Time Complexity: \mathcal{O}(N \cdot \max A_i)


There are no comments at the moment.