Contest Link

This problem uses the greedy technique, in which each player desires to take a card with a high score.

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)

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()

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)))

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)
    
        

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()

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()