Contest Link
A) Card Game
This problem uses the greedy technique, in which each player desires to take a card with a high score.
- Let left_pointer and right_pointer represent the beginning and end of the array, respectively.
- Then compare numbers at left_pointer and right_pointer and select the greatest of both.
- Add the score of the chosen cards to the corresponding player.
- 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.
- Continue until the left_pointer and right_pointer cross each other.
- Time complexity: O(n)
- Space Complexity: O(1)
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()
B)Button
if the keyboard key is broken we know it cannot type consecutive letters of length odd number.
which technique can we use to check the length of consecutive similar letters.
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.
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)))
C) Shortest Substring
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.
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)
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)
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)
D) Find K
Simulate with sample examples
Assume the array given was [A,B,C,D] what would be the pattern when you simulate it?
What pattern can we see if we always remove the element at index 0.
-
- 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
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()
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()
E) Drop the Stones
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.
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()