Editorial for SAC '22 Code Challenge 1 P4 - That Problem
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