[Here](https://mirror.codeforces.com/gym/495192) is the mashup link (the problems are from Codeforces' problem set).↵
↵
#### [A. The Lone Element Quest](https://mirror.codeforces.com/gym/49519229) is the mashup link (the problems are from Codeforces' problem set).↵
↵
#### [A. The Lone Element Quest](https://mirror.codeforces.com/gym/495129/problem/A)↵
↵
<spoiler summary = "Solution">↵
First identify the unique element by counting the occurrences of the numbers and then find it's index in the array.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from collections import Counter↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
nums = list(map(int,input().split()))↵
count = Counter(nums)↵
for key in count:↵
if count[key] == 1:↵
mynum = key↵
for i in range(len(nums)):↵
if nums[i] == mynum:↵
print(i + 1)↵
break↵
```↵
</spoiler>↵
↵
#### [B. Festive Matrix](https://mirror.codeforces.com/gym/49519229/problem/B)↵
↵
<spoiler summary = "Solution">↵
↵
For each element $a_{ij}$ , if it lies on the main diagonal $(i - j = 0)$, secondary diagonal $(i + j = n - 1)$, middle row $(i = n/2)$, or middle column $(j = n/2)$, it is added to the total sum; otherwise, it is skipped. ↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n = int(input())↵
a = [[*map(int, input().split())] for _ in range(n)]↵
total = 0↵
for i in range(n):↵
for j in range(n):↵
if i - j == 0 or i + j == n - 1 or i == n//2 or j == n//2:↵
total += a[i][j]↵
print(total)↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [C. Winterbourne](https://mirror.codeforces.com/gym/49519229/problem/C)↵
↵
<spoiler summary= "Hint">↵
If there is no one between the $i$-th and $j$-th person then $max(a_i,a_j)$ free chairs should be between them.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
If there is no one between the $i$-th and $j$-th person then $max(a_i,a_j)$ free chairs should be between them.↵
So we should find a permutation $p$ of the array $a$, when $max(p_1,p_2)$ + $max(p_2,p_3)$ $+...$ + $max(p_{n-1},p_n)$ + $max(p_n,p_1)$↵
is minimal.↵
↵
We can assume that the array is non-decreasing $(a_i ≤ a_i +1)$. So $max(p_1,p_2)$ + $max(p_2,p_3)$ $+...$ + $max(p_{n-1},p_n)$ + $max(p_n,p_1)$ will be minimal if the permutation of $p$ is sorted. $max(p_1,p_2)$ = $p_2$, $max(p_2,p_3)$=$p_3$, ... $max(p_{n−1},p_n)$=$p_n$, and $max(p_n,p_1)$=$p_n$.↵
↵
They also sit on $n$ chairs. If we add all of these, we get that the answer is YES if: $n$+ $\sum_{i=1}^{n} (a_i)$ $-$ $min(a_i)$ + $max(a_i)$ $ ≤m $ . ( $a_i$ = {$a_1$,$a_2$,...$a_n$} ) ↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
t = int(input())↵
for _ in range(t):↵
n, m = list(map(int, input().split()))↵
nums = list(map(int, input().split()))↵
if max(nums) - min(nums) + sum(nums) + n > m:↵
print("NO")↵
else:↵
print("YES")↵
↵
```↵
</spoiler>↵
↵
↵
#### [D. Santa's Substrings](https://mirror.codeforces.com/gym/49519229/problem/D)↵
↵
<spoiler summary = "Hint">↵
<p>↵
For a string $a$ to be a substring of another string $b$, the length of $a$ should be less or equal to that of $b$.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
<p>↵
Sort all the strings by their lengths. ↵
Then, for each $i ∈ [0...n−2]$ check that $s_{i}$ is a substring of $s_{i + 1}$. ↵
If it doesn't hold for some $i$ then the answer is "NO". Otherwise, the answer is "YES", and the sorted array is the correct order of the strings.↵
<br/>↵
<br/>↵
If there are several strings of the same length, their order does not matter, because if the answer is "YES", then all the strings of the same length should be equal.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
↵
n = int(input())↵
strings = []↵
↵
for _ in range(n):↵
strings.append(input())↵
↵
strings.sort(key=len)↵
↵
for indx in range(n - 1):↵
if strings[indx] not in strings[indx + 1]:↵
print('NO')↵
exit()↵
↵
print('YES')↵
for string in strings:↵
print(string)↵
↵
```↵
</spoiler>↵
↵
#### [E. Simon's Wordplay](https://mirror.codeforces.com/gym/49519229/problem/E)↵
↵
<spoiler summary = "Hint 1">↵
Since the words only contain five characters $(a, b, c, d, e)$, we can approach the problem by maximizing the story for each character individually.↵
</spoiler>↵
↵
<spoiler summary = "Hint 2">↵
How can we quantify a word's impact on the overall story? ↵
</spoiler>↵
↵
<spoiler summary = "Hint 3">↵
For a given character in a word, the word's contribution is expressed as $x - ( len(word) - x)$, with $x$ denoting the character's occurrences and $(len(word) - x)$ representing the rest of the letters in the word.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
1.Calculate Contributions: For each word and for each character from ‘a’ to ‘e’, calculate the word’s contribution towards that character. ↵
↵
2.Sort Contributions: For each character, sort the words based on their contributions towards that character. Words with higher contributions are sorted higher.↵
↵
3.Select Words: For each character, select the words in the order of their sorted contributions until the sum of the contributions becomes non-positive. This gives us the maximum number of words that can make an interesting story with that character as the majority character.↵
↵
4.Find the Maximum: Repeat the above steps for all characters and keep track of the maximum number of words found. This will be the maximum number of words that can make an interesting story.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
arr = []↵
↵
for i in range(n):↵
arr.append(input())↵
↵
ans = 0↵
↵
#for each character(a,b,c,d,e)↵
for j in range(5):↵
char_count = []↵
char = chr(ord('a') + j)↵
↵
for word in arr:↵
char_count.append(2*(word.count(char)) - len(word))↵
↵
char_count.sort(reverse=True)↵
↵
if char_count[0] <= 0:↵
continue↵
↵
total = char_count[0]↵
i = 1↵
while i < len(char_count) and total + char_count[i] > 0:↵
total += char_count[i]↵
i += 1↵
↵
ans = max(ans,i)↵
print(ans)↵
↵
```↵
</spoiler>↵
↵
#### [F. Enchanted Sorting: The Grid Conundrum](https://mirror.codeforces.com/gym/49519229/problem/F)↵
↵
<spoiler summary = "Approach">↵
<p>↵
First, let's check whether the given grid is good. If it is, we can swap the first column with itself and print $1 1$ as an answer. If it is not, there is a row that has elements that should be swapped.↵
<br/>↵
<br/>↵
Let's say this row is $a$, and let $b$ be the sorted version of $a$. After having these, let's find the set of indices $i$ where $a_{i} ≠ b_{i}$. If there are 3 or more such positions, the answer is $−1$, because by making a single swap we can only correct at most 2 of them.↵
<br/>↵
<br/>↵
But if there are no more than 2 such positions where $a_{i} ≠ b_{i}$, then let's swap the corresponding columns and check whether each row is sorted. If the grid is now good, we have found the answer. If not, the answer is $−1$ because we can not sort $a$ in any other way and get a good grid after that.</p>↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python3↵
↵
↵
↵
t = int(input())↵
for _ in range(t):↵
↵
grid = []↵
n, m = map(int, input().split())↵
↵
for row in range(n):↵
grid.append(list(map(int, input().split())))↵
↵
↵
unsorted_row = None↵
# check if every row is sorted↵
for row in range(n):↵
for col in range(1, m):↵
if grid[row][col - 1] > grid[row][col]:↵
unsorted_row = grid[row]↵
break↵
↵
if unsorted_row != None:↵
break↵
↵
# if all rows are already sorted we can swap the first column with itself as an answer↵
if unsorted_row == None:↵
print(1, 1)↵
continue↵
↵
↵
sorted_version = sorted(unsorted_row)↵
disordered_columns = []↵
can_be_good = True↵
↵
# identify the indices whose values are not in their sorted positions in the unsorted row↵
for indx in range(m):↵
if unsorted_row[indx] != sorted_version[indx]:↵
disordered_columns.append(indx)↵
↵
if len(disordered_columns) >= 3:↵
can_be_good = False↵
break↵
↵
# if those indices are more than 3, we can't make it sorted with a single swap↵
if not can_be_good:↵
print(-1)↵
continue↵
↵
# swap the corresponding columns of those indices↵
for row in range(n):↵
col1, col2 = disordered_columns↵
grid[row][col1], grid[row][col2] = grid[row][col2], grid[row][col1]↵
↵
# check if all rows are sorted after the swap↵
for row in range(n):↵
for col in range(1, m):↵
if grid[row][col - 1] > grid[row][col]:↵
can_be_good = False↵
break↵
↵
if not can_be_good:↵
break↵
↵
if not can_be_good:↵
print(-1)↵
↵
else:↵
print(disordered_columns[0] + 1, disordered_columns[1] + 1)↵
↵
↵
```↵
</spoiler>↵
↵
↵
#### [A. The Lone Element Quest](https://mirror.codeforces.com/gym/495192
↵
#### [A. The Lone Element Quest](https://mirror.codeforces.com/gym/495129/problem/A)↵
↵
<spoiler summary = "Solution">↵
First identify the unique element by counting the occurrences of the numbers and then find it's index in the array.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from collections import Counter↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
nums = list(map(int,input().split()))↵
count = Counter(nums)↵
for key in count:↵
if count[key] == 1:↵
mynum = key↵
for i in range(len(nums)):↵
if nums[i] == mynum:↵
print(i + 1)↵
break↵
```↵
</spoiler>↵
↵
#### [B. Festive Matrix](https://mirror.codeforces.com/gym/4951
↵
<spoiler summary = "Solution">↵
↵
For each element $a_{ij}$ , if it lies on the main diagonal $(i - j = 0)$, secondary diagonal $(i + j = n - 1)$, middle row $(i = n/2)$, or middle column $(j = n/2)$, it is added to the total sum; otherwise, it is skipped. ↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n = int(input())↵
a = [[*map(int, input().split())] for _ in range(n)]↵
total = 0↵
for i in range(n):↵
for j in range(n):↵
if i - j == 0 or i + j == n - 1 or i == n//2 or j == n//2:↵
total += a[i][j]↵
print(total)↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [C. Winterbourne](https://mirror.codeforces.com/gym/4951
↵
<spoiler summary= "Hint">↵
If there is no one between the $i$-th and $j$-th person then $max(a_i,a_j)$ free chairs should be between them.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
If there is no one between the $i$-th and $j$-th person then $max(a_i,a_j)$ free chairs should be between them.↵
So we should find a permutation $p$ of the array $a$, when $max(p_1,p_2)$ + $max(p_2,p_3)$ $+...$ + $max(p_{n-1},p_n)$ + $max(p_n,p_1)$↵
is minimal.↵
↵
We can assume that the array is non-decreasing $(a_i ≤ a_i +1)$. So $max(p_1,p_2)$ + $max(p_2,p_3)$ $+...$ + $max(p_{n-1},p_n)$ + $max(p_n,p_1)$ will be minimal if the permutation of $p$ is sorted. $max(p_1,p_2)$ = $p_2$, $max(p_2,p_3)$=$p_3$, ... $max(p_{n−1},p_n)$=$p_n$, and $max(p_n,p_1)$=$p_n$.↵
↵
They also sit on $n$ chairs. If we add all of these, we get that the answer is YES if: $n$+ $\sum_{i=1}^{n} (a_i)$ $-$ $min(a_i)$ + $max(a_i)$ $ ≤m $ . ( $a_i$ = {$a_1$,$a_2$,...$a_n$} ) ↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
t = int(input())↵
for _ in range(t):↵
n, m = list(map(int, input().split()))↵
nums = list(map(int, input().split()))↵
if max(nums) - min(nums) + sum(nums) + n > m:↵
print("NO")↵
else:↵
print("YES")↵
↵
```↵
</spoiler>↵
↵
↵
#### [D. Santa's Substrings](https://mirror.codeforces.com/gym/4951
↵
<spoiler summary = "Hint">↵
<p>↵
For a string $a$ to be a substring of another string $b$, the length of $a$ should be less or equal to that of $b$.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
<p>↵
Sort all the strings by their lengths. ↵
Then, for each $i ∈ [0...n−2]$ check that $s_{i}$ is a substring of $s_{i + 1}$. ↵
If it doesn't hold for some $i$ then the answer is "NO". Otherwise, the answer is "YES", and the sorted array is the correct order of the strings.↵
<br/>↵
<br/>↵
If there are several strings of the same length, their order does not matter, because if the answer is "YES", then all the strings of the same length should be equal.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
↵
n = int(input())↵
strings = []↵
↵
for _ in range(n):↵
strings.append(input())↵
↵
strings.sort(key=len)↵
↵
for indx in range(n - 1):↵
if strings[indx] not in strings[indx + 1]:↵
print('NO')↵
exit()↵
↵
print('YES')↵
for string in strings:↵
print(string)↵
↵
```↵
</spoiler>↵
↵
#### [E. Simon's Wordplay](https://mirror.codeforces.com/gym/4951
↵
<spoiler summary = "Hint 1">↵
Since the words only contain five characters $(a, b, c, d, e)$, we can approach the problem by maximizing the story for each character individually.↵
</spoiler>↵
↵
<spoiler summary = "Hint 2">↵
How can we quantify a word's impact on the overall story? ↵
</spoiler>↵
↵
<spoiler summary = "Hint 3">↵
For a given character in a word, the word's contribution is expressed as $x - ( len(word) - x)$, with $x$ denoting the character's occurrences and $(len(word) - x)$ representing the rest of the letters in the word.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
1.Calculate Contributions: For each word and for each character from ‘a’ to ‘e’, calculate the word’s contribution towards that character. ↵
↵
2.Sort Contributions: For each character, sort the words based on their contributions towards that character. Words with higher contributions are sorted higher.↵
↵
3.Select Words: For each character, select the words in the order of their sorted contributions until the sum of the contributions becomes non-positive. This gives us the maximum number of words that can make an interesting story with that character as the majority character.↵
↵
4.Find the Maximum: Repeat the above steps for all characters and keep track of the maximum number of words found. This will be the maximum number of words that can make an interesting story.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
arr = []↵
↵
for i in range(n):↵
arr.append(input())↵
↵
ans = 0↵
↵
#for each character(a,b,c,d,e)↵
for j in range(5):↵
char_count = []↵
char = chr(ord('a') + j)↵
↵
for word in arr:↵
char_count.append(2*(word.count(char)) - len(word))↵
↵
char_count.sort(reverse=True)↵
↵
if char_count[0] <= 0:↵
continue↵
↵
total = char_count[0]↵
i = 1↵
while i < len(char_count) and total + char_count[i] > 0:↵
total += char_count[i]↵
i += 1↵
↵
ans = max(ans,i)↵
print(ans)↵
↵
```↵
</spoiler>↵
↵
#### [F. Enchanted Sorting: The Grid Conundrum](https://mirror.codeforces.com/gym/4951
↵
<spoiler summary = "Approach">↵
<p>↵
First, let's check whether the given grid is good. If it is, we can swap the first column with itself and print $1 1$ as an answer. If it is not, there is a row that has elements that should be swapped.↵
<br/>↵
<br/>↵
Let's say this row is $a$, and let $b$ be the sorted version of $a$. After having these, let's find the set of indices $i$ where $a_{i} ≠ b_{i}$. If there are 3 or more such positions, the answer is $−1$, because by making a single swap we can only correct at most 2 of them.↵
<br/>↵
<br/>↵
But if there are no more than 2 such positions where $a_{i} ≠ b_{i}$, then let's swap the corresponding columns and check whether each row is sorted. If the grid is now good, we have found the answer. If not, the answer is $−1$ because we can not sort $a$ in any other way and get a good grid after that.</p>↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python3↵
↵
↵
↵
t = int(input())↵
for _ in range(t):↵
↵
grid = []↵
n, m = map(int, input().split())↵
↵
for row in range(n):↵
grid.append(list(map(int, input().split())))↵
↵
↵
unsorted_row = None↵
# check if every row is sorted↵
for row in range(n):↵
for col in range(1, m):↵
if grid[row][col - 1] > grid[row][col]:↵
unsorted_row = grid[row]↵
break↵
↵
if unsorted_row != None:↵
break↵
↵
# if all rows are already sorted we can swap the first column with itself as an answer↵
if unsorted_row == None:↵
print(1, 1)↵
continue↵
↵
↵
sorted_version = sorted(unsorted_row)↵
disordered_columns = []↵
can_be_good = True↵
↵
# identify the indices whose values are not in their sorted positions in the unsorted row↵
for indx in range(m):↵
if unsorted_row[indx] != sorted_version[indx]:↵
disordered_columns.append(indx)↵
↵
if len(disordered_columns) >= 3:↵
can_be_good = False↵
break↵
↵
# if those indices are more than 3, we can't make it sorted with a single swap↵
if not can_be_good:↵
print(-1)↵
continue↵
↵
# swap the corresponding columns of those indices↵
for row in range(n):↵
col1, col2 = disordered_columns↵
grid[row][col1], grid[row][col2] = grid[row][col2], grid[row][col1]↵
↵
# check if all rows are sorted after the swap↵
for row in range(n):↵
for col in range(1, m):↵
if grid[row][col - 1] > grid[row][col]:↵
can_be_good = False↵
break↵
↵
if not can_be_good:↵
break↵
↵
if not can_be_good:↵
print(-1)↵
↵
else:↵
print(disordered_columns[0] + 1, disordered_columns[1] + 1)↵
↵
↵
```↵
</spoiler>↵
↵
