Codeforces
CF Step
Youtube Linkedin Discord Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Back to homepage
  1. Home
  2. /
  3. Codeforces
  4. /
  5. Contests
  6. /
  7. EPIC Institute of Technology Round Summer 2025 (Codeforces Round 1036, Div. 1 + Div. 2)
  8. /
  9. D. Make a Palindrome
  10. /
  11. Hints: Make a Palindrome

Hints: Make a Palindrome

The operation is scary at first: “pick any window of length $\ge k$, remove its $k$-th smallest value.” Let’s tame it.

Sort the array mentally and let $V$ be the $k$-th smallest value in the original $a$. That value $V$ splits $a$ into two kinds of entries:

  • entries with value $> V$ (there are exactly $n - k$ of these in sorted order, though some of value $V$ may tie with the boundary),
  • entries with value $\le V$ (there are at least $k$ of these).

Question: do you really need to worry about the entries whose value is $> V$? Can operations always get rid of them?

Answer to Hint 1: Yes — any entry with value $> V$ can always be removed. Intuition: to delete an entry $x$ you need a window of length $\ge k$ where $x$ is the $k$-th smallest. Since there are at least $k$ entries of value $\le V$ in the array, and $x > V$, you can always arrange a window containing $x$ together with $k-1$ entries of value $\le V$. In that window $x$ is among the largest, so you can pick $x$ as the $k$-th smallest and delete it. (If they aren’t adjacent yet, delete other “$> V$” entries first in any order; an inductive argument shows it’s always possible.)

So without loss of generality, assume we begin by deleting every entry with value $> V$. Let

$$c = [\,a_i : a_i \le V\,],$$

taken in the original order. The problem now lives entirely on $c$ (with $|c| \ge k$).

What do operations look like inside $c$? Which of $c$’s entries can you still delete?

Answer to Hint 2: The maximum value in $c$ is exactly $V$. An operation on a window of $c$ of length $\ge k$ removes the window’s $k$-th smallest. Since every entry of $c$ is $\le V$, the $k$-th smallest of any window is also $\le V$.

Claim: in this reduced problem, the only entries you can reliably delete from $c$ are those equal to $V$.

  • Entries of value $< V$ are “protected”: in any window of length $\ge k$, there are enough entries of value $\ge$ them (indeed, enough entries of value exactly $V$ among the top of the window) that you’d end up deleting a $V$-entry instead of them.
  • Entries of value $= V$ are deletable: put such an entry at the top of a length-$k$ window that also contains $k-1$ of the smaller entries; then this $V$-entry is the $k$-th smallest.

You can accept this as a lemma. Think about why the greedy that deletes only $V$-valued entries is enough: is there ever a benefit to deleting a smaller entry?

How does this reshape the original question about palindromes?

Answer to Hint 3: The problem becomes:

You have the sequence $c$. You may delete any subset of the entries equal to $V$. Is the remaining sequence a palindrome?

Almost. There is one more constraint you must not forget — it comes from how many operations you’re allowed to perform.

What is the smallest length the array can possibly reach?

Answer to Hint 4: Every operation requires the current length to be $\ge k$ (that’s the “window of length $\ge k$” rule). So each operation turns a length-$L$ array (with $L \ge k$) into a length-$(L-1)$ array. The smallest length you can ever reach is $k - 1$ (reached from length $k$). You cannot go below $k - 1$.

So the final palindrome’s length must satisfy $L_{\text{final}} \ge k - 1$.

Putting it together, your algorithm has to decide: can we delete some subset of the $V$-entries from $c$ so that what remains is a palindrome of length at least $k - 1$?

What’s a natural way to check this?

Answer to Hint 5: Two pointers. Let $l = 0$ and $r = |c|$. Walk inward:

  • If $c[l] = c[r - 1]$: great, these are the outer pair of the palindrome. Do $l{+}{+}$, $r{-}{-}$ and recurse.
  • If $c[l] \ne c[r - 1]$: the mismatch must be resolved by deleting one of them. The only entries we’re allowed to delete are those equal to $V$.
    • If $c[l] = V$: delete $c[l]$ (advance $l$, increment deletion counter).
    • Otherwise, if $c[r - 1] = V$: delete $c[r - 1]$ (retract $r$, increment deletion counter).
    • Otherwise: neither endpoint equals $V$ and they don’t match — impossible.

This greedy is safe: when there is a choice, deleting the $V$-entry on the mismatching side is forced (the other side’s entry is smaller-than-$V$, and we cannot delete small entries).

Why is this greedy correct when both endpoints equal $V$ but we still choose to match them instead of delete?

Answer to Hint 6: If $c[l] = c[r - 1] = V$, matching them is strictly better than deleting. Matching keeps two entries (length stays $L$, no operation used), while deleting removes one (costs an operation and shortens the final array). Shortening can only make the length constraint harder and cannot help anywhere else, so we never prefer deleting over a legal match.

Also, when $c[l] \ne c[r - 1]$ and both sides have $V$-entries at other positions, we only ever need to consider the current endpoint — if the current-left is $V$, deleting it strictly simplifies the prefix; and symmetrically on the right.

Now turn the procedure into a clean termination check.

Answer to Hint 7: After the two-pointer terminates (either $l \ge r$, or we hit the impossible case), let

$$\mathrm{rm} = (\text{number of } V\text{-entries deleted during the walk}).$$

The remaining palindrome has length

$$L_{\text{final}} = |c| - \mathrm{rm}.$$

Output YES iff the loop did not hit the impossible case and $L_{\text{final}} \ge k - 1$. Otherwise NO.

(If your loop stores a sentinel like $\mathrm{rm} = n + 1$ on the impossible case, a single final comparison $|c| - \mathrm{rm} \ge k - 1$ handles both conditions at once.)

Now reduce it to code.

Answer to Hint 8: Implementation outline, per test case:

  1. Read $n$, $k$, and $a$.
  2. Compute $V$: copy $a$ to $b$, sort $b$, take $V = b[k - 1]$ (the $k$-th smallest, $1$-indexed).
  3. Build $c$: iterate over $a$ in order and append each $a_i$ with $a_i \le V$.
  4. Two-pointer on $c$ with $l = 0$, $r = |c|$, $\mathrm{rm} = 0$:
    • while $l < r$:
      • if $c[l] = c[r - 1]$: $l{+}{+}$, $r{-}{-}$;
      • else if $c[l] = V$: $l{+}{+}$, $\mathrm{rm}{+}{+}$;
      • else if $c[r - 1] = V$: $r{-}{-}$, $\mathrm{rm}{+}{+}$;
      • else: mark impossible (e.g. $\mathrm{rm} \gets n + 1$) and break.
  5. Output YES iff $|c| - \mathrm{rm} \ge k - 1$, else NO.

Complexity: $O(n \log n)$ per test case from the sort; the rest is linear. With $\sum n \le 2 \cdot 10^5$, this is comfortably fast.

Answer to Hint 9 (sanity checks with the samples):

  • $a = [5,4,3,4,5]$, $k = 3$: sorted $[3,4,4,5,5]$, $V = 4$. $c = [4,3,4]$. Two-pointer: $4 = 4$ match; middle $3$ alone. $\mathrm{rm} = 0$, length $3 \ge 2$. YES.
  • $a = [5,2,4,3,1]$, $k = 4$: sorted $[1,2,3,4,5]$, $V = 4$. $c = [2,4,3,1]$. Endpoints $2$ vs $1$, neither equals $V$: impossible. NO.
  • $a = [1,2,1,2,2]$, $k = 4$: sorted $[1,1,2,2,2]$, $V = 2$. $c = [1,2,1,2,2]$. Endpoints $1$ vs $2$: right is $V$, delete it ($\mathrm{rm} = 1$). Now $[1,2,1,2]$ — endpoints $1$ vs $2$: delete right ($\mathrm{rm} = 2$). Now $[1,2,1]$ — $1 = 1$ match, middle $2$. Length $= 5 - 2 = 3 \ge 3$. YES.

Everything matches the expected outputs.