[B. Thousand Sunny's Network Setup↵
](https://codeforces.net/gym/594356/problem/B)↵
↵
<spoiler summary="Solution">↵
The problem requires selecting k computers with the highest possible equal internet speed, given that we can only decrease speeds but not increase them. A simple and efficient approach is to sort the array in descending order and directly pick the k-th largest speed, as this ensures we select the highest possible speed that at least k computers can have. Alternatively, a brute-force approach involves iterating through potential speeds and counting how many computers can support them, keeping track of the maximum valid speed. Due to the weak constraints (n ≤ 100), both approaches work efficiently, with sorting providing an O(n log n) solution.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
```python↵
↵
n, k = map(int, input().split())↵
print(sorted(map(int, input().split()))[n - k])↵
```↵
↵
</spoiler>↵
↵
[D. Pirates Island: Painting the Grand Line](https://codeforces.net/gym/594356/problem/D)↵
↵
<spoiler summary= "Solution">↵
↵
You’re given an `NXM` grid where each cell has an initial color. A *stranger set* is a group of cells that:↵
↵
1. All share the **same** color.↵
2. No two cells in the set share a side (cells can touch diagonally but not edge-to-edge).↵
↵
In a single step, you can choose **any** such stranger set and repaint **all** its cells in any other color. The objective is to make **all** cells the same color using the fewest steps.↵
↵
#### Key Insight↵
↵
For each `color(c)`:↵
↵
- If **no pair** of adjacent cells has `color(c)`, you can repaint **all** of those cells in **1 step**. (They’re already pairwise strangers.)↵
- If **at least one** pair of adjacent cells has color `color(c)`, you need **2 steps** to repaint all cells of that color. (Because you can split the connected component into two “stranger” groups.)↵
↵
Hence, define for each `color(c)`:↵
↵
- **`color(c) = 0`** if `(c)` does **not** appear in the grid.↵
- **`color(c) = 1`** if `(c)` appears, but never in two adjacent cells.↵
- **`color(c) = 2`** if `(c)` appears and there is at least one pair of adjacent cells `color(c)`.↵
↵
#### Choosing the Final Color↵
↵
- Let `S` be the sum of `color(c)` over every color `c` that appears.↵
- In code, this is computed as `sum(has_color ) + sum(adj_found)`, where `has_color [c]` is `1` if `c` appears, and `adj_found[c]` is `1` if `c` has adjacent cells.↵
- If you select some color `C*` as the final color, you **do not** need to repaint cells already in `C*`.↵
- The minimum steps required to unify the grid into a single color is:↵
↵
**`result`** = `S - max(cost(c))`↵
↵
In the code, `max(cost(c)) = 1 + max(adj_found[c])`. Hence, the final result is:↵
↵
**`result`** = `(sum(has_color ) + sum(adj_found)) - 1 - max(adj_found)`↵
↵
↵
#### Complexity Analysis:↵
↵
- **Time Complexity:** `O(n*m)`:↵
- `O(n*m)` to read the grid and determine adjacent cells.↵
- `O(n*m)` to compute costs and find the maximum cost.↵
↵
- **Space Complexity:** `O(n*m)`:↵
- We store the entire grid `n*m` elements.↵
- We also maintain two arrays of size `(n*m) + 1` to track which colors appear and whether they have adjacent cells.↵
↵
</spoiler>↵
↵
<spoiler summary= "Code">↵
```↵
import sys ↵
input = sys.stdin.readline ↵
↵
def solve():↵
n, m = map(int, input().split())↵
grid = [list(map(int, input().split())) for i in range(n)]↵
has_color = [0] * (n * m + 1)↵
adj_found= [0] * (n * m + 1)↵
↵
for i in range(n):↵
for j in range(m):↵
has_color[grid[i][j]] = 1↵
↵
if i + 1 < n and grid[i][j] == grid[i + 1][j]:↵
adj_found[grid[i][j]] = 1↵
if j + 1 < m and grid[i][j] == grid[i][j + 1]:↵
adj_found[grid[i][j]] = 1↵
↵
print(sum(has_color) + sum(adj_found) - 1 - max(adj_found))↵
↵
if __name__ == '__main__':↵
for _ in range(int(input())):↵
solve()↵
```↵
</spoiler>↵
↵
↵
↵
[E. Straw Hat's Blue-Red Permutation](https://codeforces.net/gym/594356/problem/E)↵
↵
==================↵
<spoiler summary = "Solution">↵
Note the following fact: if a number $x$↵
in a permutation was obtained from a blue number and a number $y$↵
in a permutation was obtained from a red number, and $x>y$↵
, then by decreasing the blue number and increasing the red number exactly $x−y$↵
times each, we will obtain the same permutation in which the two numbers have swapped places. Thus, if a permutation can be obtained at all, some permutation can be obtained by making all the red numbers equal to $n,n−1,…,n−k+1$↵
, and the blue ones equal to $1,2,…,n−k$↵
, where $k$↵
is the total count of red numbers.↵
↵
Now consider separately two red numbers $a_{i}$↵
and $a_{j}$↵
such that $a_{i}>a_{j}$↵
. If $x$↵
is produced by increasing $a_{i}$↵
and $y$↵
is produced by increasing $a_{j}$↵
, and in the same time $x<y$↵
then $y>x⩾a_{i}>a_{j}$↵
, and the following is also true: $x>a_{j}$↵
and $y>a_{i}$↵
. So we just showed that if an answer exists, it also exists if greater numbers are produced by greater values from the input. The same holds for the blue numbers.↵
↵
Let us sort all elements ai↵
by the key $(c_{i},a_{i})$↵
, where $c_{i}$↵
the color of $i-th$ element (and blue comes before red). It remains to check that for any $t$↵
from $1$↵
to $n$↵
we can get the number $t$↵
from the $t$↵
-th element of the obtained sorted array. To do this, we iterate through it and check that either $c_{t}='B'$ and $a_{t}⩾t$↵
so it can be reduced to $t$, or, symmetrically, $c_{t}='R'$ and $a_{t}⩽t$.↵
<\spoiler>↵
<spoiler summary = "Code">↵
<\spoiler>↵
](https://codeforces.net/gym/594356/problem/B)↵
↵
<spoiler summary="Solution">↵
The problem requires selecting k computers with the highest possible equal internet speed, given that we can only decrease speeds but not increase them. A simple and efficient approach is to sort the array in descending order and directly pick the k-th largest speed, as this ensures we select the highest possible speed that at least k computers can have. Alternatively, a brute-force approach involves iterating through potential speeds and counting how many computers can support them, keeping track of the maximum valid speed. Due to the weak constraints (n ≤ 100), both approaches work efficiently, with sorting providing an O(n log n) solution.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
```python↵
↵
n, k = map(int, input().split())↵
print(sorted(map(int, input().split()))[n - k])↵
```↵
↵
</spoiler>↵
↵
[D. Pirates Island: Painting the Grand Line](https://codeforces.net/gym/594356/problem/D)↵
↵
<spoiler summary= "Solution">↵
↵
You’re given an `NXM` grid where each cell has an initial color. A *stranger set* is a group of cells that:↵
↵
1. All share the **same** color.↵
2. No two cells in the set share a side (cells can touch diagonally but not edge-to-edge).↵
↵
In a single step, you can choose **any** such stranger set and repaint **all** its cells in any other color. The objective is to make **all** cells the same color using the fewest steps.↵
↵
#### Key Insight↵
↵
For each `color(c)`:↵
↵
- If **no pair** of adjacent cells has `color(c)`, you can repaint **all** of those cells in **1 step**. (They’re already pairwise strangers.)↵
- If **at least one** pair of adjacent cells has color `color(c)`, you need **2 steps** to repaint all cells of that color. (Because you can split the connected component into two “stranger” groups.)↵
↵
Hence, define for each `color(c)`:↵
↵
- **`color(c) = 0`** if `(c)` does **not** appear in the grid.↵
- **`color(c) = 1`** if `(c)` appears, but never in two adjacent cells.↵
- **`color(c) = 2`** if `(c)` appears and there is at least one pair of adjacent cells `color(c)`.↵
↵
#### Choosing the Final Color↵
↵
- Let `S` be the sum of `color(c)` over every color `c` that appears.↵
- In code, this is computed as `sum(has_color ) + sum(adj_found)`, where `has_color [c]` is `1` if `c` appears, and `adj_found[c]` is `1` if `c` has adjacent cells.↵
- If you select some color `C*` as the final color, you **do not** need to repaint cells already in `C*`.↵
- The minimum steps required to unify the grid into a single color is:↵
↵
**`result`** = `S - max(cost(c))`↵
↵
In the code, `max(cost(c)) = 1 + max(adj_found[c])`. Hence, the final result is:↵
↵
**`result`** = `(sum(has_color ) + sum(adj_found)) - 1 - max(adj_found)`↵
↵
↵
#### Complexity Analysis:↵
↵
- **Time Complexity:** `O(n*m)`:↵
- `O(n*m)` to read the grid and determine adjacent cells.↵
- `O(n*m)` to compute costs and find the maximum cost.↵
↵
- **Space Complexity:** `O(n*m)`:↵
- We store the entire grid `n*m` elements.↵
- We also maintain two arrays of size `(n*m) + 1` to track which colors appear and whether they have adjacent cells.↵
↵
</spoiler>↵
↵
<spoiler summary= "Code">↵
```↵
import sys ↵
input = sys.stdin.readline ↵
↵
def solve():↵
n, m = map(int, input().split())↵
grid = [list(map(int, input().split())) for i in range(n)]↵
has_color = [0] * (n * m + 1)↵
adj_found= [0] * (n * m + 1)↵
↵
for i in range(n):↵
for j in range(m):↵
has_color[grid[i][j]] = 1↵
↵
if i + 1 < n and grid[i][j] == grid[i + 1][j]:↵
adj_found[grid[i][j]] = 1↵
if j + 1 < m and grid[i][j] == grid[i][j + 1]:↵
adj_found[grid[i][j]] = 1↵
↵
print(sum(has_color) + sum(adj_found) - 1 - max(adj_found))↵
↵
if __name__ == '__main__':↵
for _ in range(int(input())):↵
solve()↵
```↵
</spoiler>↵
↵
↵
↵
[E. Straw Hat's Blue-Red Permutation](https://codeforces.net/gym/594356/problem/E)↵
↵
<spoiler summary = "Solution">↵
Note the following fact: if a number $x$↵
in a permutation was obtained from a blue number and a number $y$↵
in a permutation was obtained from a red number, and $x>y$↵
, then by decreasing the blue number and increasing the red number exactly $x−y$↵
times each, we will obtain the same permutation in which the two numbers have swapped places. Thus, if a permutation can be obtained at all, some permutation can be obtained by making all the red numbers equal to $n,n−1,…,n−k+1$↵
, and the blue ones equal to $1,2,…,n−k$↵
, where $k$↵
is the total count of red numbers.↵
↵
Now consider separately two red numbers $a_{i}$↵
and $a_{j}$↵
such that $a_{i}>a_{j}$↵
. If $x$↵
is produced by increasing $a_{i}$↵
and $y$↵
is produced by increasing $a_{j}$↵
, and in the same time $x<y$↵
then $y>x⩾a_{i}>a_{j}$↵
, and the following is also true: $x>a_{j}$↵
and $y>a_{i}$↵
. So we just showed that if an answer exists, it also exists if greater numbers are produced by greater values from the input. The same holds for the blue numbers.↵
↵
Let us sort all elements ai↵
by the key $(c_{i},a_{i})$↵
, where $c_{i}$↵
the color of $i-th$ element (and blue comes before red). It remains to check that for any $t$↵
from $1$↵
to $n$↵
we can get the number $t$↵
from the $t$↵
-th element of the obtained sorted array. To do this, we iterate through it and check that either $c_{t}='B'$ and $a_{t}⩾t$↵
so it can be reduced to $t$, or, symmetrically, $c_{t}='R'$ and $a_{t}⩽t$.↵
<\spoiler>↵
<spoiler summary = "Code">↵
<\spoiler>↵
