[**Contest Link**](https://codeforces.com/gym/424075)↵
================↵
↵
#### [A) Card Game](https://codeforces.com/gym/424075/problem/A)↵
↵
<spoiler summary="Approach">↵
This problem uses the greedy technique, in which each player desires to take a card with a high score.↵
</spoiler>↵
↵
<spoiler summary="Steps">↵
1. Let left_pointer and right_pointer represent the beginning and end of the array, respectively.↵
2. Then compare numbers at left_pointer and right_pointer and select the greatest of both.↵
3. Add the score of the chosen cards to the corresponding player.↵
4. The player turn can be identified by variable 'turn'. If turn is an even number, player 1(Wube) takes the turn; otherwise, player 2(Henok) takes the turn.↵
5. Continue until the left_pointer and right_pointer cross each other.↵
↵
- **Time complexity: O(n)**↵
- **Space Complexity: O(1)**↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
def main():↵
#input↵
length = int(input())↵
numbers = list(map(int, input().split()))↵
↵
#initialize pointers↵
left = 0↵
right = length - 1↵
turn = 0↵
wube_score = 0↵
henok_score = 0↵
↵
while left <= right:↵
cur_max = 0↵
↵
if numbers[left] > numbers[right]:↵
cur_max = numbers[left]↵
left += 1↵
↵
else:↵
cur_max = numbers[right]↵
right -= 1↵
↵
if turn % 2 == 0:↵
wube_score += cur_max↵
else:↵
henok_score += cur_max↵
↵
turn += 1↵
↵
print(wube_score, henok_score)↵
↵
main()↵
~~~~~↵
↵
↵
</spoiler>↵
↵
#### [B)Button](https://codeforces.com/gym/424075/problem/B)↵
↵
<spoiler summary="Hint 1">↵
if the keyboard key is broken we know it cannot type consecutive letters of length odd number.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
which technique can we use to check the length of consecutive similar letters.↵
</spoiler>↵
↵
<spoiler summary="Approach">↵
Since we want to know how many of consecutive similar letters are there, we can use two pointers, one to go through the string and one to count consecutive similar letters. ↵
↵
Then we check if that length is odd or even. If it is odd we can consider it as a working button and since we don't want to have duplicate buttons, we can use set.↵
↵
Finally we will cast it to list and sort it to get the answer in alphabetical order and print it by joining the elements.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
tests = int(input())↵
for _ in range(tests):↵
string = input()↵
size = len(string)↵
left = 0↵
answer = set()↵
while left < size:↵
right = left + 1↵
count = 1↵
while right < size and string[right] == string[right - 1]:↵
count += 1↵
right += 1↵
left += 1↵
if count % 2 == 1 and string[left] not in answer:↵
answer.add(string[left])↵
left += 1↵
answer = list(answer)↵
print("".join(sorted(answer)))↵
~~~~~↵
↵
</spoiler>↵
↵
↵
#### [C) Shortest Substring](https://codeforces.com/gym/424075/problem/C)↵
↵
<spoiler summary="Approach 1">↵
The main idea of my solution is that the answer should look like **abb...bbbbbc**: one character of type a, a block of characters of type b, and one character of type c. If we find all blocks of consecutive equal characters in our string, each candidate for the answer can be obtained by expanding a block to the left and to the right by exactly one character. So the total length of all candidates is **O(n)**, and we can check them all.↵
↵
Why does the answer look like abb...bbbbbc? If the first character of the substring appears somewhere else in it, it can be deleted. The same applies for the last character. So, the first and the last characters should be different, and should not appear anywhere else within the string. Since there are only three types of characters, the answer always looks like abb...bbbbbc.↵
</spoiler>↵
↵
<spoiler summary="Code 1">↵
↵
~~~~~↵
from collections import defaultdict↵
↵
num_tests = int(input())↵
↵
for _ in range(num_tests):↵
string = input()↵
len_str = len(string)↵
ans = len_str + 1↵
↵
freq = []↵
for i in range(len_str):↵
cur_char = string[i]↵
if len(freq) == 0 or freq[-1][0] != cur_char:↵
freq.append([cur_char, 1])↵
else:↵
freq[-1][1] += 1↵
↵
freq_size = len(freq)↵
for i in range(1, freq_size - 1):↵
if freq[i - 1][0] != freq[i + 1][0]:↵
ans = min(ans, freq[i][1] + 2)↵
↵
if ans == len_str + 1:↵
ans = 0↵
↵
print(ans)↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Approach 2">↵
We can use **the sliding window technique** to solve this problem. We extend our window until we find all the three characters 1, 2, 3. And we will try to shorten the interval as much as we can but we have to make sure that the three numbers are present in the substring. ↵
↵
- **Time Complexity: O(n)** ↵
- **Space Complexity: O(n)**↵
</spoiler>↵
↵
↵
<spoiler summary="Code 2">↵
↵
~~~~~↵
from collections import defaultdict↵
↵
num_tests = int(input())↵
↵
for _ in range(num_tests):↵
string = input()↵
len_str = len(string)↵
occurence = defaultdict(int)↵
↵
left = 0↵
contained = 0↵
ans = len_str + 1↵
for right in range(len_str):↵
char_at_right = string[right]↵
occurence[char_at_right] += 1↵
↵
if occurence[char_at_right] == 1:↵
contained += 1↵
↵
while contained >= 3:↵
char_at_left = string[left]↵
occurence[char_at_left] -= 1↵
↵
if occurence[char_at_left] == 0:↵
contained -= 1↵
↵
left += 1↵
↵
if left > 0:↵
ans = min(ans, right - left + 2)↵
↵
if ans == len_str + 1:↵
ans = 0↵
↵
print(ans)↵
↵
↵
~~~~~↵
↵
</spoiler>↵
↵
#### [D) Find K](https://codeforces.com/gym/424075/problem/D)↵
↵
<spoiler summary="Hint 1">↵
Simulate with sample examples↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Assume the array given was [A,B,C,D] what would be the pattern when you simulate it?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
What pattern can we see if we always remove the element at index 0.↵
</spoiler>↵
↵
↵
<spoiler summary="Approach">↵
- - let say we are given an array [A,B,C,D] and Let's always remove the element at index 0 and see the resulting pattern↵
- - first we delete A and subtract from the rest↵
- - * [B — A, C — A, D — A] ↵
- - Then we delete the next sequence which is B — A ↵
- - * [C — A — (B — A), D — A — (B — A)] ↵
- - * which simplifies to [C — B, D — B] ↵
- - Finally we delete the next sequence which is C — B↵
- - * [D — B — (C — B)] ↵
- - * which simplifies to [D — C] ↵
↵
**- So we can see that we only need two number whose difference is equal to k.**↵
so basically we need to find two numbers that meet the condition and print YES and if we can't get print NO↵
</spoiler>↵
↵
<spoiler summary="Code 1">↵
↵
~~~~~↵
def solve():↵
n , k = map(int , input().split())↵
nums = list(map(int, input().split()))↵
↵
i = 0↵
j = 1↵
found = False↵
nums.sort()↵
while not found and j < n:↵
difference = nums[j] - nums[i]↵
if difference == k:↵
found = True↵
elif difference > k:↵
i += 1↵
else:↵
j += 1↵
↵
if found:↵
print("YES")↵
else:↵
print("NO")↵
↵
def main():↵
t = int(input())↵
↵
for _ in range(t):↵
solve()↵
↵
main()↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code 2">↵
↵
~~~~~↵
def solve():↵
n, k = map(int, input().split())↵
a = list(map(int, input().split()))↵
↵
occured = set()↵
ok = False↵
i = 0↵
↵
while not ok and i < n:↵
x = a[i] - k↵
y = a[i] + k↵
↵
if x in occured:↵
ok = True↵
↵
if y in occured:↵
ok = True↵
↵
occured.add(a[i])↵
i += 1↵
↵
if ok:↵
print("YES")↵
else:↵
print("NO")↵
↵
↵
def main():↵
t = int(input())↵
for i in range(t):↵
solve()↵
main()↵
~~~~~↵
↵
↵
</spoiler>↵
↵
#### [E) Drop the Stones](https://codeforces.com/gym/424075/problem/E)↵
↵
<spoiler summary="Approach">↵
This solution involves solving for each column individually, by starting from the bottom and working towards the top. For each column, the row of the last obstacle seen is kept track of and initially set to n + 1, treating the floor as the (n + 1)th row of obstacles. If a new obstacle is encountered, the last row variable is updated. If a stone is encountered, it is moved to the row above the last obstacle seen and the last row variable is decreased by 1. This solution has a time complexity of **O(nm)** and is efficient, however slower alternatives that run in **O(n^2*m)** that simulate each stone falling are also accepted.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
cases = int(input())↵
↵
for _ in range(cases):↵
ROWS, COLS = map(int , input().split())↵
↵
grid = []↵
↵
for _ in range(ROWS):↵
temp = list(input())↵
grid.append(temp)↵
↵
for cur_col in range(COLS):↵
cur = ROWS↵
for cur_row in range(ROWS - 1, -1, -1):↵
↵
if grid[cur_row][cur_col] == '*':↵
cur -= 1↵
↵
if cur_row != cur:↵
grid[cur][cur_col] = '*'↵
grid[cur_row][cur_col] = '.'↵
↵
elif grid[cur_row][cur_col] == 'o':↵
cur = cur_row↵
↵
↵
for cur_row in range(ROWS):↵
for cur_col in range(COLS):↵
print(grid[cur_row][cur_col],end='')↵
print()↵
print()↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
================↵
↵
#### [A) Card Game](https://codeforces.com/gym/424075/problem/A)↵
↵
<spoiler summary="Approach">↵
This problem uses the greedy technique, in which each player desires to take a card with a high score.↵
</spoiler>↵
↵
<spoiler summary="Steps">↵
1. Let left_pointer and right_pointer represent the beginning and end of the array, respectively.↵
2. Then compare numbers at left_pointer and right_pointer and select the greatest of both.↵
3. Add the score of the chosen cards to the corresponding player.↵
4. The player turn can be identified by variable 'turn'. If turn is an even number, player 1(Wube) takes the turn; otherwise, player 2(Henok) takes the turn.↵
5. Continue until the left_pointer and right_pointer cross each other.↵
↵
- **Time complexity: O(n)**↵
- **Space Complexity: O(1)**↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
def main():↵
#input↵
length = int(input())↵
numbers = list(map(int, input().split()))↵
↵
#initialize pointers↵
left = 0↵
right = length - 1↵
turn = 0↵
wube_score = 0↵
henok_score = 0↵
↵
while left <= right:↵
cur_max = 0↵
↵
if numbers[left] > numbers[right]:↵
cur_max = numbers[left]↵
left += 1↵
↵
else:↵
cur_max = numbers[right]↵
right -= 1↵
↵
if turn % 2 == 0:↵
wube_score += cur_max↵
else:↵
henok_score += cur_max↵
↵
turn += 1↵
↵
print(wube_score, henok_score)↵
↵
main()↵
~~~~~↵
↵
↵
</spoiler>↵
↵
#### [B)Button](https://codeforces.com/gym/424075/problem/B)↵
↵
<spoiler summary="Hint 1">↵
if the keyboard key is broken we know it cannot type consecutive letters of length odd number.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
which technique can we use to check the length of consecutive similar letters.↵
</spoiler>↵
↵
<spoiler summary="Approach">↵
Since we want to know how many of consecutive similar letters are there, we can use two pointers, one to go through the string and one to count consecutive similar letters. ↵
↵
Then we check if that length is odd or even. If it is odd we can consider it as a working button and since we don't want to have duplicate buttons, we can use set.↵
↵
Finally we will cast it to list and sort it to get the answer in alphabetical order and print it by joining the elements.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
tests = int(input())↵
for _ in range(tests):↵
string = input()↵
size = len(string)↵
left = 0↵
answer = set()↵
while left < size:↵
right = left + 1↵
count = 1↵
while right < size and string[right] == string[right - 1]:↵
count += 1↵
right += 1↵
left += 1↵
if count % 2 == 1 and string[left] not in answer:↵
answer.add(string[left])↵
left += 1↵
answer = list(answer)↵
print("".join(sorted(answer)))↵
~~~~~↵
↵
</spoiler>↵
↵
↵
#### [C) Shortest Substring](https://codeforces.com/gym/424075/problem/C)↵
↵
<spoiler summary="Approach 1">↵
The main idea of my solution is that the answer should look like **abb...bbbbbc**: one character of type a, a block of characters of type b, and one character of type c. If we find all blocks of consecutive equal characters in our string, each candidate for the answer can be obtained by expanding a block to the left and to the right by exactly one character. So the total length of all candidates is **O(n)**, and we can check them all.↵
↵
Why does the answer look like abb...bbbbbc? If the first character of the substring appears somewhere else in it, it can be deleted. The same applies for the last character. So, the first and the last characters should be different, and should not appear anywhere else within the string. Since there are only three types of characters, the answer always looks like abb...bbbbbc.↵
</spoiler>↵
↵
<spoiler summary="Code 1">↵
↵
~~~~~↵
from collections import defaultdict↵
↵
num_tests = int(input())↵
↵
for _ in range(num_tests):↵
string = input()↵
len_str = len(string)↵
ans = len_str + 1↵
↵
freq = []↵
for i in range(len_str):↵
cur_char = string[i]↵
if len(freq) == 0 or freq[-1][0] != cur_char:↵
freq.append([cur_char, 1])↵
else:↵
freq[-1][1] += 1↵
↵
freq_size = len(freq)↵
for i in range(1, freq_size - 1):↵
if freq[i - 1][0] != freq[i + 1][0]:↵
ans = min(ans, freq[i][1] + 2)↵
↵
if ans == len_str + 1:↵
ans = 0↵
↵
print(ans)↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Approach 2">↵
We can use **the sliding window technique** to solve this problem. We extend our window until we find all the three characters 1, 2, 3. And we will try to shorten the interval as much as we can but we have to make sure that the three numbers are present in the substring. ↵
↵
- **Time Complexity: O(n)** ↵
- **Space Complexity: O(n)**↵
</spoiler>↵
↵
↵
<spoiler summary="Code 2">↵
↵
~~~~~↵
from collections import defaultdict↵
↵
num_tests = int(input())↵
↵
for _ in range(num_tests):↵
string = input()↵
len_str = len(string)↵
occurence = defaultdict(int)↵
↵
left = 0↵
contained = 0↵
ans = len_str + 1↵
for right in range(len_str):↵
char_at_right = string[right]↵
occurence[char_at_right] += 1↵
↵
if occurence[char_at_right] == 1:↵
contained += 1↵
↵
while contained >= 3:↵
char_at_left = string[left]↵
occurence[char_at_left] -= 1↵
↵
if occurence[char_at_left] == 0:↵
contained -= 1↵
↵
left += 1↵
↵
if left > 0:↵
ans = min(ans, right - left + 2)↵
↵
if ans == len_str + 1:↵
ans = 0↵
↵
print(ans)↵
↵
↵
~~~~~↵
↵
</spoiler>↵
↵
#### [D) Find K](https://codeforces.com/gym/424075/problem/D)↵
↵
<spoiler summary="Hint 1">↵
Simulate with sample examples↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Assume the array given was [A,B,C,D] what would be the pattern when you simulate it?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
What pattern can we see if we always remove the element at index 0.↵
</spoiler>↵
↵
↵
<spoiler summary="Approach">↵
- - let say we are given an array [A,B,C,D] and Let's always remove the element at index 0 and see the resulting pattern↵
- - first we delete A and subtract from the rest↵
- - * [B — A, C — A, D — A] ↵
- - Then we delete the next sequence which is B — A ↵
- - * [C — A — (B — A), D — A — (B — A)] ↵
- - * which simplifies to [C — B, D — B] ↵
- - Finally we delete the next sequence which is C — B↵
- - * [D — B — (C — B)] ↵
- - * which simplifies to [D — C] ↵
↵
**- So we can see that we only need two number whose difference is equal to k.**↵
so basically we need to find two numbers that meet the condition and print YES and if we can't get print NO↵
</spoiler>↵
↵
<spoiler summary="Code 1">↵
↵
~~~~~↵
def solve():↵
n , k = map(int , input().split())↵
nums = list(map(int, input().split()))↵
↵
i = 0↵
j = 1↵
found = False↵
nums.sort()↵
while not found and j < n:↵
difference = nums[j] - nums[i]↵
if difference == k:↵
found = True↵
elif difference > k:↵
i += 1↵
else:↵
j += 1↵
↵
if found:↵
print("YES")↵
else:↵
print("NO")↵
↵
def main():↵
t = int(input())↵
↵
for _ in range(t):↵
solve()↵
↵
main()↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code 2">↵
↵
~~~~~↵
def solve():↵
n, k = map(int, input().split())↵
a = list(map(int, input().split()))↵
↵
occured = set()↵
ok = False↵
i = 0↵
↵
while not ok and i < n:↵
x = a[i] - k↵
y = a[i] + k↵
↵
if x in occured:↵
ok = True↵
↵
if y in occured:↵
ok = True↵
↵
occured.add(a[i])↵
i += 1↵
↵
if ok:↵
print("YES")↵
else:↵
print("NO")↵
↵
↵
def main():↵
t = int(input())↵
for i in range(t):↵
solve()↵
main()↵
~~~~~↵
↵
↵
</spoiler>↵
↵
#### [E) Drop the Stones](https://codeforces.com/gym/424075/problem/E)↵
↵
<spoiler summary="Approach">↵
This solution involves solving for each column individually, by starting from the bottom and working towards the top. For each column, the row of the last obstacle seen is kept track of and initially set to n + 1, treating the floor as the (n + 1)th row of obstacles. If a new obstacle is encountered, the last row variable is updated. If a stone is encountered, it is moved to the row above the last obstacle seen and the last row variable is decreased by 1. This solution has a time complexity of **O(nm)** and is efficient, however slower alternatives that run in **O(n^2*m)** that simulate each stone falling are also accepted.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
cases = int(input())↵
↵
for _ in range(cases):↵
ROWS, COLS = map(int , input().split())↵
↵
grid = []↵
↵
for _ in range(ROWS):↵
temp = list(input())↵
grid.append(temp)↵
↵
for cur_col in range(COLS):↵
cur = ROWS↵
for cur_row in range(ROWS - 1, -1, -1):↵
↵
if grid[cur_row][cur_col] == '*':↵
cur -= 1↵
↵
if cur_row != cur:↵
grid[cur][cur_col] = '*'↵
grid[cur_row][cur_col] = '.'↵
↵
elif grid[cur_row][cur_col] == 'o':↵
cur = cur_row↵
↵
↵
for cur_row in range(ROWS):↵
for cur_col in range(COLS):↵
print(grid[cur_row][cur_col],end='')↵
print()↵
print()↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
