The editorial video for Codeforces Round 1137 (Div. 2) is now available here.
Do check out the ihatecp.com.
2289A - Problem from Dolgoderevenskoye
What are we really counting here? Focus on the number of odd divisors vs even divisors of $$$x$$$.
Artem moves first and can choose any parity. He'll pick the parity with more divisors!
The second player wins only if the count of odd divisors equals the count of even divisors.
Case 1: If $$$x$$$ is odd, what can we say about all its divisors?
All divisors of an odd number are odd. Artem chooses an odd card, and the second player has no even cards to play. Artem wins immediately.
Case 2: If $$$x \equiv 2 \pmod{4}$$$ (divisible by 2 but not by 4).
For every divisor $$$i$$$ of $$$x$$$, we also have $$$2i$$$ as a divisor.
This means: odd divisors and even divisors come in pairs.
The counts are equal → second player wins!
Case 3: If $$$x \equiv 0 \pmod{4}$$$ (divisible by 4 or higher power of 2).
For every divisor $$$i$$$, we have both $$$2i$$$ and $$$4i$$$ as divisors.
This creates more even divisors than odd divisors.
Artem chooses even parity and wins!
Final answer:
• $$$x$$$ is odd → YES
• $$$x \equiv 2 \pmod{4}$$$ → NO
• $$$x \equiv 0 \pmod{4}$$$ → YES
My submission — 399479055
2289B - Problem from Chebarkul
Focus on the $$$i$$$-th element of sequence $$$B$$$ (the chosen subsequence).
What is the earliest index in $$$A$$$ that $$$B[i]$$$ can come from?
The $$$i$$$-th element of $$$B$$$ needs at least $$$i-1$$$ elements before it in $$$A$$$.
So $$$B[i]$$$ cannot come from indices $$$1$$$ to $$$i-1$$$ in $$$A$$$.
Earliest possible: $$$B[i] = A[i]$$$
What is the latest index in $$$A$$$ that $$$B[i]$$$ can come from?
We need $$$k - i$$$ elements after $$$B[i]$$$ in the subsequence.
So the last $$$k - i$$$ elements of $$$A$$$ cannot be chosen as $$$B[i]$$$.
Latest possible: $$$B[i] = A[n - (k - i)]$$$
Can we actually achieve any element in this range?
Yes! Choose:
• First $$$i - 1$$$ elements from $$$A$$$ (for positions before $$$B[i]$$$)
• Last $$$k - i$$$ elements from $$$A$$$ (for positions after $$$B[i]$$$)
• Any one element in between for $$$B[i]$$$
This construction works for any index in the valid range.
So $$$B[i]$$$ can be any element from index $$$i$$$ to index $$$n - (k - i)$$$ in $$$A$$$.
Let's simplify this: $$$n - (k - i) = n - k + i$$$
So the range is: $$$A[i], A[i+1], A[i+2], \ldots, A[i + n - k]$$$
That's exactly $$$n - k + 1$$$ consecutive elements!
$$$B[i]$$$ will always have the same value if and only if all elements from $$$A[i]$$$ to $$$A[i + n - k]$$$ are equal.
Problem reduces to: count how many indices $$$i$$$ have all elements equal in the range $$$[i, i + n - k]$$$.
Solution 1: Sliding Window with Frequency Map
Maintain a frequency map for a window of size $$$n - k + 1$$$:
• Add $$$A[i]$$$ when it enters the window
• Remove $$$A[i - (n-k+1)]$$$ when it exits
• If map has only 1 unique value, all elements in window are equal
Iterate through all positions and count windows where the map size equals 1.
Time complexity: $$$O(n \log n)$$$ due to map operations.
Solution 2: Prefix Sum Trick
Let's make an array $$$b$$$ where $$$b[i]$$$ marks if $$$A[i]$$$ is different from $$$A[i-1]$$$. Set $$$b[0] = 0$$$, and:
For example, if $$$A = [3, 3, 5, 5, 5, 2]$$$, we get $$$b = [0, 0, 1, 0, 0, 1]$$$
Compute prefix sums as usual: $$$prefix[i] = b[0] + b[1] + ... + b[i]$$$
Now here's the neat part: a range $$$[L, R]$$$ has all equal elements exactly when there are no "changes" inside it. In other words, the range sum should be zero.
So for range $$$[i, i + n - k]$$$, we just check if $$$prefix[i + n - k] - prefix[i] = 0$$$. That's it!
This runs in $$$O(n)$$$ which is faster than the map approach.
My submission — 399480552
2289C - Problem from Ust-Katav
Consider a subarray. Let $$$m$$$ be the index of the minimum element, and $$$p_m$$$ be its value.
For which subarrays is the element at position $$$m$$$ (value $$$p_m$$$) the minimum?
Look at it from the perspective of position $$$m$$$.
Let $$$\ell$$$ be the number of elements between $$$m$$$ and the nearest element smaller than $$$p_m$$$ on the left (or the array boundary). Similarly, let $$$r$$$ be the count on the right.
Key insight: If you choose the left endpoint anywhere among those $$$\ell$$$ elements and the right endpoint anywhere among those $$$r$$$ elements, then the element at $$$m$$$ (value $$$p_m$$$) will be the minimum.
These are the ONLY subarrays where the element at position $$$m$$$ is the minimum.
Two subarrays will definitely have the element at $$$m$$$ as the minimum:
1. Length 1: Just the element at position $$$m$$$ (value $$$p_m$$$)
2. Length $$$\ell + r + 1$$$: The full span from the left boundary to the right boundary
Why don't other lengths work? Let's check length $$$\ell + r$$$:
• If we include the leftmost element (start from left boundary), the subarray still has $$$m$$$ as minimum
• If we include the rightmost element (end at right boundary), the subarray also has $$$m$$$ as minimum
We found two different subarrays of the same length with the same minimum! So these can't be counted separately.
Similarly, for any length between 2 and $$$\ell + r$$$, there are multiple subarrays of that length with $$$m$$$ as the minimum. Only lengths 1 and $$$\ell + r + 1$$$ give us a unique subarray.
But wait, this proof works only when we can move both left and right. What if $$$\ell = 0$$$ or $$$r = 0$$$?
Edge case: When the element is at a boundary.
If $$$\ell = 0$$$ (no smaller element on the left):
• Any subarray starting at $$$m$$$ and extending to the right will have $$$m$$$ as minimum
• Count: $$$r + 1$$$ subarrays (lengths 1, 2, 3, ..., $$$r + 1$$$)
Similarly, if $$$r = 0$$$ (no smaller element on the right):
• Any subarray ending at $$$m$$$ will have $$$m$$$ as minimum
• Count: $$$\ell + 1$$$ subarrays
In these cases, all lengths from 1 to $$$\ell + r + 1$$$ work!
Algorithm: Process elements in increasing order of their values.
For each element, find the nearest smaller element on left and right to get $$$\ell$$$ and $$$r$$$. Then:
• If $$$\ell = 0$$$ or $$$r = 0$$$: add $$$\ell + r + 1$$$
• Otherwise: add 2
Alternative approach: Use a monotonic stack to find the nearest smaller element on each side efficiently.
This avoids sorting and runs in $$$O(n)$$$ instead of $$$O(n \log n)$$$.
My submission — 399481725
2289D - Problem from Yuzhnouralsk
Let's trace through what happens when we apply operations on a sample array.
Initial array: $$$[a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8]$$$
After $$$\text{op}(5)$$$:
• $$$a_4 \gets a_4 + a_5$$$ (add to left neighbor)
• $$$a_6 \gets a_6 + a_5$$$ (add to right neighbor)
• $$$a_5 \gets -a_5$$$ (negate)
Array: $$$[a_1, a_2, a_3, \color{blue}{a_4+a_5}, \color{red}{-a_5}, \color{blue}{a_6+a_5}, a_7, a_8]$$$
After $$$\text{op}(4)$$$:
• $$$a_3 \gets a_3 + (a_4+a_5)$$$
• $$$a_5 \gets (-a_5) + (a_4+a_5) = a_4$$$
• $$$a_4 \gets -(a_4+a_5)$$$
Array: $$$[a_1, a_2, \color{blue}{a_3+a_4+a_5}, \color{red}{-(a_4+a_5)}, \color{blue}{a_4}, a_6+a_5, a_7, a_8]$$$
After $$$\text{op}(3)$$$:
• $$$a_2 \gets a_2 + (a_3+a_4+a_5)$$$
• $$$a_4 \gets (-(a_4+a_5)) + (a_3+a_4+a_5) = a_3$$$
• $$$a_3 \gets -(a_3+a_4+a_5)$$$
Array: $$$[a_1, \color{blue}{a_2+a_3+a_4+a_5}, \color{red}{-(a_3+a_4+a_5)}, \color{blue}{a_3}, a_4, a_6+a_5, a_7, a_8]$$$
After $$$\text{op}(6)$$$:
• $$$a_5 \gets a_4 + (a_6+a_5) = a_4+a_5+a_6$$$
• $$$a_7 \gets a_7 + (a_6+a_5)$$$
• $$$a_6 \gets -(a_6+a_5)$$$
Array: $$$[a_1, a_2+a_3+a_4+a_5, -(a_3+a_4+a_5), a_3, \color{blue}{a_4+a_5+a_6}, \color{red}{-(a_5+a_6)}, \color{blue}{a_7+a_5+a_6}, a_8]$$$
Notice the pattern? Each element becomes a sum of contiguous original elements!
For example, after these operations:
• $$$a_2 = a_2+a_3+a_4+a_5$$$ (sum of elements 2-5)
• $$$a_3 = -(a_3+a_4+a_5)$$$ (negated sum)
• $$$a_5 = a_4+a_5+a_6$$$ (sum of elements 4-6)
Every element is essentially a subarray sum, possibly negated. Whenever we see subarray sums, we should think about prefix sums!
Whenever we see subarray sums, we should think about prefix sums!
Let's define prefix sums: $$$p_0 = 0$$$, $$$p_i = a_1 + a_2 + ... + a_i$$$
Then: $$$a_i = p_i - p_{i-1}$$$
Let's rewrite our array in terms of prefix sum differences and apply the same operations.
Let's trace the same operations in terms of prefix sum differences.
Initial: $$$[p_1-p_0, p_2-p_1, p_3-p_2, p_4-p_3, p_5-p_4, p_6-p_5, p_7-p_6, p_8-p_7]$$$
Prefix array: $$$[p_0, p_1, p_2, p_3, p_4, p_5, p_6, p_7, p_8]$$$
After $$$\text{op}(5)$$$:
• $$$a_4 = (p_4-p_3) + (p_5-p_4) = p_5-p_3$$$
• $$$a_5 = -(p_5-p_4) = p_4-p_5$$$
• $$$a_6 = (p_6-p_5) + (p_5-p_4) = p_6-p_4$$$
Array: $$$[p_1-p_0, p_2-p_1, p_3-p_2, p_5-p_3, p_4-p_5, p_6-p_4, p_7-p_6, p_8-p_7]$$$
Prefix array: $$$[p_0, p_1, p_2, p_3, \color{red}{p_5}, \color{blue}{p_4}, p_6, p_7, p_8]$$$ (swapped $$$\color{blue}{p_4} \leftrightarrow \color{red}{p_5}$$$)
After $$$\text{op}(4)$$$:
• $$$a_3 = (p_3-p_2) + (p_5-p_3) = p_5-p_2$$$
• $$$a_4 = -(p_5-p_3) = p_3-p_5$$$
• $$$a_5 = (p_4-p_5) + (p_5-p_3) = p_4-p_3$$$
Array: $$$[p_1-p_0, p_2-p_1, p_5-p_2, p_3-p_5, p_4-p_3, p_6-p_4, p_7-p_6, p_8-p_7]$$$
Prefix array: $$$[p_0, p_1, p_2, \color{red}{p_5}, \color{blue}{p_3}, p_4, p_6, p_7, p_8]$$$ (swapped $$$\color{blue}{p_3} \leftrightarrow \color{red}{p_5}$$$)
After $$$\text{op}(3)$$$:
• $$$a_2 = (p_2-p_1) + (p_5-p_2) = p_5-p_1$$$
• $$$a_3 = -(p_5-p_2) = p_2-p_5$$$
• $$$a_4 = (p_3-p_5) + (p_5-p_2) = p_3-p_2$$$
Array: $$$[p_1-p_0, p_5-p_1, p_2-p_5, p_3-p_2, p_4-p_3, p_6-p_4, p_7-p_6, p_8-p_7]$$$
Prefix array: $$$[p_0, p_1, \color{red}{p_5}, \color{blue}{p_2}, p_3, p_4, p_6, p_7, p_8]$$$ (swapped $$$\color{blue}{p_2} \leftrightarrow \color{red}{p_5}$$$)
After $$$\text{op}(6)$$$:
• $$$a_5 = (p_4-p_3) + (p_6-p_4) = p_6-p_3$$$
• $$$a_6 = -(p_6-p_4) = p_4-p_6$$$
• $$$a_7 = (p_7-p_6) + (p_6-p_4) = p_7-p_4$$$
Array: $$$[p_1-p_0, p_5-p_1, p_2-p_5, p_3-p_2, p_6-p_3, p_4-p_6, p_7-p_4, p_8-p_7]$$$
Prefix array: $$$[p_0, p_1, p_5, p_2, p_3, \color{red}{p_6}, \color{blue}{p_4}, p_7, p_8]$$$ (swapped $$$\color{blue}{p_4} \leftrightarrow \color{red}{p_6}$$$)
Key observation: Look at what happens to the prefix array itself!
Initial prefix array: $$$[p_0, p_1, p_2, p_3, p_4, p_5, p_6, p_7, p_8]$$$
After $$$\text{op}(5)$$$: $$$[p_0, p_1, p_2, p_3, \color{green}{p_5, p_4}, p_6, p_7, p_8]$$$ (swapped $$$p_4 \leftrightarrow p_5$$$)
After $$$\text{op}(4)$$$: $$$[p_0, p_1, p_2, \color{green}{p_5, p_3}, p_4, p_6, p_7, p_8]$$$ (swapped $$$p_3 \leftrightarrow p_5$$$)
After $$$\text{op}(3)$$$: $$$[p_0, p_1, \color{green}{p_5, p_2}, p_3, p_4, p_6, p_7, p_8]$$$ (swapped $$$p_2 \leftrightarrow p_5$$$)
After $$$\text{op}(6)$$$: $$$[p_0, p_1, p_5, p_2, p_3, \color{green}{p_6, p_4}, p_7, p_8]$$$ (swapped $$$p_4 \leftrightarrow p_6$$$)
Operation $$$\text{op}(i)$$$ swaps adjacent elements $$$p_{i-1}$$$ and $$$p_i$$$ in the prefix array!
With the observation that operations swap adjacent prefix sums:
For the array to have all non-negative increasing elements, we need:
$$$a[0] \geq 0, a[1] \geq 0, ..., a[n-1] \geq 0$$$ and $$$a[0] \leq a[1] \leq ... \leq a[n-1]$$$
In terms of prefix sums:
$$$p[1] - p[0] \geq 0$$$, $$$p[2] - p[1] \geq 0$$$, ...
This means: $$$p[0] \leq p[1] \leq p[2] \leq ... \leq p[n]$$$
We need to sort the prefix sums in increasing order!
But wait! First check: can we even achieve non-negative values?
For all $$$a[i] \geq 0$$$, we need all prefix sums to be non-negative.
If any $$$p[i] \lt 0$$$, it's impossible → output $$$-1$$$.
Otherwise, we need to count: how many swaps to sort the prefix sums?
Now we're left with: take adjacent elements from prefix sums and swap them repeatedly until the array is sorted.
This is exactly the Bubble Sort algorithm!
How many swaps does bubble sort need?
Consider: we've already sorted elements from index 0 to $$$i$$$, and now we need to insert $$$p[i+1]$$$ into its correct position.
The number of swaps needed = number of elements in $$${p[0], p[1], ..., p[i]}$$$ that are greater than $$$p[i+1]$$$.
This is called counting inversions!
An inversion is a pair $$$(i, j)$$$ where $$$i \lt j$$$ but $$$p[i] \gt p[j]$$$.
Total swaps needed = total number of inversions in the prefix sum array.
How to count inversions efficiently?
Method 1: Use an ordered_set
• For each element $$$p[i]$$$, query how many elements inserted so far are $$$ \gt p[i]$$$
• Insert $$$p[i]$$$ into the ordered_set
• Time: $$$O(n \log n)$$$
Method 2: Merge Sort with inversion counting
Method 3: Fenwick Tree (BIT) or Segment Tree with coordinate compression
All methods give $$$O(n \log n)$$$ complexity.
My submission — 399484722
2289E - The Problem from Silach
The given structure is a tournament bracket represented as a tree.
We need to track two things:
1. For each match, which players can potentially win that match
2. For each player, what's the highest match they reach before being eliminated
Let's explore an $$$O(n^2)$$$ solution first, then we'll optimize it.
For each match $$$i$$$, maintain a list $$$winners[i]$$$ = players who can win this match.
Initially, each player $$$i$$$ starts at leaf match $$$i$$$, so $$$winners[i] = {i}$$$.
Now consider match $$$i$$$ which has two child matches $$$u$$$ and $$$v$$$.
We already know $$$winners[u]$$$ and $$$winners[v]$$$ from processing earlier matches.
Which players survive to match $$$i$$$?
Look at the maximum rank from each side: let $$$mx_u$$$ = max rank in $$$winners[u]$$$, and $$$mx_v$$$ = max rank in $$$winners[v]$$$.
Players from side $$$u$$$ survive if their rank $$$ \lt mx_v + d$$$. Similarly for side $$$v$$$.
So for each match $$$i$$$ with children $$$u$$$ and $$$v$$$:
1. Find the maximum rank on each side: $$$mx_u$$$ and $$$mx_v$$$
2. Players from $$$u$$$ with rank $$$\geq mx_v + d$$$ get eliminated here
3. Players from $$$v$$$ with rank $$$\geq mx_u + d$$$ get eliminated here
4. For eliminated players, record that they reached match $$$i$$$
5. Merge the remaining survivors from both sides into $$$winners[i]$$$
If we do this naively, each match takes $$$O(n)$$$ time, giving $$$O(n^2)$$$ total.
Can we optimize the merging?
Yes! Use small-to-large merge: always iterate through the smaller set and insert into the larger set.
Why does this help?
Each time a player is moved from a smaller set to a larger set, the new set size is at least double.
So each player can be moved at most $$$O(\log n)$$$ times before the set becomes larger than $$$n$$$.
Total work: $$$n$$$ players $$$\times$$$ $$$O(\log n)$$$ moves each = $$$O(n \log n)$$$ instead of $$$O(n^2)$$$!
My submission — 399487330








I think the title is supposed to be 1137 not 1037
Thanks, fixed.
what about problem F?
I was able to think of the quadratic solution for E, however for some reason I can't really understand like the correctness of the merging like I dunno it just feels weird that this is correct. Can you help me intuitively how understand how did you arrive at this idea? Like I really feel very weird about this problem honestly even after like spending an hour on it.