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

**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:

##### Subtask 1

We can check all tuples of where , check if , and increment our total.

**Time Complexity:**

##### Subtask 2

Suppose we had an array such that was equal to the number of indices such that and . We can then iterate through all tuples of , and add to our total. We can compute using suffix sums.

**Time Complexity:**

##### Subtask 3

Welcome to another ~~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 with equal to the number of increasing subsequences ending at or before index with a length of and a sum of . Then for each element, we can add to our total and update the array appropriately. We can update the array with the following recurrence:

The initial state of the array is all elements equal to with . Note that we only need to consider and for this problem. While using this recurrence directly uses memory, it is possible to reduce it to .

**Time Complexity:**

## Comments