The problems today are Construct the Lexicographically Largest Valid Sequence1, Make Sum Divisible by P2, Find the Winner of an Array Game3, Valid Permutations for DI Sequence4 and Closest Subsequence Sum5.

The solution scripts are pushed on my Github repository: A, B, C, D and E.

gantt dateFormat YYYY-MM-DD HH:mm axisFormat %H:%M section Problem A A :2021-06-17 22:33, 14m section Problem B B :2021-06-17 22:47, 10m B :2021-06-17 23:28, 32m section Problem C C :2021-06-17 22:57, 10m section Problem D D :2021-06-17 23:07, 4m D :2021-06-18 00:00, 37m section Problem E E :2021-06-17 23:11, 17m

## A. Construct the Lexicographically Largest Valid Sequence⌗

### Commentary⌗

Idea. Put the largest unfilled number on the leftmost entry that is empty - if it is impossible, backtrack and remove the previously inserted number.

Suppose that $n = 5$ in our example. Initially there is an array of nine empty entries and none of the numbers are used.

digraph { graph [bgcolor="transparent"] node [color="#ffe4e1", fontcolor="#ffe4e1", fillcolor="#33333c", style="filled"] edge [color="#ffe4e1", fontcolor="#ffe4e1"] node [shape=&#34;rect&#34;] &#34;_________&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] }

The largest unused number that can be filled on the first entry is 5. Let's fill it into the first (and the sixth due to constraints):

digraph { graph [bgcolor="transparent"] node [color="#ffe4e1", fontcolor="#ffe4e1", fillcolor="#33333c", style="filled"] edge [color="#ffe4e1", fontcolor="#ffe4e1"] node [shape=&#34;rect&#34;] &#34;5____5___&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] }

The unused numbers are $\{1, 2, 3, 4\}$. The largest unused number that fits on the second entry is 3. Note that 4 is not feasible because the sixth entry is already filled.

digraph { graph [bgcolor="transparent"] node [color="#ffe4e1", fontcolor="#ffe4e1", fillcolor="#33333c", style="filled"] edge [color="#ffe4e1", fontcolor="#ffe4e1"] node [shape=&#34;rect&#34;] &#34;53__35___&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;3&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;3&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] }

We then can fit 4 and 1 to the third and the fourth entries, respectively:

digraph { graph [bgcolor="transparent"] node [color="#ffe4e1", fontcolor="#ffe4e1", fillcolor="#33333c", style="filled"] edge [color="#ffe4e1", fontcolor="#ffe4e1"] node [shape=&#34;rect&#34;] rankdir=TB &#34;534_354__&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;3&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;3&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] &#34;5341354__&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;3&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;1&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;3&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] &#34;534_354__&#34; -&gt; &#34;5341354__&#34;[color=&#34;transparent&#34;] }

However, the only unused number is 2 and it does not fit to the remaining entries. Hence, we will backtrack to the previous state.

digraph { graph [bgcolor="transparent"] node [color="#ffe4e1", fontcolor="#ffe4e1", fillcolor="#33333c", style="filled"] edge [color="#ffe4e1", fontcolor="#ffe4e1"] node [shape=&#34;rect&#34;] &#34;534_354__&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;3&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;3&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] }

The only number that fits to the fourth entry is 1. Since we have already tested it, there are no solutions and the previous state is further backtracked.

digraph { graph [bgcolor="transparent"] node [color="#ffe4e1", fontcolor="#ffe4e1", fillcolor="#33333c", style="filled"] edge [color="#ffe4e1", fontcolor="#ffe4e1"] node [shape=&#34;rect&#34;] &#34;53__35___&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;3&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;3&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] }

From above, putting 4 into the third entry yields no valid solutions. We will put the next possible number, which is 1. Filling in the remaining entries we have the lexigraphically largest sequence.

digraph { graph [bgcolor="transparent"] node [color="#ffe4e1", fontcolor="#ffe4e1", fillcolor="#33333c", style="filled"] edge [color="#ffe4e1", fontcolor="#ffe4e1"] node [shape=&#34;rect&#34;] &#34;531_35___&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;3&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;1&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;3&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] &#34;531435_4_&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;3&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;1&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;3&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] &#34;531435242&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;3&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;1&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;3&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;2&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;30&#34; height=&#34;30&#34;&gt;2&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] &#34;531_35___&#34; -&gt; &#34;531435_4_&#34;[color=&#34;transparent&#34;] &#34;531435_4_&#34; -&gt; &#34;531435242&#34;[color=&#34;transparent&#34;] }
This looks unsound! The time complexity is $\mathcal{O}(n!)$. Although $1 \leq n \leq 20$, $n!$ is still very big. I am not convinced that a solution is always found early on.

### Timeline⌗

• [2021.06.17 22:33] Start
• [2021.06.17 22:47] First attempt (AC)

## B. Make Sum Divisible by P⌗

### Commentary⌗

We are given an array of $1 \leq n \leq 10^5$ elements $a_1, a_2, ..., a_n$. The objective is to remove the shortest subarray such that the sum of the remaining entries is divisible by a given modulo $p$.

My approach is to compute two partial sums, $L_k$ and $R_k$ for $k = 0, 1, ..., n$:

$L_k = \left(+\sum_{i=1}^k a_i\right)\ \text{mod}\ p, \qquad R_k = \left(-\sum_{i=k+1}^n a_i\right)\ \text{mod}\ p.$

class Solution:
def minSubarray(self, nums: List[int], p: int) -> int:
n = len(nums)

left_partial_sums  = [0 for _ in range(n+1)]
right_partial_sums = [0 for _ in range(n+1)]

for i in range(n):
left_partial_sums[i+1] = (left_partial_sums[i] + nums[i]) % p

for i in range(n, 0, -1):
right_partial_sums[i-1] = (right_partial_sums[i] - nums[i-1]) % p

# Omitted. Let's cover that later.
# Example 1 from the Problem

nums = [3, 1, 4, 2]
p    = 6

left_partial_sums  = [0, 3, 4, 2, 4] # before modulo: [  0,  3,  4,  8, 10]
right_partial_sums = [4, 5, 0, 4, 0] # before modulo: [-10, -7, -6, -2,  0]

What are the partial sums for? Let's make a claim:

Claim. If $a_{m+1}, a_{m+2}, …, a_{m+k}$ are removed so that the sum of the remaining entries is divisible by $p$, then $L_m = R_{m+k}$.

Proof. The below operations are taken under modulo $p$.

\begin{aligned} & (a_1 + a_2 + ... + a_m) + (a_{m+k+1} + a_{m+k+2} + ... + a_n) \\ \equiv\ & \sum_{i=1}^m a_i + \sum_{i=m+k+1}^{n} a_{i} \\ \equiv\ & \sum_{i=1}^m a_i - \left(-\sum_{i=m+k+1}^{n} a_{i}\right) \\ \equiv\ & L_m - R_{m+k} \\ \equiv\ & 0 \end{aligned}

From the above claim, we can remove either one of the following subarray to achieve our goal:

1. $a_1, a_2$ (the remaining entries are 4 and 2, which sums to 6);
2. $a_1, a_2, a_3, a_4$ (this should be rejected because all entries are removed);
3. $a_3$ (the remaining entries are 3, 1 and 2).

We could remove only one element to make the sum divisible by 6.

#### One careless mistake⌗

I received a TLE while solving this. The below code is extracted from the attempt:

class Solution:
def minSubarray(self, nums: List[int], p: int) -> int:
# Omitted...

for i in range(n+1):
lhs[left_partial_sums[i]] = lhs.get(left_partial_sums[i], []) + [i]
rhs[right_partial_sums[i]] = rhs.get(right_partial_sums[i], []) + [i]

# Omitted...

I initially thought that the time complexity for the above snippet is $\mathcal{O}(n)$. It is instead $\mathcal{O}(n^2)$ because we need to copy the slice every time it is referred. I used append to improve the time complexity.

class Solution:
def minSubarray(self, nums: List[int], p: int) -> int:
# Omitted...

for i in range(n+1):
lhs[left_partial_sums[i]] = lhs.get(left_partial_sums[i], [])
lhs[left_partial_sums[i]].append(i)
rhs[right_partial_sums[i]] = rhs.get(right_partial_sums[i], [])
rhs[right_partial_sums[i]].append(i)

# Omitted...

### Timeline⌗

• [2021.06.17 22:47] Start
• [2021.06.17 22:57] Paused
• [2021.06.17 23:28] Resumed
• [2021.06.17 23:50] First attempt (WA: 132/142)
• Reason: Computed an incorrect index.
• [2021.06.18 23:54] Second attempt (TLE: 139/142)
• Reason: As stated above.
• [2021.06.18 00:00] Third attempt (AC)

## C. Find the Winner of an Array Game⌗

Idea. It is a simple simulation question… It is equivalent by removing the loser instead of moving it to the end of the array. Note that the losers won’t win again because the numbers of the winners should be increasing.

### Timeline⌗

• [2021.06.17 22:57] Start
• [2021.06.17 23:07] First attempt (AC)

## D. Valid Permutations for DI Sequence⌗

Idea. Use dynamic programming where dp[i][j] is the number of permutations such that a[i] is the j-th largest amongst a[0], a[1], …, a[i].

### Timeline⌗

• [2021.06.17 23:07] Start
• [2021.06.17 23:11] Paused
• [2021.06.18 00:00] Resumed
• [2021.06.18 00:10] Hinted
• [2021.06.18 00:37] First attempt (AC)

## E. Closest Subsequence Sum⌗

Idea. This is a pretty standard meet-in-the-middle challenge that decreases the number of checks for brute-force from $2^{40}$ to $2^{21}$.

### Timeline⌗

• [2021.06.17 23:11] Start
• [2021.06.17 23:21] First attempt (WA: 0/73)
• Reason: I misclicked submit during testing...
• [2021.06.17 23:28] Second attempt (AC)

## Postmortem⌗

Surprisingly, I was used to solve dynamic programming problems effectively when I was in ACM-ICPC team. However it took far more time for me to figure out that D was a DP problem. On the other hand, I received less incorrect attempts. Does it mean that I am more careful than yesterday?

1. LeetCode "Construct the Lexicographically Largest Valid Sequence"
https://leetcode.com/problems/construct-the-lexicographically-largest-valid-sequence/
2. LeetCode "Make Sum Divisible by P"
https://leetcode.com/problems/make-sum-divisible-by-p/
3. LeetCode "Find the Winner of an Array Game"
https://leetcode.com/problems/find-the-winner-of-an-array-game/
4. LeetCode "Valid Permutations for DI Sequence"
https://leetcode.com/problems/valid-permutations-for-di-sequence/
5. LeetCode "Closest Subsequence Sum"
https://leetcode.com/problems/closest-subsequence-sum/