[Here](https://codeforces.com/gym/496495) is the mashup link (the problems are from Codeforces' problem set).↵
↵
#### [A. Word Quest](https://codeforces.com/gym/496495/problem/A)↵
↵
<spoiler summary = "Solution">↵
One way to solve the problem is by iterating through the grid and, when a letter is found, continuing downwards until the entire word is obtained.↵
↵
However, there is a faster coding approach: simply input each character and output it if it is not a dot. This method works because the characters are inputted in the same top-to-bottom order. The time complexity remains constant, denoted as O(1), regardless of the approach used.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
↵
tc = int(input())↵
↵
for _ in range(tc):↵
result = []↵
for i in range(8):↵
result += [char for char in input() if char.isalpha()] ↵
↵
print("".join(result))↵
↵
↵
↵
```↵
</spoiler>↵
↵
Complexity: O(1).↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
#### [B. Z-OrderSort](https://codeforces.com/gym/496495/problem/B)↵
↵
<spoiler summary = "Solution">↵
It is apparent that we can perform a z-sort on any given array, denoted as $(nums)$ Let's define $(k)$ as the count of even positions within $(nums)$ We can assign the maximum $(k)$ elements to those even positions, and distribute the remaining $(n-k)$ elements to the odd positions. It's clear that the resulting array will be z-sorted.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
↵
n = int(input())↵
nums = list(map(int,input().split()))↵
↵
result = [0]*n↵
↵
nums.sort()↵
↵
k = n-1↵
for i in range(1, n, 2):↵
result[i] = nums[k]↵
k-= 1↵
↵
for i in range(0, n, 2):↵
result[i] = nums[k]↵
k-= 1↵
↵
print(*result)↵
↵
↵
```↵
</spoiler>↵
↵
Complexity: O(nlogn)↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
#### [C. Less or Equal](https://codeforces.com/gym/496495/problem/C)↵
↵
↵
<spoiler summary = "Solution">↵
↵
We will do the following steps inorder to solve it↵
Sort the given sequence in non-decreasing order.↵
The first $(k)$ elements of the sorted sequence will be the smallest $(k)$ elements.↵
Any number smaller than or equal to $(a[k-1])$' will have exactly $(k)$ elements less than or equal to it.↵
If is $(k)$ is 0 , the smallest possible value is 1.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
↵
n, k = list(map(int, input().split()))↵
↵
nums = list(map(int, input().split()))↵
↵
nums.sort()↵
↵
if n==k:↵
print(nums[k-1])↵
elif n > k and nums[k] > nums[k-1]:↵
print(nums[k-1])↵
elif k == 0 and nums[0] > 1:↵
print(1)↵
else:↵
print(-1)↵
↵
↵
```↵
</spoiler>↵
↵
Complexity: O(nlogn)↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
#### [D. Line](https://codeforces.com/gym/496495/problem/D)↵
↵
↵
<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. ↵
↵
Consider a line represented by the string "LRRLL". If the ith person turns around, the value of the line will change by specific amounts for each person. For example, if the second person turns around, they will see 3 people before and 1 person after, so the value of the line changes by -2. ↵
↵
Now, to solve this problem efficiently, we can follow these steps: ↵
↵
1. Calculate the change in value for each person in the line if they were to turn around. This will create an array or list of values representing the change in value for each person. ↵
2. Sort this array or list of values in decreasing order. This will help us determine which person turning around will yield the maximum increase in the overall value. ↵
3. Calculate the total values of each person in the line as they were in their original position. ↵
4. Create a result array↵
5. Traverse through the sorted list of values ↵
I. assign the sum of total values and each values in the sorted array to the total sum↵
II. append this result to the result array↵
↵
This approach, based on sorting the value changes and then greedily selecting the individuals whose turning around increases the overall value, ensures a time complexity of O(n log n) per test case, where 'n' represents the number of people in the line.↵
↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
for _ in range(int(input())):↵
n = int(input())↵
lines = input()↵
values = []↵
totCount = 0↵
# getting the total counts of each person in current line↵
# and getting the maximized count of each persons by swapping the persons view direction↵
for i, line in enumerate(lines):↵
if line == 'L':↵
totCount += i↵
values.append(max(i, n - i - 1) - i)↵
else:↵
totCount += (n - i - 1)↵
values.append(max(i, n - i - 1) - (n - i - 1))↵
↵
# sort values in decreasing order to maximize the counts↵
values.sort(reverse=True)↵
for i in range(len(values)):↵
totCount += values[i]↵
values[i] = totCount↵
↵
print(*values)↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
#### [E. OR in Matrix](https://codeforces.com/gym/496495/problem/E)↵
↵
↵
<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. ↵
↵
Create a separate matrix with the same dimension and size and Initially, set all all values of this newly created matrix to $(1).↵
↵
If any corresponding cell in the given matrix is $(0) make all the rows and columns of that corresponding cell in the newly created matrix to $(0).↵
↵
Examine this newly created matrix if it can generate the given matrix. If it cannot produce the given matrix, the answer is clearly “NO”.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n, m = map(int, input().split())↵
matrix = []↵
for _ in range(n):↵
matrix.append(list(map(int, input().split())))↵
↵
# reconstructing the original matrix↵
original = [[1 for _ in range(m)] for _ in range(n)]↵
for i in range(n):↵
for j in range(m):↵
if matrix[i][j] == 0:↵
for k in range(n):↵
original[k][j] = 0↵
for t in range(m):↵
original[i][t] = 0↵
# perform the OR operation on the original matrix↵
newMatrix = [[0 for _ in range(m)] for _ in range(n)]↵
for i in range(n):↵
for j in range(m):↵
newMatrix[i][j] |= int(any(original[i] + [original[k][j] for k in range(n)]))↵
↵
# compare the new matrix with the given matrix↵
if newMatrix == matrix:↵
print('YES')↵
for i in range(n):↵
print(*original[i])↵
else:↵
print('NO')↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
#### [A. Word Quest](https://codeforces.com/gym/496495/problem/A)↵
↵
<spoiler summary = "Solution">↵
One way to solve the problem is by iterating through the grid and, when a letter is found, continuing downwards until the entire word is obtained.↵
↵
However, there is a faster coding approach: simply input each character and output it if it is not a dot. This method works because the characters are inputted in the same top-to-bottom order. The time complexity remains constant, denoted as O(1), regardless of the approach used.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
↵
tc = int(input())↵
↵
for _ in range(tc):↵
result = []↵
for i in range(8):↵
result += [char for char in input() if char.isalpha()] ↵
↵
print("".join(result))↵
↵
↵
↵
```↵
</spoiler>↵
↵
Complexity: O(1).↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
#### [B. Z-OrderSort](https://codeforces.com/gym/496495/problem/B)↵
↵
<spoiler summary = "Solution">↵
It is apparent that we can perform a z-sort on any given array, denoted as $(nums)$ Let's define $(k)$ as the count of even positions within $(nums)$ We can assign the maximum $(k)$ elements to those even positions, and distribute the remaining $(n-k)$ elements to the odd positions. It's clear that the resulting array will be z-sorted.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
↵
n = int(input())↵
nums = list(map(int,input().split()))↵
↵
result = [0]*n↵
↵
nums.sort()↵
↵
k = n-1↵
for i in range(1, n, 2):↵
result[i] = nums[k]↵
k-= 1↵
↵
for i in range(0, n, 2):↵
result[i] = nums[k]↵
k-= 1↵
↵
print(*result)↵
↵
↵
```↵
</spoiler>↵
↵
Complexity: O(nlogn)↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
#### [C. Less or Equal](https://codeforces.com/gym/496495/problem/C)↵
↵
↵
<spoiler summary = "Solution">↵
↵
We will do the following steps inorder to solve it↵
Sort the given sequence in non-decreasing order.↵
The first $(k)$ elements of the sorted sequence will be the smallest $(k)$ elements.↵
Any number smaller than or equal to $(a[k-1])$' will have exactly $(k)$ elements less than or equal to it.↵
If is $(k)$ is 0 , the smallest possible value is 1.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
↵
n, k = list(map(int, input().split()))↵
↵
nums = list(map(int, input().split()))↵
↵
nums.sort()↵
↵
if n==k:↵
print(nums[k-1])↵
elif n > k and nums[k] > nums[k-1]:↵
print(nums[k-1])↵
elif k == 0 and nums[0] > 1:↵
print(1)↵
else:↵
print(-1)↵
↵
↵
```↵
</spoiler>↵
↵
Complexity: O(nlogn)↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
#### [D. Line](https://codeforces.com/gym/496495/problem/D)↵
↵
↵
<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. ↵
↵
Consider a line represented by the string "LRRLL". If the ith person turns around, the value of the line will change by specific amounts for each person. For example, if the second person turns around, they will see 3 people before and 1 person after, so the value of the line changes by -2. ↵
↵
Now, to solve this problem efficiently, we can follow these steps: ↵
↵
1. Calculate the change in value for each person in the line if they were to turn around. This will create an array or list of values representing the change in value for each person. ↵
2. Sort this array or list of values in decreasing order. This will help us determine which person turning around will yield the maximum increase in the overall value. ↵
3. Calculate the total values of each person in the line as they were in their original position. ↵
4. Create a result array↵
5. Traverse through the sorted list of values ↵
I. assign the sum of total values and each values in the sorted array to the total sum↵
II. append this result to the result array↵
↵
This approach, based on sorting the value changes and then greedily selecting the individuals whose turning around increases the overall value, ensures a time complexity of O(n log n) per test case, where 'n' represents the number of people in the line.↵
↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
for _ in range(int(input())):↵
n = int(input())↵
lines = input()↵
values = []↵
totCount = 0↵
# getting the total counts of each person in current line↵
# and getting the maximized count of each persons by swapping the persons view direction↵
for i, line in enumerate(lines):↵
if line == 'L':↵
totCount += i↵
values.append(max(i, n - i - 1) - i)↵
else:↵
totCount += (n - i - 1)↵
values.append(max(i, n - i - 1) - (n - i - 1))↵
↵
# sort values in decreasing order to maximize the counts↵
values.sort(reverse=True)↵
for i in range(len(values)):↵
totCount += values[i]↵
values[i] = totCount↵
↵
print(*values)↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
#### [E. OR in Matrix](https://codeforces.com/gym/496495/problem/E)↵
↵
↵
<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. ↵
↵
Create a separate matrix with the same dimension and size and Initially, set all all values of this newly created matrix to $(1).↵
↵
If any corresponding cell in the given matrix is $(0) make all the rows and columns of that corresponding cell in the newly created matrix to $(0).↵
↵
Examine this newly created matrix if it can generate the given matrix. If it cannot produce the given matrix, the answer is clearly “NO”.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n, m = map(int, input().split())↵
matrix = []↵
for _ in range(n):↵
matrix.append(list(map(int, input().split())))↵
↵
# reconstructing the original matrix↵
original = [[1 for _ in range(m)] for _ in range(n)]↵
for i in range(n):↵
for j in range(m):↵
if matrix[i][j] == 0:↵
for k in range(n):↵
original[k][j] = 0↵
for t in range(m):↵
original[i][t] = 0↵
# perform the OR operation on the original matrix↵
newMatrix = [[0 for _ in range(m)] for _ in range(n)]↵
for i in range(n):↵
for j in range(m):↵
newMatrix[i][j] |= int(any(original[i] + [original[k][j] for k in range(n)]))↵
↵
# compare the new matrix with the given matrix↵
if newMatrix == matrix:↵
print('YES')↵
for i in range(n):↵
print(*original[i])↵
else:↵
print('NO')↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
