Editorial for DMOPC '21 Contest 8 P3 - Weaker Data

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

Subtask 1

Hint

Insert the numbers in the order $N, N-1, \dots, 1$ . How many new valleys are added each time?

Hint 2

Use dynamic programming.

Solution

Consider inserting the numbers in the order $N, N-1, \dots, 1$ . If we are inserting the number $x$ and there are $i$ previously inserted numbers before $x$ , this adds $i(N-x-i)$ new valleys. We can now use dynamic programming, where $dp[i][j]$ represents that we have inserted $i$ numbers and there are currently $j$ valleys. As we may have $\mathcal{O}(N^3)$ valleys in the worst case, we need $\mathcal{O}(N^4)$ states and a total of $\mathcal{O}(N^5)$ transitions.

To solve for the lexicographically smallest permutation, we can let $dp[i][j]$ be a list, representing the lexicographically smallest partially formed permutation. Comparing these permutations adds another factor of $N$ to the complexity, but this solution should still easily pass subtask 1 as the constant factors are tiny.

Time Complexity: $\mathcal{O}(N^5)$ or $\mathcal{O}(N^6)$

Non Lexicographically Least

Hint

Which $K$ are possible?

Hint 2

Use a greedy algorithm.

Subtask 2 Solution

Consider which $K$ are possible for each $N$ . Trying some small cases, following our approach of inserting $N, N-1, \dots, 1$ in order, we can find that:

When $N = 1$ ~N = 1~ or $N = 2$ ~N = 2~, only $K = 0$ ~K = 0~ is possible.
When $N = 3$ ~N = 3~, we can add either $0$ ~0~ or $1$ ~1~ to a number obtainable from $N = 2$ ~N = 2~. Thus $K \in [0,1]$ ~K \in [0,1]~ are possible.
When $N = 4$ ~N = 4~, we can add either $0$ ~0~ or $2$ ~2~ to a number obtainable from $N = 3$ ~N = 3~. Thus $K \in [0,3]$ ~K \in [0,3]~ are possible.
When $N = 5$ ~N = 5~, we can add either $0$ ~0~ or $3$ ~3~ or $4$ ~4~ to a number obtainable from $N = 3$ ~N = 3~. Thus $K \in [0,7]$ ~K \in [0,7]~ are possible.

At this point, we might realize that the problem reduces to representing $K$ as the sum of numbers of the form $i(N-x-i)$ , and we might conjecture that all $K$ between $0$ and the maximum possible $K$ are obtainable. Let's try a greedy approach to write $K$ in this form. Since the added numbers are smaller when inserting $N, N-1, \dots$ , we should intuitively use them last to gain more control over $K$ . This encourages us to loop through $x$ in the order $1, 2, \dots, N$ , greedily picking the largest $i(N-x-i)$ that does not exceed the current value of $K$ each time.

Proof

Let $a_x = \left\lfloor \frac{x}{2} \right\rfloor \cdot \left\lceil \frac{x}{2} \right\rceil$ for all $x$ be the maximum possible $i(x-i)$ . We will prove by induction on $N$ that all $K$ between $0$ and $\sum_{n=0}^{N-1} a_n$ can be formed this way. The base cases $N = 1,2$ are clear. Suppose the induction hypothesis is true for $N-1$ . Then we have two cases:

If $K \le \sum_{n=0}^{N-2} a_n$ ~K \le \sum_{n=0}^{N-2} a_n~, then the greedy algorithm will not increase $K$ ~K~, so $K$ ~K~ is still $\le \sum_{n=0}^{N-2} a_n$ ~\le \sum_{n=0}^{N-2} a_n~ when there are $N-1$ ~N-1~ numbers left.
If $\sum_{n=0}^{N-2} a_n < K \le \sum_{n=0}^{N-1} a_n$ , then note that $a_{N-1} \le \left(\sum_{n=0}^{N-2} a_n\right)+1 \le K$ , so the greedy algorithm will leave $K$ ~K~ as $K-a_{N-1} \le \sum_{n=0}^{N-2} a_n$ ~K-a_{N-1} \le \sum_{n=0}^{N-2} a_n~ when there are $N-1$ ~N-1~ numbers left.

In both cases, the induction step follows.

Afterwards, it is easy to simulate inserting the numbers in quadratic time overall.

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

Subtask 3 Optimizations

For subtask 3, we can binary search for $i$ each time and use a data structure such as a binary indexed tree to simulate the greedy algorithm.

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

Lexicographically Least

Hint

Print out all the lexicographically smallest permutations for small $N$ generated by a brute force or the subtask 1 algorithm, and look for patterns.

Hint 2

Except for a single family of corner cases that reduce to $N = 5, K = 4$ , we should always insert a number $x$ either at the front or in the middle of the partially formed permutation.

Subtask 2 Solution

Printing out all the lexicographically smallest permutations for small $N$ , we might notice some patterns. In general, we should always insert a number at the left end if possible (to minimize the first element of the permutation), or we should insert it in the middle (intuitively, this leaves $K$ as small as possible for the rest of the permutation, which makes it more likely that the first element of the final permutation is small). This is true except for when the permutation reduces to the $N = 5, K = 4$ case, where the permutation should be 2 1 4 3 5.

More precisely, let $a_x = \left\lfloor \frac{x}{2} \right\rfloor \cdot \left\lceil \frac{x}{2} \right\rceil$ for all $x$ and let $b_n = \sum_{x=0}^{n-1} a_x$ for all $n$ . We should insert $1$ at the left end if $0 \le K \le b_{N-1}$ , or insert $1$ at position $\left\lfloor \frac{N+1}{2} \right\rfloor$ if $b_{N-1} < K \le b_N$ , except for the $N = 5, K = 4$ case, and continue to fill out $2, 3, \dots, N$ similarly.

Proof Sketch

Let $Lex(N,K)$ be a $0$ -indexed sequence of length $N$ , the lexicographically least permutation for the input N K, defined for all $0 \le K \le b_N$ . For any two sequences $p$ and $q$ , let $p < q$ denote that $p$ is lexicographically smaller than $q$ , let $p+1$ denote the sequence formed by adding 1 to all terms of $p$ , and let $Ins(p,c,x)$ denote the sequence formed by inserting the number $x$ before $p_c$ in $p$ .

We will prove by induction on $N$ that $Lex(N,K)$ will be generated by this algorithm, and furthermore, it satisfies $Lex(N,k) < Lex(N,k+1)$ for all $0 \le k < b_N$ . Small base cases of $1 \le N < 100$ or so can be computer verified with the subtask 1 dynamic programming code.

Suppose that $N \ge 100$ and the induction hypothesis is true for $N-1$ . Then $Lex(N,K) = Ins(Lex(N-1,K-c(N-1-c))+1,c,1)$ for some $0 \le c \le N-1$ . Since replacing $c$ by $N-1-c$ gives the same $K-c(N-1-c)$ , we must in fact have $0 \le c \le \left\lfloor \frac{N-1}{2} \right\rfloor$ . Now we have some cases:

If $0 \le K \le b_{N-1}$ ~0 \le K \le b_{N-1}~, then the algorithm inserts $1$ ~1~ at the beginning of $Lex(N-1,K)+1$ ~Lex(N-1,K)+1~. Thus, $Lex(N,K)_0$ ~Lex(N,K)_0~ must be $1$ ~1~, and it follows that $c = 0$ ~c = 0~ and the algorithm indeed correctly generates $Lex(N,K)$ ~Lex(N,K)~.
If $b_{N-1} < K \le b_N$ ~b_{N-1} < K \le b_N~, then the algorithm inserts $1$ ~1~ at the middle of $Lex(N-1,K)+1$ ~Lex(N-1,K)+1~, before position $\left\lfloor \frac{N-1}{2} \right\rfloor$ . We must have $c > 0$ ~c > 0~; suppose that $c < \left\lfloor \frac{N-1}{2} \right\rfloor$ .
- If $c \ge \log_2(a_{N-1})+5$ ~c \ge \log_2(a_{N-1})+5~, then we have $Lex(N-1,K-a_{N-1}) < Lex(N-1,K-c(N-1-c))$ by induction hypothesis. It suffices to prove that $Lex(N-1,K-a_{N-1})$ ~Lex(N-1,K-a_{N-1})~ and $Lex(N-1,K-c(N-1-c))$ ~Lex(N-1,K-c(N-1-c))~ first differ in a position less than $c$ ~c~.
  
  Note that $K-c(N-1-c) > K-a_{N-1} > b_{N-1}-a_{N-1}$ . In the algorithm, the numbers that get inserted in the beginning while forming a sequence of the form $Lex(N-1,b_{N-1}-k)$ ~Lex(N-1,b_{N-1}-k)~ is equivalent to the sequence from applying a greedy subset sum algorithm to $k$ ~k~ with $a_{N-2}, a_{N-3}, \dots, a_0$ ~a_{N-2}, a_{N-3}, \dots, a_0~ (that is, loop through $a_{N-2}, a_{N-3}, \dots, a_0$ ~a_{N-2}, a_{N-3}, \dots, a_0~ in order. Whenever we see a number $a_i$ ~a_i~ that does not exceed the current value of $k$ ~k~, add $N-1-i$ ~N-1-i~ to the front of the sequence and subtract $a_i$ ~a_i~ from $k$ ~k~), up to some small issues near the end from the $N = 5, K = 4$ ~N = 5, K = 4~ case.
  
  Note that $a_i \le \frac{1}{2}a_{i+1}$ ~a_i \le \frac{1}{2}a_{i+1}~ for all $i$ ~i~. It follows that if $a_j$ ~a_j~ is the first number that did not get subtracted from $k$ ~k~ (because $k < a_j$ ~k < a_j~), then each time some $a_i$ ~a_i~ with $i < j$ ~i < j~ is subtracted from $k$ ~k~, $k$ ~k~ is reduced to at most half the old value. Since $K-c(N-1-c) > K-a_{N-1} > b_{N-1}-a_{N-1}$ , we can apply this lemma with $k = b_{N-1}-(K-c(N-1-c)) < a_{N-1}$ ~k = b_{N-1}-(K-c(N-1-c)) < a_{N-1}~ and $k = b_{N-1}-(K-a_{N-1}) < a_{N-1}$ ~k = b_{N-1}-(K-a_{N-1}) < a_{N-1}~ (using $a_j = a_{N-1}$ ~a_j = a_{N-1}~) to conclude that at most $\log_2(a_{N-1})+2$ ~\log_2(a_{N-1})+2~ numbers get inserted in the beginning while forming $Lex(N-1,K-a_{N-1})$ ~Lex(N-1,K-a_{N-1})~ and $Lex(N-1,K-c(N-1-c))$ ~Lex(N-1,K-c(N-1-c))~. As $K-a_{N-1} \ne K-c(N-1-c)$ ~K-a_{N-1} \ne K-c(N-1-c)~, these sets of numbers are different. Furthermore, we can show that no two numbers (except for the ones that are almost $N$ ~N~) in these sets differ by $1$ ~1~, so when the first elements of the partially formed permutations differ, this difference will only get "pushed" right by elements inserted at the beginning. It follows that there is indeed a difference within the first $c$ ~c~ numbers.
- Otherwise, $c < \log_2(a_{N-1})+5$ ~c < \log_2(a_{N-1})+5~. It suffices to prove that $Lex(N-1,K-a_{N-1})_0 < Lex(N-1,K-c(N-1-c))_0$ .
  
  By the algorithm, $Lex(N-1,K-a_{N-1})_0$ ~Lex(N-1,K-a_{N-1})_0~ is equal to $N-1$ ~N-1~ minus the largest $i$ ~i~ such that $a_i \le b_{N-1}-(K-a_{N-1})$ ~a_i \le b_{N-1}-(K-a_{N-1})~ and $Lex(N-1,K-c(N-1-c))_0$ ~Lex(N-1,K-c(N-1-c))_0~ is equal to $N-1$ ~N-1~ minus the largest $j$ ~j~ such that $a_j \le b_{N-1}-(K-c(N-1-c))$ ~a_j \le b_{N-1}-(K-c(N-1-c))~. As $N \ge 100$ ~N \ge 100~, $a_{N-1} \ge \frac{(N-1)^2-1}{4} > (\log_2(a_{N-1})+5)(N-1-(\log_2(a_{N-1})+5))+\frac{N}{2} > c(N-1-c)+\frac{N}{2}$ . This means that $a_{i+1} > b_{N-1}-(K-a_{N-1}) > b_{N-1}-(K-c(N-1-c))+\frac{N}{2} \ge a_j+\frac{N}{2} > a_{j+1} \implies i > j$ . Hence $Lex(N-1,K-a_{N-1})_0 = N-1-i < N-1-j = Lex(N-1,K-c(N-1-c))_0$ as required.
Finally, note that $Lex(N,k) = Ins(Lex(N-1,k)+1,0,1) < Ins(Lex(N-1,k+1),0,1) = Lex(N,k+1)$ for $0 \le k < b_{N-1}$ ~0 \le k < b_{N-1}~, $Lex(N,b_{N-1}) < Lex(N,b_{N-1}+1)$ ~Lex(N,b_{N-1}) < Lex(N,b_{N-1}+1)~ because $Lex(N,b_{N-1})_0 = 1 < Lex(N,b_{N-1}+1)_0$ , and $Lex(N,k) = Ins(Lex(N-1,k-a_{N-1})+1,\left\lfloor \frac{N-1}{2} \right\rfloor,1) < Ins(Lex(N-1,k+1-a_{N-1})+1,\left\lfloor \frac{N-1}{2} \right\rfloor,1) = Lex(N,k+1)$ for $b_{N-1}+1 \le K < b_N$ ~b_{N-1}+1 \le K < b_N~, so $Lex(N,k) < Lex(N,k+1)$ ~Lex(N,k) < Lex(N,k+1)~ for all $0 \le k < b_N$ ~0 \le k < b_N~ as required.

Therefore by induction, the correctness of this algorithm is proven.

It is easy to simulate inserting the numbers in quadratic time overall.

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

Subtask 3 Optimizations

For subtask 3, we can simulate the above algorithm in linear time using two double-ended queues to store the first and second halves of the partially formed permutation. Whenever the first half grows too large, we move its rightmost element to the left side of the second half.

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

Comments

There are no comments at the moment.