[Here](https://codeforces.net/contestInvitation/cccd31bebeb08638cc7f11e41ebbd2d9d0a60025) is the link to the contest. All problems are from Codeforces' problemset.↵
↵
#### [A. Make the Product Zero](https://codeforces.net/gym/586960/problem/A)↵
↵
<spoiler summary="Hint"> ↵
To make the product of all elements zero, we need at least one element in the array to be zero. </spoiler>↵
↵
↵
↵
<spoiler summary="Solution"> ↵
<p> ↵
↵
There are three cases to consider: ↵
<ul>↵
<li>If there is already a zero in the array, no operations are needed.</li>↵
<li>If there are negative numbers, we can turn one of them into zero, requiring at most |A[i]| operations.</li> ↵
<li>If all numbers are positive, the minimum number of operations required is to turn the smallest positive number into zero.</li> ↵
</ul> ↵
↵
The solution involves iterating through the array and determining the minimum number of operations needed. ↵
</p>↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Code1"> ↵
```python3↵
n = int(input())↵
nums = list(map(int, input().split()))↵
↵
min_operations = float('inf')↵
zero_found = False↵
↵
for num in nums:↵
if num == 0:↵
zero_found = True↵
break↵
min_operations = min(min_operations, abs(num))↵
↵
if zero_found:↵
print(0)↵
else:↵
print(min_operations)↵
↵
```↵
</spoiler>↵
↵
<spoiler summary="Code2"> ↵
```python3↵
def solve():↵
n = int(input())↵
a = [abs(int(x)) for x in input().split()]↵
print(min(a))↵
↵
solve()↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
#### [B. Special Matrix Quest](https://codeforces.net/gym/586960/problem/B)↵
↵
<spoiler summary="Hint">↵
To solve this problem efficiently, consider how elements are positioned in the matrix and how to avoid double-counting.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
<p>↵
The problem requires us to identify and sum specific elements in an <b>n × n</b> matrix where <b>n</b> is odd. The elements to be considered are:↵
<ul>↵
<li><b>Elements of the main diagonal:</b> These are the elements where the row index equals the column index, i.e., <b>(i, i)</b>.</li>↵
<li><b>Elements of the secondary diagonal:</b> These are the elements where the sum of the row index and column index equals <b>n − 1</b>, i.e., <b>(i, n − 1 − i)</b>.</li>↵
<li><b>Elements of the middle row:</b> This is the row that has exactly <b>((n − 1) / 2)</b> rows above and below it.</li>↵
<li><b>Elements of the middle column:</b> This is the column that has exactly <b>(n − 1) / 2</b> columns to the left and right of it.</li>↵
</ul>↵
↵
To avoid double-counting elements that fall into multiple categories (e.g., the intersection of the main diagonal and the middle row), we use a set to keep track of the positions we have already included in the sum.↵
↵
The solution involves iterating through the matrix and checking if each element falls into one of the four categories. If it does, and it hasn't been added to the sum before, we add it to the sum and mark its position as visited.↵
</p>↵
</spoiler>↵
↵
<spoiler summary="Code1">↵
↵
↵
```↵
n = int(input()) ↵
matrix = [] ↵
for _ in range(n): ↵
inp = [int(i) for i in input().split()] ↵
matrix.append(inp) ↵
↵
visited = set() ↵
mid_row = mid_col = n // 2 ↵
ans = 0 ↵
↵
for i in range(n): ↵
# Main diagonal ↵
if (i, i) not in visited: ↵
ans += matrix[i][i] ↵
visited.add((i, i)) ↵
↵
# Secondary diagonal ↵
if (i, n - 1 - i) not in visited: ↵
ans += matrix[i][n - 1 - i] ↵
visited.add((i, n - 1 - i)) ↵
↵
# Middle row ↵
if (mid_row, i) not in visited: ↵
ans += matrix[mid_row][i] ↵
visited.add((mid_row, i)) ↵
↵
# Middle column ↵
if (i, mid_col) not in visited: ↵
ans += matrix[i][mid_col] ↵
visited.add((i, mid_col)) ↵
↵
print(ans)↵
↵
↵
↵
↵
```↵
↵
↵
↵
Time Complexity = O(n)↵
</spoiler>↵
↵
↵
<spoiler summary="Code2">↵
↵
↵
```↵
'''↵
Basic Properties↵
<> i == j --> main diagonal↵
<> i + j == ( n - 1) --> secondary diagonal↵
<> i == n//2 --> middle row↵
<> j == n//2 --> middle column↵
'''↵
def solve():↵
matrix = []↵
n = int(input())↵
for i in range(n):↵
row = list(map(int , input().split()))↵
matrix.append(row)↵
↵
ans = 0↵
for i in range(n):↵
for j in range(n):↵
if i == j or i == n//2 or j == n//2 or i + j == n - 1 :↵
ans += matrix[i][j]↵
↵
print(ans)↵
↵
↵
↵
↵
solve()↵
↵
```↵
↵
Time Complexity = O(n * n)↵
</spoiler>↵
↵
↵
↵
↵
####[ C. The Splitting Game](https://codeforces.net/gym/586960/problem/C)↵
↵
↵
<spoiler summary = "Solution">↵
<p>↵
↵
We need to split the string $s$ into two non-empty parts $a$ and $b$ such that the sum of distinct characters in both parts is maximized. The key observation here is that we can efficiently track the distinct characters in both parts as we move through the string.↵
↵
We can solve this problem by iterating over each character of the string and keeping track of two sets:↵
<ul>↵
<li>One set for characters in the left part (which means for $a$).</li>↵
<li>One set for characters in the right part (which means for $b$).</li>↵
</ul>↵
↵
At each split point, we move one character from the right set to the left set and update the distinct counts accordingly. By doing this, we can maintain the current sum of distinct characters and track the maximum sum observed.↵
↵
Here's how we can implement it:↵
↵
<ul>↵
<li>Start by putting all characters in the right part of the string.</li>↵
<li>Iterate through each character in the string, shifting one character at a time from the right part to the left part, and updating the distinct character counts for both parts.</li>↵
<li>At each step, compute the sum of distinct characters in both parts and keep track of the maximum sum observed.</li>↵
</ul>↵
↵
</p>↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
from collections import Counter↵
↵
def max_distinct_split(s):↵
right_counter = Counter(s) # Tracks character counts in the right part↵
left_counter = Counter() # Tracks character counts in the left part↵
max_distinct_sum = 0 # Stores the maximum sum of distinct characters↵
↵
for char in s:↵
# Move character from right part to left part↵
left_counter[char] += 1↵
right_counter[char] -= 1↵
↵
# If a character count in the right part becomes zero, remove it↵
if right_counter[char] == 0:↵
del right_counter[char]↵
↵
# Calculate the sum of distinct characters in both parts↵
distinct_sum = len(left_counter) + len(right_counter)↵
max_distinct_sum = max(max_distinct_sum, distinct_sum)↵
↵
return max_distinct_sum↵
↵
↵
t = int(input())↵
↵
for _ in range(t):↵
n = int(input())↵
s = input()↵
print(max_distinct_split(s))↵
```↵
</spoiler>↵
↵
#### [D. Bomb Detection Validation](https://codeforces.net/gym/586960/problem/D)↵
↵
<spoiler summary = "Solution">↵
To solve this problem, we need to validate whether a given Minesweeper field is consistent with the rules of the game. We are given a grid where each cell can either be empty, contain a digit (from $1$ to $8$), or a bomb ($'*’$). The task is to ensure that for each cell with a digit $k$, exactly $k$ neighboring cells contain bombs. For empty cells ($'.'$), all surrounding cells must be free of bombs. We iterate through the grid, for each non-bomb cell, we count the number of bombs in its $8$ neighboring cells. If a numbered cell doesn't match the expected bomb count, or if an empty cell has surrounding bombs, we flag the grid as invalid. If the entire grid passes the checks, we output $"YES"$; otherwise, $"NO"$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n, m = map(int, input().split()) # Read dimensions of the grid↵
grid = []↵
↵
# Read the grid input↵
for _ in range(n):↵
row = input()↵
grid.append(row)↵
↵
# Directions for 8 neighboring cells (up, down, left, right, and diagonals)↵
directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]↵
↵
def is_inbound(x, y):↵
"""Check if the given coordinates are within the grid bounds."""↵
return 0 <= x < n and 0 <= y < m↵
↵
def count_bombs(x, y):↵
"""Count the number of bombs surrounding a given cell."""↵
bomb_count = 0↵
for dx, dy in directions:↵
ni, nj = x + dx, y + dy↵
if is_inbound(ni, nj) and grid[ni][nj] == '*':↵
bomb_count += 1↵
↵
return bomb_count↵
↵
valid = True # Flag to track validity of the field↵
↵
# Iterate through each cell in the grid↵
for i in range(n):↵
for j in range(m):↵
if grid[i][j] == '*':↵
continue # Bomb cells are inherently valid↵
↵
bomb_count = count_bombs(i, j)↵
↵
if grid[i][j] == '.': # Empty cell should not have any bombs around it↵
if bomb_count > 0:↵
valid = False↵
else: # Numbered cell should match the count of surrounding bombs↵
if int(grid[i][j]) != bomb_count:↵
valid = False↵
↵
# Print result based on validity↵
print("YES" if valid else "NO")↵
```↵
</spoiler>↵
↵
↵
↵
#### [E. Symmetrization](https://codeforces.net/gym/586960/problem/E)↵
↵
<spoiler summary = "Approach">↵
<p>Let's rotate the grid by 0∘, 90∘, 180∘, and 270∘, and mark all cells that map to each other under these rotations. For example, for 4×4 and 5×5 grids, the grid must have the following patterns, the same letters denoting equal values:↵
</p>↵
↵
$$↵
\begin{bmatrix}↵
a & b & c & a \\↵
c & d & d & b\\↵
b & d & d & c\\↵
a & c & b & a \\↵
\end{bmatrix}↵
\quad↵
\begin{bmatrix}↵
a & b & c & d & a \\↵
d & e & f & e & b\\↵
c & f & g & f & c\\↵
b & e & f & e & d\\↵
a & d & c & b & a \\↵
\end{bmatrix}↵
$$↵
<p>↵
In general, we can rotate the grid by 0∘, 90∘, 180∘, and 270∘ and see which cells need to have equal values by seeing the positions which each cell maps to.↵
</p>↵
<p>↵
Now to solve the problem, we consider each equal value (each of the letters a, b, c, ... in the above figures) independently, and consider the minimum number of moves to make them all 0 or all 1. The answer is the total across all values.↵
</p>↵
<p>↵
The time complexity is O($ n^2 $).↵
And the space complexity is O($ 1 $).↵
↵
</p>↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
Let's consider the upper triangular quarter of the grid. If we are at $(i, j)$, after rotating it by 0∘, 90∘, 180∘, and 270∘, the bit at this position is replaced by the one at $(j, n - i - 1)$, $(n - i - 1, n - j - 1)$, $(n - j - 1, i)$ respectively. From these four positions we count the numbers of zeros and ones and take the minimum. We sum those minimums for all positions in the upper triangular quarter of the grid.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
↵
↵
t = int(input())↵
for _ in range(t):↵
↵
n = int(input())↵
↵
grid = []↵
for i in range(n):↵
grid.append(input())↵
↵
↵
min_ops = 0↵
↵
for row in range(n//2):↵
for col in range(row, n - row - 1):↵
↵
zero_one_count = [0, 0]↵
↵
zero_one_count[int(grid[row][col])] += 1↵
zero_one_count[int(grid[col][n - row - 1])] += 1↵
zero_one_count[int(grid[n - row - 1][n - col - 1])] += 1↵
zero_one_count[int(grid[n - col - 1][row])] += 1↵
↵
min_ops += min(zero_one_count)↵
↵
print(min_ops)↵
↵
```↵
</spoiler>↵
↵
↵
↵
####[ F. Array Transformation](https://codeforces.net/gym/586960/problem/F)↵
↵
↵
**Approach 1:**↵
↵
<spoiler summary = "Hint1">↵
For a specific C, what happens to those elements that appear in our array less than C times?↵
</spoiler>↵
↵
<spoiler summary = "Hint2">↵
What about the elements that appear C or more times?↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
<p>↵
↵
For a given integer $C$, all elements in the array that appear less than $C$ times should be deleted to make the array beautiful because we can’t increase their frequency as we are only allowed to delete elements and not add. For elements that appear $C$ or more times, $count_x$ — $C$ elements should be deleted for every integer x in the given array where $count_x$ is the number of times $x$ appears in the given array.↵
</p>↵
↵
<p>↵
Let's have a dictionary $dict$ to count the frequency of each number in the given array. Let $\mathbf{min}_{count}$, $\mathbf{max}_{count}$ be the minimum and maximum frequencies(values) we have in $dict$. To find the optimal answer $\mathbf{min}_{count}$ <= $C$ <= $\mathbf{max}_{count}$ should be satisfied. If $C$ is outside that range, we will have to delete more elements than necessary and we can't find the optimal answer that way. ↵
</p>↵
↵
<p>↵
<ul>↵
<li>Let $removed$ be our variable to count the number of elements we will remove to make the given array beautiful. We have at most $n$ different values for $C$ in that range. ↵
</li>↵
↵
<li>For every $C$ we can iterate over $dict$ and we will add $dict[x]$ to removed if $dict[x]$ < $C$ and $C$ - $dict[x]$ otherwise. This would take $O(n^2)$ time. ↵
</li>↵
</ul>↵
</p>↵
↵
<p>↵
But note that if there is no such number y such that $dict[y]$ = $C$, then such a value of $C$ will not give the minimum answer (because we have removed unnecessary elements). So if we consider only the frequencies that exist in $dict$ we can find our answer in $O(\sqrt{n} . n)$ time.↵
↵
</p>↵
↵
<ul>↵
<li>↵
$\text{Time Complexity: } O(\sqrt{n} . n)$↵
</li>↵
<li>↵
$\text{Space Complexity: } O(n)$↵
</li>↵
</ul>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from collections import Counter↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
arr = list(map(int, input().split()))↵
↵
count = Counter(arr)↵
↵
options = set(count.values())↵
min_deletions = float('inf')↵
↵
#c is always in range 1 to n↵
for c in range(1, n + 1):↵
if c not in options:↵
continue↵
↵
deletions = 0↵
for num in count:↵
if count[num] < c:↵
deletions += count[num]↵
else:↵
deletions += count[num] - c↵
↵
min_deletions = min(min_deletions, deletions)↵
↵
print(min_deletions)↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
**Approach 2:**↵
↵
<spoiler summary = "Hint">↵
What if we sort each number based on their frequency ?↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
<p>↵
Let’s have a new array called $arr$. For every $key, value$ pair we have in our $dict$, we add $value$ (frequencies) to $arr$ and sort it. Then we can iterate over this array and for every unique frequency we get in our iteration we can easily count how many elements we need to remove to make the given array beautiful as follows: $removed$ = $n - (len(arr) - i) * arr[i]$. ↵
↵
</p>↵
↵
<p>↵
Here $C = arr[i]$. If we have already calculated our answer for this particular $C$ (that is, $i > 0$ and $arr[i] == arr[i - 1]$ is $True$), we move on to the next iteration. Otherwise we are sure that there are $len(arr) - i$ unique elements that exist $arr[i]$ or more times. Since we only want each of them to appear exactly $arr[i]$ times, we will end up with $arr[i] * (len(arr) - i)$ elements in our array. That’s why $removed = n - (len(arr) - i) * arr[i]$ is $True$↵
</p>↵
↵
<ul>↵
<li>↵
$\text{Time Complexity: } O(nlogn)$↵
</li>↵
<li>↵
$\text{Space Complexity: } O(n)$↵
</li>↵
</ul>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from collections import Counter↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
arr = list(map(int, input().split()))↵
↵
count = Counter(arr)↵
↵
values = list(count.values())↵
values.sort()↵
↵
min_deletions = float('inf')↵
↵
for i in range(len(values)):↵
# you can add the following if condition to only count deletions for↵
# unique values of c = arr[i] but it's not mandatory. ↵
# if i > 0 and values[i] == values[i - 1]:↵
# continue↵
↵
deletions = n - (len(values) - i) * values[i]↵
min_deletions = min(min_deletions, deletions)↵
↵
print(min_deletions)↵
↵
```↵
</spoiler>↵
↵
↵
**Approach 3:**↵
↵
<spoiler summary="Solution">↵
↵
This problem can be solved using a dictionary to track the count of each number in the array. By iterating through the array and incrementing the count of each number in the dictionary, we calculate the current count (`current_count`) for each number. Additionally, we utilize another dictionary (`appearance_dict`) to monitor the total size of the numbers for each frequency count (calculated as `frequency_count * frequency = the total size`). This calculation allows us to understand the array's total size if the frequency is set as `C`.↵
↵
After traversing through the array, we determine the maximum value in the `appearance_dict` dictionary. This value signifies the maximum size capable of accommodating numbers. The key retrieved from the dictionary indicates the maximum frequency for each unique number, necessary to make the array beautiful. Our goal is to ensure each number appears either zero or `C` times. Hence, we must eliminate all elements except those appearing `C` times. Consequently, the number of elements to remove equals the total number of elements minus the maximum value found in the `appearance_dict` dictionary.↵
↵
↵
<ul>↵
<li>↵
$\text{Time Complexity: } O(n)$↵
</li>↵
<li>↵
$\text{Space Complexity: } O(n)$↵
</li>↵
</ul>↵
↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Code">↵
```python↵
from collections import defaultdict↵
↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
nums = list(map(int, input().split()))↵
↵
count = defaultdict(int)↵
appearance_dict = defaultdict(int)↵
↵
for num in nums:↵
count[num] += 1↵
current_count = count[num]↵
appearance_dict[current_count] += 1↵
↵
max_appearance = 0↵
↵
for key , value in appearance_dict.items():↵
max_appearance = max(key * value , max_appearance)↵
↵
print(n - max_appearance)↵
↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
#### [A. Make the Product Zero](https://codeforces.net/gym/586960/problem/A)↵
↵
<spoiler summary="Hint"> ↵
To make the product of all elements zero, we need at least one element in the array to be zero. </spoiler>↵
↵
↵
↵
<spoiler summary="Solution"> ↵
<p> ↵
↵
There are three cases to consider: ↵
<ul>↵
<li>If there is already a zero in the array, no operations are needed.</li>↵
<li>If there are negative numbers, we can turn one of them into zero, requiring at most |A[i]| operations.</li> ↵
<li>If all numbers are positive, the minimum number of operations required is to turn the smallest positive number into zero.</li> ↵
</ul> ↵
↵
The solution involves iterating through the array and determining the minimum number of operations needed. ↵
</p>↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Code1"> ↵
```python3↵
n = int(input())↵
nums = list(map(int, input().split()))↵
↵
min_operations = float('inf')↵
zero_found = False↵
↵
for num in nums:↵
if num == 0:↵
zero_found = True↵
break↵
min_operations = min(min_operations, abs(num))↵
↵
if zero_found:↵
print(0)↵
else:↵
print(min_operations)↵
↵
```↵
</spoiler>↵
↵
<spoiler summary="Code2"> ↵
```python3↵
def solve():↵
n = int(input())↵
a = [abs(int(x)) for x in input().split()]↵
print(min(a))↵
↵
solve()↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
#### [B. Special Matrix Quest](https://codeforces.net/gym/586960/problem/B)↵
↵
<spoiler summary="Hint">↵
To solve this problem efficiently, consider how elements are positioned in the matrix and how to avoid double-counting.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
<p>↵
The problem requires us to identify and sum specific elements in an <b>n × n</b> matrix where <b>n</b> is odd. The elements to be considered are:↵
<ul>↵
<li><b>Elements of the main diagonal:</b> These are the elements where the row index equals the column index, i.e., <b>(i, i)</b>.</li>↵
<li><b>Elements of the secondary diagonal:</b> These are the elements where the sum of the row index and column index equals <b>n − 1</b>, i.e., <b>(i, n − 1 − i)</b>.</li>↵
<li><b>Elements of the middle row:</b> This is the row that has exactly <b>((n − 1) / 2)</b> rows above and below it.</li>↵
<li><b>Elements of the middle column:</b> This is the column that has exactly <b>(n − 1) / 2</b> columns to the left and right of it.</li>↵
</ul>↵
↵
To avoid double-counting elements that fall into multiple categories (e.g., the intersection of the main diagonal and the middle row), we use a set to keep track of the positions we have already included in the sum.↵
↵
The solution involves iterating through the matrix and checking if each element falls into one of the four categories. If it does, and it hasn't been added to the sum before, we add it to the sum and mark its position as visited.↵
</p>↵
</spoiler>↵
↵
<spoiler summary="Code1">↵
↵
↵
```↵
n = int(input()) ↵
matrix = [] ↵
for _ in range(n): ↵
inp = [int(i) for i in input().split()] ↵
matrix.append(inp) ↵
↵
visited = set() ↵
mid_row = mid_col = n // 2 ↵
ans = 0 ↵
↵
for i in range(n): ↵
# Main diagonal ↵
if (i, i) not in visited: ↵
ans += matrix[i][i] ↵
visited.add((i, i)) ↵
↵
# Secondary diagonal ↵
if (i, n - 1 - i) not in visited: ↵
ans += matrix[i][n - 1 - i] ↵
visited.add((i, n - 1 - i)) ↵
↵
# Middle row ↵
if (mid_row, i) not in visited: ↵
ans += matrix[mid_row][i] ↵
visited.add((mid_row, i)) ↵
↵
# Middle column ↵
if (i, mid_col) not in visited: ↵
ans += matrix[i][mid_col] ↵
visited.add((i, mid_col)) ↵
↵
print(ans)↵
↵
↵
↵
↵
```↵
↵
↵
↵
Time Complexity = O(n)↵
</spoiler>↵
↵
↵
<spoiler summary="Code2">↵
↵
↵
```↵
'''↵
Basic Properties↵
<> i == j --> main diagonal↵
<> i + j == ( n - 1) --> secondary diagonal↵
<> i == n//2 --> middle row↵
<> j == n//2 --> middle column↵
'''↵
def solve():↵
matrix = []↵
n = int(input())↵
for i in range(n):↵
row = list(map(int , input().split()))↵
matrix.append(row)↵
↵
ans = 0↵
for i in range(n):↵
for j in range(n):↵
if i == j or i == n//2 or j == n//2 or i + j == n - 1 :↵
ans += matrix[i][j]↵
↵
print(ans)↵
↵
↵
↵
↵
solve()↵
↵
```↵
↵
Time Complexity = O(n * n)↵
</spoiler>↵
↵
↵
↵
↵
####[ C. The Splitting Game](https://codeforces.net/gym/586960/problem/C)↵
↵
↵
<spoiler summary = "Solution">↵
<p>↵
↵
We need to split the string $s$ into two non-empty parts $a$ and $b$ such that the sum of distinct characters in both parts is maximized. The key observation here is that we can efficiently track the distinct characters in both parts as we move through the string.↵
↵
We can solve this problem by iterating over each character of the string and keeping track of two sets:↵
<ul>↵
<li>One set for characters in the left part (which means for $a$).</li>↵
<li>One set for characters in the right part (which means for $b$).</li>↵
</ul>↵
↵
At each split point, we move one character from the right set to the left set and update the distinct counts accordingly. By doing this, we can maintain the current sum of distinct characters and track the maximum sum observed.↵
↵
Here's how we can implement it:↵
↵
<ul>↵
<li>Start by putting all characters in the right part of the string.</li>↵
<li>Iterate through each character in the string, shifting one character at a time from the right part to the left part, and updating the distinct character counts for both parts.</li>↵
<li>At each step, compute the sum of distinct characters in both parts and keep track of the maximum sum observed.</li>↵
</ul>↵
↵
</p>↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
from collections import Counter↵
↵
def max_distinct_split(s):↵
right_counter = Counter(s) # Tracks character counts in the right part↵
left_counter = Counter() # Tracks character counts in the left part↵
max_distinct_sum = 0 # Stores the maximum sum of distinct characters↵
↵
for char in s:↵
# Move character from right part to left part↵
left_counter[char] += 1↵
right_counter[char] -= 1↵
↵
# If a character count in the right part becomes zero, remove it↵
if right_counter[char] == 0:↵
del right_counter[char]↵
↵
# Calculate the sum of distinct characters in both parts↵
distinct_sum = len(left_counter) + len(right_counter)↵
max_distinct_sum = max(max_distinct_sum, distinct_sum)↵
↵
return max_distinct_sum↵
↵
↵
t = int(input())↵
↵
for _ in range(t):↵
n = int(input())↵
s = input()↵
print(max_distinct_split(s))↵
```↵
</spoiler>↵
↵
#### [D. Bomb Detection Validation](https://codeforces.net/gym/586960/problem/D)↵
↵
<spoiler summary = "Solution">↵
To solve this problem, we need to validate whether a given Minesweeper field is consistent with the rules of the game. We are given a grid where each cell can either be empty, contain a digit (from $1$ to $8$), or a bomb ($'*’$). The task is to ensure that for each cell with a digit $k$, exactly $k$ neighboring cells contain bombs. For empty cells ($'.'$), all surrounding cells must be free of bombs. We iterate through the grid, for each non-bomb cell, we count the number of bombs in its $8$ neighboring cells. If a numbered cell doesn't match the expected bomb count, or if an empty cell has surrounding bombs, we flag the grid as invalid. If the entire grid passes the checks, we output $"YES"$; otherwise, $"NO"$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n, m = map(int, input().split()) # Read dimensions of the grid↵
grid = []↵
↵
# Read the grid input↵
for _ in range(n):↵
row = input()↵
grid.append(row)↵
↵
# Directions for 8 neighboring cells (up, down, left, right, and diagonals)↵
directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]↵
↵
def is_inbound(x, y):↵
"""Check if the given coordinates are within the grid bounds."""↵
return 0 <= x < n and 0 <= y < m↵
↵
def count_bombs(x, y):↵
"""Count the number of bombs surrounding a given cell."""↵
bomb_count = 0↵
for dx, dy in directions:↵
ni, nj = x + dx, y + dy↵
if is_inbound(ni, nj) and grid[ni][nj] == '*':↵
bomb_count += 1↵
↵
return bomb_count↵
↵
valid = True # Flag to track validity of the field↵
↵
# Iterate through each cell in the grid↵
for i in range(n):↵
for j in range(m):↵
if grid[i][j] == '*':↵
continue # Bomb cells are inherently valid↵
↵
bomb_count = count_bombs(i, j)↵
↵
if grid[i][j] == '.': # Empty cell should not have any bombs around it↵
if bomb_count > 0:↵
valid = False↵
else: # Numbered cell should match the count of surrounding bombs↵
if int(grid[i][j]) != bomb_count:↵
valid = False↵
↵
# Print result based on validity↵
print("YES" if valid else "NO")↵
```↵
</spoiler>↵
↵
↵
↵
#### [E. Symmetrization](https://codeforces.net/gym/586960/problem/E)↵
↵
<spoiler summary = "Approach">↵
<p>Let's rotate the grid by 0∘, 90∘, 180∘, and 270∘, and mark all cells that map to each other under these rotations. For example, for 4×4 and 5×5 grids, the grid must have the following patterns, the same letters denoting equal values:↵
</p>↵
↵
$$↵
\begin{bmatrix}↵
a & b & c & a \\↵
c & d & d & b\\↵
b & d & d & c\\↵
a & c & b & a \\↵
\end{bmatrix}↵
\quad↵
\begin{bmatrix}↵
a & b & c & d & a \\↵
d & e & f & e & b\\↵
c & f & g & f & c\\↵
b & e & f & e & d\\↵
a & d & c & b & a \\↵
\end{bmatrix}↵
$$↵
<p>↵
In general, we can rotate the grid by 0∘, 90∘, 180∘, and 270∘ and see which cells need to have equal values by seeing the positions which each cell maps to.↵
</p>↵
<p>↵
Now to solve the problem, we consider each equal value (each of the letters a, b, c, ... in the above figures) independently, and consider the minimum number of moves to make them all 0 or all 1. The answer is the total across all values.↵
</p>↵
<p>↵
The time complexity is O($ n^2 $).↵
And the space complexity is O($ 1 $).↵
↵
</p>↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
Let's consider the upper triangular quarter of the grid. If we are at $(i, j)$, after rotating it by 0∘, 90∘, 180∘, and 270∘, the bit at this position is replaced by the one at $(j, n - i - 1)$, $(n - i - 1, n - j - 1)$, $(n - j - 1, i)$ respectively. From these four positions we count the numbers of zeros and ones and take the minimum. We sum those minimums for all positions in the upper triangular quarter of the grid.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
↵
↵
t = int(input())↵
for _ in range(t):↵
↵
n = int(input())↵
↵
grid = []↵
for i in range(n):↵
grid.append(input())↵
↵
↵
min_ops = 0↵
↵
for row in range(n//2):↵
for col in range(row, n - row - 1):↵
↵
zero_one_count = [0, 0]↵
↵
zero_one_count[int(grid[row][col])] += 1↵
zero_one_count[int(grid[col][n - row - 1])] += 1↵
zero_one_count[int(grid[n - row - 1][n - col - 1])] += 1↵
zero_one_count[int(grid[n - col - 1][row])] += 1↵
↵
min_ops += min(zero_one_count)↵
↵
print(min_ops)↵
↵
```↵
</spoiler>↵
↵
↵
↵
####[ F. Array Transformation](https://codeforces.net/gym/586960/problem/F)↵
↵
↵
**Approach 1:**↵
↵
<spoiler summary = "Hint1">↵
For a specific C, what happens to those elements that appear in our array less than C times?↵
</spoiler>↵
↵
<spoiler summary = "Hint2">↵
What about the elements that appear C or more times?↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
<p>↵
↵
For a given integer $C$, all elements in the array that appear less than $C$ times should be deleted to make the array beautiful because we can’t increase their frequency as we are only allowed to delete elements and not add. For elements that appear $C$ or more times, $count_x$ — $C$ elements should be deleted for every integer x in the given array where $count_x$ is the number of times $x$ appears in the given array.↵
</p>↵
↵
<p>↵
Let's have a dictionary $dict$ to count the frequency of each number in the given array. Let $\mathbf{min}_{count}$, $\mathbf{max}_{count}$ be the minimum and maximum frequencies(values) we have in $dict$. To find the optimal answer $\mathbf{min}_{count}$ <= $C$ <= $\mathbf{max}_{count}$ should be satisfied. If $C$ is outside that range, we will have to delete more elements than necessary and we can't find the optimal answer that way. ↵
</p>↵
↵
<p>↵
<ul>↵
<li>Let $removed$ be our variable to count the number of elements we will remove to make the given array beautiful. We have at most $n$ different values for $C$ in that range. ↵
</li>↵
↵
<li>For every $C$ we can iterate over $dict$ and we will add $dict[x]$ to removed if $dict[x]$ < $C$ and $C$ - $dict[x]$ otherwise. This would take $O(n^2)$ time. ↵
</li>↵
</ul>↵
</p>↵
↵
<p>↵
But note that if there is no such number y such that $dict[y]$ = $C$, then such a value of $C$ will not give the minimum answer (because we have removed unnecessary elements). So if we consider only the frequencies that exist in $dict$ we can find our answer in $O(\sqrt{n} . n)$ time.↵
↵
</p>↵
↵
<ul>↵
<li>↵
$\text{Time Complexity: } O(\sqrt{n} . n)$↵
</li>↵
<li>↵
$\text{Space Complexity: } O(n)$↵
</li>↵
</ul>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from collections import Counter↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
arr = list(map(int, input().split()))↵
↵
count = Counter(arr)↵
↵
options = set(count.values())↵
min_deletions = float('inf')↵
↵
#c is always in range 1 to n↵
for c in range(1, n + 1):↵
if c not in options:↵
continue↵
↵
deletions = 0↵
for num in count:↵
if count[num] < c:↵
deletions += count[num]↵
else:↵
deletions += count[num] - c↵
↵
min_deletions = min(min_deletions, deletions)↵
↵
print(min_deletions)↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
**Approach 2:**↵
↵
<spoiler summary = "Hint">↵
What if we sort each number based on their frequency ?↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
<p>↵
Let’s have a new array called $arr$. For every $key, value$ pair we have in our $dict$, we add $value$ (frequencies) to $arr$ and sort it. Then we can iterate over this array and for every unique frequency we get in our iteration we can easily count how many elements we need to remove to make the given array beautiful as follows: $removed$ = $n - (len(arr) - i) * arr[i]$. ↵
↵
</p>↵
↵
<p>↵
Here $C = arr[i]$. If we have already calculated our answer for this particular $C$ (that is, $i > 0$ and $arr[i] == arr[i - 1]$ is $True$), we move on to the next iteration. Otherwise we are sure that there are $len(arr) - i$ unique elements that exist $arr[i]$ or more times. Since we only want each of them to appear exactly $arr[i]$ times, we will end up with $arr[i] * (len(arr) - i)$ elements in our array. That’s why $removed = n - (len(arr) - i) * arr[i]$ is $True$↵
</p>↵
↵
<ul>↵
<li>↵
$\text{Time Complexity: } O(nlogn)$↵
</li>↵
<li>↵
$\text{Space Complexity: } O(n)$↵
</li>↵
</ul>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from collections import Counter↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
arr = list(map(int, input().split()))↵
↵
count = Counter(arr)↵
↵
values = list(count.values())↵
values.sort()↵
↵
min_deletions = float('inf')↵
↵
for i in range(len(values)):↵
# you can add the following if condition to only count deletions for↵
# unique values of c = arr[i] but it's not mandatory. ↵
# if i > 0 and values[i] == values[i - 1]:↵
# continue↵
↵
deletions = n - (len(values) - i) * values[i]↵
min_deletions = min(min_deletions, deletions)↵
↵
print(min_deletions)↵
↵
```↵
</spoiler>↵
↵
↵
**Approach 3:**↵
↵
<spoiler summary="Solution">↵
↵
This problem can be solved using a dictionary to track the count of each number in the array. By iterating through the array and incrementing the count of each number in the dictionary, we calculate the current count (`current_count`) for each number. Additionally, we utilize another dictionary (`appearance_dict`) to monitor the total size of the numbers for each frequency count (calculated as `frequency_count * frequency = the total size`). This calculation allows us to understand the array's total size if the frequency is set as `C`.↵
↵
After traversing through the array, we determine the maximum value in the `appearance_dict` dictionary. This value signifies the maximum size capable of accommodating numbers. The key retrieved from the dictionary indicates the maximum frequency for each unique number, necessary to make the array beautiful. Our goal is to ensure each number appears either zero or `C` times. Hence, we must eliminate all elements except those appearing `C` times. Consequently, the number of elements to remove equals the total number of elements minus the maximum value found in the `appearance_dict` dictionary.↵
↵
↵
<ul>↵
<li>↵
$\text{Time Complexity: } O(n)$↵
</li>↵
<li>↵
$\text{Space Complexity: } O(n)$↵
</li>↵
</ul>↵
↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Code">↵
```python↵
from collections import defaultdict↵
↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
nums = list(map(int, input().split()))↵
↵
count = defaultdict(int)↵
appearance_dict = defaultdict(int)↵
↵
for num in nums:↵
count[num] += 1↵
current_count = count[num]↵
appearance_dict[current_count] += 1↵
↵
max_appearance = 0↵
↵
for key , value in appearance_dict.items():↵
max_appearance = max(key * value , max_appearance)↵
↵
print(n - max_appearance)↵
↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
