Two Arrays

Research note: I checked the Codeforces problem statement and the Kotlin Heroes 14 editorial. The official tutorial text for 2199D is still listed as Tutorial is loading..., but the published official solution by Roms checks exactly the intersection of the arrays after trimming the first and last positions. The proof below is the actual reason that tiny check works.

First, ignore positions except when comparing final equality. The median depends only on the multiset of chosen values, and for a singleton final array, order is irrelevant anyway.

Two basic facts:

• An operation never creates a value that was not already present.
• The array length decreases by marked_count - 1, which is even, so every array always has odd length.

Define $Good(A)$ as the set of values $x$ such that array $A$ can be transformed into the one-element array $[x]$.

The key lemma is:

For a sorted odd-length array $v_1 \le v_2 \le \dots \le v_k$,

• if $k=1$, then $Good(A)=\{v_1\}$;
• if $k>1$, then $Good(A)$ is exactly the set of values appearing among $v_2,v_3,\dots,v_{k-1}$.

Necessity first. Suppose $k>1$ and a value $x$ does not appear in the middle positions. Then $x$ is either the unique minimum $v_1$ or the unique maximum $v_k$. Consider the unique minimum case; the maximum case is symmetric.

As long as $x$ is present, every other value is greater than $x$. If a real operation marks $x$ together with at least two other elements, then $x$ is the smallest marked element, so it cannot be the median. If the operation marks only $x$, nothing changes. Therefore any operation that actually reduces the array and includes $x$ deletes $x$ forever, while operations not including $x$ keep it as the unique minimum. The final reducing operation cannot output $x$. So a unique endpoint value is impossible. Brutal, but clean.

Now sufficiency. Take any occurrence of $x$ that is not the first or last position. Keep this occurrence alive. It has at least one element on its left and at least one element on its right in sorted order.

While the length is greater than $3$:

• If there are at least three elements to the left of the kept $x$, mark three of them. Their median is still $\le x$, so after replacing them by that median, $x$ still has a left support and the right side is unchanged.
• Else if there are at least three elements to the right, do the symmetric move. The replacement is $\ge x$, so $x$ still has a right support.
• Otherwise, since the total number of elements besides $x$ is even and the length is still greater than $3$, the only remaining case is two elements on each side. Mark the two left elements and one right element. The median is $\le x$, leaving one left support and one right support.

Eventually the array has exactly three elements: one $\le x$, the kept $x$, and one $\ge x$. Mark all three; their median is $x$. Done. This is why the answer is not just the original median. You can burn junk from one side until the target becomes the median. Math, not magic.

Now connect the lemma to the two-array problem.

If the two arrays share some value $x$ in their $Good$ sets, reduce both arrays to $[x]$ and print YES.

Conversely, suppose the arrays can be made equal to some array $C$. If $C$ has length $1$, its only value is reachable from both originals. If $C$ has length greater than $1$, then by the lemma $C$ can be reduced further to some value from its middle positions. Since both originals can reach $C$, both originals can also reach that singleton. So their $Good$ sets must intersect.

So the entire problem collapses to this:

• For an array of length $1$, its reachable range is just its only element.
• For an array of length $>1$, ignore index $0$ and index $n-1$.
• Check whether the two remaining sorted ranges have a common value.

Use two pointers because the arrays are already sorted.

Edge cases:

• $n=m=1$: answer is YES iff the two values are equal.
• Duplicates at the ends are handled correctly by deleting positions, not values. For example, in $[1,1,2]$, value $1$ is reachable because it appears in the middle position.
• One array of length $1$ works naturally: its sole value must appear in the other array's trimmed range.

Complexity is $O(n+m)$ per test case, and $O(n+m)$ memory for storing the arrays. Across all tests this is $O(\sum(n+m))$, easily inside the limits.