B. Thousand Sunny's Network Setup
SolutionThe 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.
Code
n, k = map(int, input().split())
print(sorted(map(int, input().split()))[n - k])
D. Pirates Island: Painting the Grand Line
SolutionYou’re given an NXM grid where each cell has an initial color. A stranger set is a group of cells that:
- All share the same color.
- 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:
Codeimport 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()
E. Straw Hat's Blue-Red Permutation
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 \gt 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} \gt a_{j}$$$ . If $$$x$$$ is produced by increasing $$$a_{i}$$$ and $$$y$$$ is produced by increasing $$$a_{j}$$$ , and in the same time $$$x \lt y$$$ then $$$y \gt x⩾a_{i} \gt a_{j}$$$ , and the following is also true: $$$x \gt a_{j}$$$ and $$$y \gt 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>
F. Luffy’s Lineup Challenge
Solution The problem involves rearranging an array b to match the order of another array a using adjacent swaps. The key insight is that both arrays are guaranteed to be permutations of the same set of elements (i.e., they are multisets), meaning that we can always reorder b to match a. We start by creating a mapping of each value in a to its corresponding index, allowing us to track where each value from b should be placed in a. For each element in b, we replace it with the index from a, resulting in a list of target positions.Once we have this list of target positions, we simulate sorting it into the correct order using adjacent swaps (similar to bubble sort). At each step, we compare adjacent elements, and if they are in the wrong order, we swap them. We continue this process until the list is sorted, recording each swap. Finally, we output the number of swaps and the swap operations themselves. This approach guarantees the desired configuration while ensuring the solution is efficient enough given the problem constraints.
from collections import defaultdict
n = int(input()) a = list(map(int, input().split())) b = list(map(int, input().split()))
hash_map = defaultdict(list) for i in range(n): hash_map[a[i]].append(i)
for i in range(n): temp = hash_map[b[i]].pop() b[i] = temp
swaps = [] swap_count = 0
while True: swapped = False for i in range(n — 1): if b[i] > b[i + 1]: b[i], b[i + 1] = b[i + 1], b[i] swaps.append((i + 1, i + 2)) swap_count += 1 swapped = True if not swapped: break
print(swap_count) for swap in swaps: print(swap[0], swap[1])
