The average of a group of numbers always has a value between the minimum and maximum numbers in that group.

Since the average of a group of numbers always has a value between the minimum and maximum numbers in that group, it can be proved that the best approach to obtain the maximum sum of averages of two subsequences is to put the maximum number alone into one subsequence, and the rest of the numbers into the other subsequence. A proof by contradiction follows.

Assume a sorted array, so $$$a_1 \le a_2 \le \ldots \le a_n$$$. Assume that there exists a bigger answer if you take the two greatest numbers (instead of only one) in one subsequence. Therefore, we need to prove that:

$$$\sum_{i=1}^{n-1} a_i / (n - 1) + a_n < \sum_{i=1}^{n-2} a_i / (n - 2) + (a_{n-1} + a_n) / 2$$$

By simplifying the inequality:

$$$a_n < 2 / (n - 1) \cdot \sum_{i=1}^{n-2} a_i / (n - 2) + (n - 3) / (n - 1) \cdot a_{n-1}$$$

Assume $$$avg_1 = \sum_{i=1}^{n-2} a_i / (n - 2)$$$, so $$$a_1 \le avg_1 \le a_{n-2}$$$ as stated at the beginning of the tutorial. The inequality becomes:

$$$a_n < (2 \cdot avg_1 + (n - 3) \cdot a_{n-1}) / (n - 1)$$$

The right-hand side of the inequality is also an average $$$avg_2$$$, such that $$$avg_1 \le avg_2 \le a_{n-1}$$$ (which can be further simplified to $$$a_1 \le avg_2 \le a_{n-1}$$$).

This means that $$$a_n$$$ is strictly less than $$$avg_2$$$. In other words, it states that $$$a_n$$$ is strictly less than a certain number between $$$a_1$$$ and $$$a_{n-1}$$$. This is a contradiction as we stated at the beginning of the proof that the array is sorted ($$$a_n \ge a_{n-1} \ge \ldots \ge a_1$$$). Summing things up, taking at least one number along with the maximum number will never yield a greater answer.

125412783

You can ignore the $$$k$$$ given in the input, try to find the minimum $$$k$$$ you need to sort the array (let call it $$$mnK$$$).

If $$$mnK$$$ $$$\le$$$ $$$k$$$ then you can split some subarrays to make it equal $$$k$$$, so the answer is will be "YES". otherwise, the answer will be "NO".

You need to split the array into the minimum number of subarrays such that each subarray is sorted.

This problem can be solved for \textbf{at least} $$$k$$$ subarrays as it is easy to just add extra subarrays (if needed) to achieve \textbf{exactly} $$$k$$$ subarrays. To solve this problem, you need to know what are the numbers that can be grouped into the same subarray. This can be done by maintaining the sorted array along with the non-sorted array.

As the numbers are distinct, we can iterate over the non-sorted array, and just add each element $$$a_i$$$ to the subarray ending in $$$a_{i - 1}$$$ IFF they follow each other in the sorted array, or start a new subarray if they do not follow each other.

For example, if the (non-sorted) array is $$$[$$$ $$$2$$$, $$$3$$$, $$$ -1$$$, $$$1$$$], the sorted array will be $$$[$$$ $$$-1$$$, $$$1$$$, $$$2$$$, $$$3$$$ $$$]$$$. If we iterate over the non-sorted array, we will add $$$2$$$ to a new subarray, then we will add $$$3$$$ to the same subarray as they follow each other in the sorted array. After that, we will start a new subarray at $$$-1$$$ as $$$-1$$$ and $$$3$$$ do not follow each other in the sorted array. Finally, we will add $$$1$$$ to the subarray containing $$$-1$$$. It should end up like this: { $$$[$$$ $$$2$$$, $$$3$$$ $$$]$$$, $$$[$$$ $$$-1$$$, $$$1$$$ $$$]$$$ }.

Using this approach, you can get the smallest number of subarrays needed. If it is strictly greater than the given $$$k$$$, the answer is ''NO''. Otherwise, it is ''YES''.

125412883

We don't care about the values in the array to know it's valid or not, we just need to know for every bit how many numbers have this bit on or off.

Try to build the array from the most significant bit ($$$k-1$$$) to the least significant bit $$$0$$$ using dynamic programming.

Can you optimize dynamic programming code with some combinatorics?

From now on, I will use $$$And$$$ to describe the result of the bitwise AND operation over all the elements in the array, and $$$Xor$$$ to describe the result of the bitwise XOR operation over all the elements in the array.

Let's call the array is valid if the value of $$$And$$$ $$$\ge$$$ $$$Xor$$$.

We don't care about the values in the array. We just need to know, for every bit, the number of indices at which this bit is on or off.

So let's build the array from the most significant bit ($$$k-1$$$) to the least significant bit ($$$0$$$) using dynamic programming and combinatorics optimization.

Define an array $$$dp$$$ where $$$dp_{i, equal}$$$ $$$=$$$ the number of ways to build the array from the $$$i$$$-th bit to $$$0$$$-th bit. $$$equal$$$ is $$$true$$$ if $$$And$$$ $$$=$$$ $$$Xor$$$ in the previous bits, and $$$false$$$ if $$$And$$$ $$$>$$$ $$$Xor$$$ ($$$And$$$ $$$<$$$ $$$Xor$$$ is not a valid state).

Our base case is $$$dp_{-1,0}$$$ $$$=$$$ $$$1$$$, and $$$dp_{-1,1}$$$ $$$=$$$ $$$1$$$.

• If $$$equal$$$ is $$$false$$$ at any moment, then you can choose any subset of indices to contain $$$1$$$ in the $$$i$$$-th bit.

  Therefore, $$$dp_{i,0}$$$ $$$=$$$ $$$2^n$$$ $$$\cdot$$$ $$$dp_{i-1,0}$$$.

• Now if $$$n$$$ is odd there are $$$2$$$ possible choices:

  1. You can make $$$i$$$-th bit $$$=$$$ $$$1$$$ in an even number of indices, then $$$And_i$$$ will be $$$0$$$ and $$$Xor_i$$$ will be $$$0$$$ too.
  2. You can make $$$i$$$-th bit $$$=$$$ $$$1$$$ in all indices, then $$$And_i$$$ will be $$$1$$$ and $$$Xor_i$$$ will be $$$1$$$ too.

  You Don't have any other valid choices. So $$$dp_{i,1}$$$ $$$=$$$ $$$dp_{i-1,1}$$$ $$$\cdot$$$ ({number of ways to choose number of indices from $$$n$$$} $$$+$$$ $$$1$$$). ($$$+1$$$ for the second choice).

• If $$$n$$$ is even there are $$$2$$$ possible choices:

  1. You can make $$$i$$$-th bit $$$=$$$ $$$1$$$ in an even number (less than $$$n$$$) of indices, then $$$And_i$$$ will be $$$0$$$ and $$$Xor_i$$$ will be $$$0$$$ also.
  2. You can make $$$i$$$-th bit $$$=$$$ $$$1$$$ in all indices, then $$$And_i$$$ will be $$$1$$$ and $$$Xor_i$$$ will be $$$0$$$. and now $$$equal$$$ will be $$$false$$$.

  You Don't have any other valid choices. So $$$dp_{i,1}$$$ $$$=$$$ $$$dp_{i-1,1}$$$ $$$\cdot$$$ (number of ways to choose number of indices from $$$n$$$ ) + $$$dp_{i-1,0}$$$.

We can precalculate the factorial, to get $$$nCr$$$ in $$$\mathcal{O}(1)$$$, and then calculate the number of ways to choose an even number from $$$n$$$ before starting the $$$dp$$$. The total complexity will be $$$\mathcal{O}(k + n)$$$.

125412943

Try to count the maximum number of rows that makes a beautiful grid, and remove the others.

Can you get some dynamic programming formula, and then optimize it with some ranges data structures?

We can use dynamic programming to get the maximum number of rows that make a beautiful grid.

Define the 2d array, $$$dp$$$, where $$$dp_{i,j}$$$ $$$=$$$ maximum number of rows (from row $$$1$$$ to row $$$i$$$) that make a beautiful grid, and has $$$1$$$ in column $$$j$$$ at the last row I have in the biggest beautiful grid. the last row in the biggest beautiful grid is the not necessary to be $$$i$$$

Form the definition:

• $$$dp_{0,j}$$$ $$$=$$$ $$$0$$$.

• $$$dp_{i,j}$$$ $$$=$$$ $$$1$$$ $$$+$$$ $$$\max_{k \in C_i}$$$ {$$$dp_{i-1,k}$$$} if $$$grid_{i,j}$$$ $$$=$$$ $$$1$$$.

• Otherwise, if $$$grid_{i,j}$$$ $$$\neq$$$ $$$1$$$, then $$$dp_{i,j}$$$ $$$=$$$ $$$dp_{i-1,j}$$$ .

where $$$C_i$$$ is that set of columns that contain $$$1$$$ in row $$$i$$$.

As you know, the set $$$C_i$$$ contains the intervals, so we just search in some intervals for the maximum, or update some intervals in the previous layer in $$$dp$$$. We can do it faster using Segment tree.

So the algorithm will be as follows:

• Define an array $$$prev$$$, where $$$prev_i$$$ $$$=$$$ the previous row of $$$i$$$ in which maximum beautiful grid end with $$$i$$$-th row. We will use it to get the rows that will not be removed.

• Build a segment tree of pairs ($$$value$$$, $$$index$$$) initially with { $$$0$$$ , $$$-1$$$ }.

• Then for each $$$i$$$ from $$$1$$$ to $$$n$$$:

  • Get the maximum value in all the ranges $$$[l_j,r_j]$$$ that contains $$$1$$$ at the $$$i$$$-th row. Let's call it $$$mx$$$.
  • Store $$$prev_{i}$$$ $$$=$$$ $$$mx.index$$$.
  • Update all the ranges $$$[l_j,r_j]$$$ of this row like this: $$$seg_j$$$ $$$=$$$ $$$max($$$ $$$seg_j$$$ $$$,$$$ { $$$mx.value$$$ $$$+$$$ $$$1$$$ $$$,$$$ $$$i$$$ }).
  • Finally, get the rows that have the maximum value using the $$$prev$$$ array, and remove the others.

The total complexity will be $$$\mathcal{O}(n + m\log{}10^9)$$$ or $$$\mathcal{O}(n + m\log{}m)$$$ if you make a coordinate compression to the values.

125412981

Try to force the king to move into one of the corners down.

If you put the queen in a row $$$x$$$, move the queen to the left of the row, then start swiping the row right, one square at a time. If you've visited all $$$8$$$ squares on the row and the king never made a vertical move, it means $$$|$$$ current king row $$$-$$$ current queen row $$$|$$$ $$$\ge 2$$$ (if the king were on row ($$$x + 1$$$\$$$x-1$$$), he would've been forced to move $$$1$$$ square (down\up) at some point).

This is one of many possible solutions. We need to force the king to move into one of the four corners (bottom right or bottom left corner in this solution) to ensure that the king will be trapped (cannot move anymore).

Place the queen on the top row. After the king makes a $$$1$$$ move, he should be below the queen's row.

Suppose the queen is on the row $$$x$$$ with the king below it (row $$$x$$$ $$$+$$$ $$$i$$$ where $$$i$$$ > $$$0$$$).

If $$$i$$$ $$$=$$$ $$$1$$$, we cannot move down to the next row as the king may move up and we will not be able to trap it. Otherwise, we can move down by one unit.

To ensure that the king is not on the next row, scan the current row, $$$x$$$, by moving the queen from the leftmost column to the rightmost column one square at a time. Therefore, you can move the queen as follows:

1. During the scan, if you have visited all $$$8$$$ squares of the current row and the king never made a vertical or diagonal move, it means that $$$i \ge 2$$$ and you can go down by one row. It is now guaranteed that the king is still below the queen.

2. If the king were on row $$$x$$$ $$$+$$$ $$$1$$$, he would have been forced to move $$$1$$$ square down at some point. If he ever goes down, move the queen down by one row.

3. If the king moves up, start scanning the row again. This can only happen a limited number of times without the king moving into a check.

In total, the queen needs to apply step $$$2$$$ up to $$$8$$$ times. At each row, step $$$1$$$ needs to be applied, so it takes $$$8$$$ moves. Step $$$1$$$ also needs to be applied every time step $$$3$$$ is applied, which can happen at most $$$8$$$ times. In total, that is $$$8$$$ $$$\cdot$$$ $$$(8$$$ $$$+$$$ $$$8)$$$ $$$=$$$ $$$128$$$ moves.

125413044