Let the stick lengths be $$$X, Y, Z$$$. The broken stick $$$X$$$ either forms two parallel sides or two perpendicular sides. In the first case, $$$X$$$ is even and $$$Y == Z$$$. In the second case, $$$X == Y+Z$$$. We try all choices of $$$X$$$.
Say we dislike $$$L$$$ songs — those $$$L$$$ songs must have unique ratings $$$q_i$$$ from $$$1$$$ to $$$L$$$. To minimize the sum of $$$|p_i - q_i|$$$, we should keep $$$q_i$$$ in the same order as $$$p_i$$$.
Optimal strategies can be described by $$$(x, k)$$$: decrease the lowest value by $$$x$$$, then set the largest $$$k$$$ values to the lowest value.
Let $$$M$$$ be the lowest value. For each $$$k = A[..i]$$$, let's find the least $$$x$$$ that we need. For $$$k = 0$$$, it is just $$$\max(0, \text{sum}(A) - K)$$$. For other $$$k$$$'s, we have the equation $$$(M-x) * (i+2) + \text{sum}(A[i+1 : -1]) \leq K$$$ which can be solved.
We try to classify all valid strings into disjoint sets to count them. Let $$$X_i$$$ be the set of all valid strings $$$t$$$ where $$$i$$$ is the last position where $$$s[i]$$$ and $$$t[i]$$$ differ. The answer is $$$1 + \sum_i X_i$$$.
To count $$$X_j$$$, let $$$i$$$ be the lowest index so that $$$s[i..j]$$$ contains $$$k$$$ ones. If this exists, then we either have $$$j-i$$$ spaces to fit $$$k$$$ or $$$k-1$$$ ones depending on the value of $$$s[j]$$$ (it must change).
First, $$$r_i = \sum_j s_{i,j} p_j$$$.
Now, observe $$$|x| = \max(x, -x)$$$, and $$$|x| + |y| = \max(x + y, x - y, -x + y, -x - y)$$$, etc. Using this idea, we can find the maximum surprise as the max over all $$$2^n$$$ possibilities of replacing $$$|x_i - r_i|$$$ with $$$x - r$$$ or $$$r - x$$$. This results in a sum of the form $$$c_0 + c_1 * p_1 + \cdots + c_n * p_n$$$, for which the best permutation can be chosen greedily (by the rearrangement inequality.)
Brute forcing small values, it seems we remove at most 3 values, so let's focus on removals.
Represent every prime as a random bitmask $$$\text{mask}(P)$$$. Then with $$$\text{mask}(X * Y) = \text{mask}(X) \oplus \text{mask}(Y)$$$, we can check whether a number is probably a square with $$$\text{mask}(X) = 0$$$.
Now we can use this trivially to solve for any $$$n$$$ with $$$\leq 2$$$ removals. For the others, try removing $$$n$$$ then applying the procedure again — we can check that this works, so every answer has $$$\leq 3$$$ removals and we've found the optimal answer for all $$$n$$$.
For problem F, here's another proof that the answer is at least $$$n-3$$$:
For a number $$$x=\prod_{i} p_i^{\alpha_i}$$$, let $$$f(x) = \prod_i p_i^{\alpha_i \bmod 2}$$$. Then $$$x$$$ is a perfect square if and only if $$$f(x) = 1$$$.
Note that for any numbers $$$x,y$$$, we have $$$f(xy) = f(f(x)f(y))$$$, and furthermore, $$$f(x^2y) = f(y)$$$. It shows that $$$f(n! \cdot (n+1)!) = f((n!)^2 \cdot (n+1)) = f(n+1)$$$.
Assume that $$$n=2k$$$ is an even number. If we choose all the numbers from $$$[1,n]$$$, we will get $$$f(1! \cdot 2! \cdot \cdots \cdot (2k-1)! \cdot (2k)!) = f(2 \cdot 4 \cdot \dots \cdot (2k)) = f(2^k \cdot k!)$$$.
From the above, we can always find a solution of size at least $$$n-2$$$ for an even number of $$$n$$$. When $$$n=2k+1$$$ is an odd number, we can just ignore the number $$$n$$$, and follow the above construction. We ignored one number, and we threw at most $$$2$$$ numbers, so we can always find a set that contains at least $$$n-3$$$ numbers.
Thanks. I have thought F for a long time but I can't solve it. Thanks for your proof.
And I wonder that why you consider that $$$answer\ge n-3$$$. In another words, why do you think that the answer is so large like this?
Thanks in advance.
Write a brute force such as enumerating subsets and you will find it XD.