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

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$ $(\binom{N}{4})$ tuples of $(i, j, k, l)$ $(i, j, k, l)$ where $i < j < k < l$ $i < j < k < l$ , check if $A_i + A_j + A_k = A_l$ $A_{i} + A_{j} + A_{k} = A_{l}$ , and increment our total.

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

Subtask 2

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

Time Complexity: $\mathcal{O}(N^3 + N \cdot \max A_i)$ $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}$ $dp$ with $\text{dp}[i][y][z]$ $dp [i] [y] [z]$ equal to the number of increasing subsequences ending at or before index $i$ $i$ with a length of $y$ $y$ and a sum of $z$ $z$ . Then for each element, we can add $\text{dp}[i - 1][3][A_i]$ $dp [i - 1] [3] [A_{i}]$ to our total and update the $\text{dp}$ $dp$ array appropriately. We can update the $\text{dp}$ $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}$ $dp [i] [y] [z] = {\begin{cases} dp [i - 1] [y] [z] + dp [i - 1] [y - 1] [z - A_{i}] & y \geq 1, z \geq A_{i} \\ dp [i - 1] [y] [z] & otherwise \end{cases}$

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

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

Comments

There are no comments at the moment.