Simply simulate the process using pointers

381A - Сережа и Дима

We can simply simulate the process by using two pointers and initialize two variable to track the values for each player and every time choose the maximum between the values pointed by the two pointer and move that pointer to the opposite direction by one and use a boolean value to keep track of who's turn it is.

The time complexity is $$$O(n)$$$ with $$$O(1)$$$ space

n = int(input())
arr = list(map(int,input().split()))
s = 0
d = 0
l = 0
r = n - 1
turn  = True
while l <= r:
    if arr[l] > arr[r]:
        val = arr[l]
        l += 1
    else:
        val = arr[r]
        r -= 1
    if turn:
        s += val
        turn = False
    else:
        d += val
        turn = True
print(s,d)

1789B - Serval и Инверсионная магия

If $$$s$$$ is palindromic initially, we can operate on the interval [1,n], the answer is $$$"Yes"$$$.

Let's consider the other case. In a palindrome $$$s$$$, for each $$$i$$$ in $$$[1,⌊n/2⌋]$$$, $$${s_i} ={s_n−i+1}$$$ must hold. For those $$$i$$$, we may check whether $$${s_i} = {s_n−i+1}$$$ is true in the initial string. For all the illegal positions $$$i$$$, the operation must contain either $$$i$$$ or $$$n+1−i$$$, but not both. For the legal positions, the operation must contain neither of $$$i$$$ nor $$$n+1−i$$$, or both of them. If the illegal positions is continuous (which means that they are $$$l,l+1,…,r−1,r$$$ for some $$$l$$$ and $$$r$$$), we may operate on the interval $$$[l,r]$$$ (or $$$[n+1−r,n+1−l]$$$), making the string palindromic. The answer is Yes. Otherwise, there must be some legal positions that lie between the illegal ones. Suppose the illegal positions range between $$$[l,r]$$$ (but not continuous), and the operation is $$$[o1,o2]$$$.

Without loss of generality, let the operation lies in the left part of the string. Then $$$o1≤l,r≤o2<n+1−r$$$ must hold to correct all the illegal positions. This interval covers all the legal positions that lie between the illegal ones but does not cover their symmetrical positions. Thus, such kind of operation will produce new illegal positions. In other words, there are no valid operations in this situation. The answer is No.

The time complexity is $$$O(n)$$$ with $$$O(1)$$$ space

def main():
    n = int(input())
    arr = input()
    l = 0
    r = len(arr)-1
    flag = False
    while l < n//2:
        if arr[l] == arr[r]:
            l += 1
            r -= 1
        elif arr[l] != arr[r] and not flag:
            while l < n//2 and arr[l] != arr[r]:
                l += 1
                r -= 1
            flag = True
        elif arr[l] != arr[r] and flag:
            print("No")
            return
    print("Yes")
if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        main()

Try to find which variant of the two pointers could fit this problem

Try to use the for-while combo to solve this problem

978C - Письма

Let's consider that if the first tower consists $$$n$$$ floors, so floor number $$$n+1$$$ belong to the next tower and it would be the first floor for that tower, by using this logic we can track if the current floor is found in the current tower or not. We can use the for while two-pointer variant, We iterate on the first array using for loop and the while loop will track how many of the floor numbers in the second array is in the current tower. for further understanding you can see the implementation below

The time complexity is $$$O(n)$$$ with $$$O(1)$$$ space

n,m = map(int,input().split())  
arr1  = list(map(int,input().split()))
arr2 = list(map(int,input().split()))
r = 0
cur = 0
prev = 0
for i in range(len(arr1)):
    cur += arr1[i]
    while r < len(arr2) and arr2[r] <= cur:
        print(i+1,arr2[r] - prev)
        r += 1
    prev = cur

Try sorting the array first

can we group the students using two pointers

1092B - Формирование команд

First Let's sort the array and try to group the students until the max difference not exceed $$$5$$$. Create two pointers to point to the first student in the group and move the other pointer until the difference exceeds $$$5$$$ and then we move the first pointer until the difference goes to being less than or equal to $$$5$$$ and do the process again. While we do the process we track the maximum number of student in one group and we return that as answer.

The time complexity is $$$O(nlog(n))$$$ with $$$O(1)$$$ space

n = int(input())
arr = list(map(int,input().split()))
arr.sort()
ans = 0
l = 0
r = 0
for i in range(len(arr)):
    while r < len(arr) and arr[r] - arr[l] <= 5:
        r += 1
    ans = max(ans,r-l)
    l += 1
print(ans)

Try to think this problem as a math problem

1656B - Операция вычитания

Let's understand it using this array $$$[a,b,c,d]$$$, First let's choose the $$$d$$$ so the array becomes $$$[a-d,b-d,c-d]$$$ so if we choose the $$$c-d$$$ next the array becomes $$$[a-c,b-c]$$$ since the $$$d$$$ is in both side they will cancel each other, and finally let's choose the $$$b-c$$$ so the array becomes $$$[a-b]$$$. if you look close the final element does only depend in two element of the array, So our task is to find those two value. We can use two pointer to find if there are two values in the array when subtract it gives us the value $$$k$$$.

The time complexity is $$$O(nlog(n))$$$ with $$$O(1)$$$ space

t = int(input())
for _ in range(t):
    n,k = map(int,input().split())
    arr = list(map(int,input().split()))
    arr.sort()
    l = 0
    r = 1
    flag = False
    if n == 1:
        if arr[0] == k:
            print("YES")
        else:
            print("NO")
        continue
    while l < n and r < n:
        if arr[l] + abs(k) == arr[r]:
            flag = True
            break
        elif arr[l] + abs(k) < arr[r]:
            l += 1  
        else:
            r += 1
    if flag:
        print("YES")
    else:
        print("NO")

The Total number of tower is the number of different(Unique) length bar in the array

37A - Towers

Since a Tower can have same length of bars, the total number of Tower will the number of unique numbers in the bars array. To get the maximum height of the tower we calculate for each length $$$x$$$ the number of bars with $$$x$$$ length.

n = int(input())
arr = list(map(int,input().split()))
arr.sort()
towers = 1
height = 1
cur_len = arr[0]
max_height = 0
for i in range(1,len(arr)):
    if arr[i] == cur_len:
        height += 1
    else:
        cur_len = arr[i]
        towers += 1
        max_height = max(max_height,height)
        height = 1
max_height = max(max_height,height)
print(max_height,towers)

n = int(input())
arr = list(map(int,input().split()))
mp = {}
for i in range(len(arr)):
    if arr[i] in mp:
        mp[arr[i]] += 1
    else:
        mp[arr[i]] = 1
print(max(mp.values()),len(mp))

If an Element $$$E$$$ is found on both companies which one should you choose to get maximum income from element $$$E$$$

981B - Businessmen Problems

If there is an element $$$E$$$ that is found on both companies choosing the one with greater income maximize our total income. We can use Map to store each elements income and when we encounter an element twice, we should set the element's income with the maximum of the two incomes. Finally we will Print the sum of all income values in the Map.

The time complexity is $$$O(n)$$$ with $$$O(n)$$$ space

n = int(input())
mp = {}
for i in range(n):
    x,y = map(int,input().split())
    mp[x] = y
m = int(input())
for i in range(m):
    x,y = map(int,input().split())
    if x in mp:
        mp[x] = max(mp[x],y)
    else:
        mp[x] = y
print(sum(mp.values()))

Can we find the smallest value in the array after every operation without simulating

Sort the array and find a way to know how much we subtract from a number until it becomes the smallest in the array

1607C - Minimum Extraction

Let's say we have 3 elements in the array $$$[a,b,c]$$$ and let's assume the array is ordered in increasing order in the first operation, Since $$$a$$$ is the smallest, we remove $$$a$$$ from the array and the array becomes $$$[b-a,c-a]$$$. In The second operation, since $$${b-a}$$$ is the smallest, we chose $$$b-a$$$ and the final element becomes $$${(c-a)} - {(b-a)}$$$ and if you look closely $$$a$$$ is subtracted in both side so we can remove $$$a$$$ from the equation, since it does change the value we get and the equation becomes $$${c-b}$$$ and the array becomes $$$[c-b]$$$. First the smallest was $$${a}$$$, and then the smallest value become $$${b-a}$$$, lastly the smallest value become $$${c-b}$$$, so every time the minimum value in the array will be $$${a_{i+1} - a_{i}}$$$. We are asked to print the maximum number among the smallest we have seen, so first let's sort the array and check for every $$$i$$$ between $$$1$$$ to $$$n$$$ our answer will be $$${ans = max({a_{i+1}} - {a_i},ans)}$$$.

The time complexity is $$$O(nlogn)$$$ with $$$O(1)$$$ space

t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int,input().split()))
    arr.sort()
    res = arr[0]
    for i in range(1,n):
        res = max(res,arr[i]-arr[i-1])
    print(res)

Let's say we need the minimize the cost, So for which fruit should we assign the smallest price to

12C - Fruits

Since we can assign the prices our-self for the fruits in-order to get the smallest price (lucky distribution) we have to give the lowest price to the fruits that appears in the list most because taking the lowest prices as much as we can makes the total price the lowest and we can do the opposite in-order to get largest price (unlucky distribution). So sort the array and iterate in forward direction for the lowest prices and in backward direction for the highest prices and then we use a Map to track the fruits that appears most in the array.

The time complexity is $$$O(nlogn)$$$ with $$$O(n)$$$ space

n,m = map(int,input().split())
arr = list(map(int,input().split()))
fruits = {}
for i in range(m):
    x = input()
    if x not in fruits:
        fruits[x] = 0
    fruits[x] += 1
fruits = sorted(fruits.items(),key=lambda x:x[1],reverse=True)
arr.sort()
large = 0
small = 0
i = 0
l = 0
r = n-1
while i < m:
    small += fruits[l][1]*arr[l]
    large += fruits[l][1]*arr[r]
    i += fruits[l][1]
    l += 1
    r -= 1 
print(small,large)

Try to simulate the process after sorting it.

682B - Алёна и mex

We can simulate the process in order to get the maximum MEX value that we can get. We can start by sorting the array and we make the MEX $$$1$$$ at the start and increment the MEX by 1 if the current element in the array is greater than or equal to the current MEX, Because we can make the value equal to MEX by decrementing it if it is greater than the MEX value. If current value in the array is less than the MEX we just jump that number and go to the next number in the array.

The time complexity is $$$O(nlogn)$$$ with $$$O(1)$$$ space

n = int(input())
arr = list(map(int,input().split()))
arr.sort()
MEX = 1
for i in range(n):
    if arr[i] >= MEX:
        MEX += 1
print(MEX)

263A - Beautiful Matrix

To find the minimum number of moves required to center a single "1" in a 5x5 matrix, we employ a distance-based approach. Imagine the center as a bullseye. First, locate the "1".

Then, calculate the absolute vertical distance |2 — row number of "1"| by counting how many rows it needs to move up or down to reach row number 2 in 0-indexed format. Similarly, calculate the absolute horizontal distance |2-row number of "1"| by counting how many columns it needs to move left or right to reach column number 2 in 0-indexed format.

Finally, add the vertical and horizontal distances to determine the minimum number of moves required. This method works because the "1" can only move up/down or left/right, mimicking independent horizontal and vertical movements needed to reach the center.

for i in range(5):
    row = list(map(int, input().split()))
    for j in range(5):
        if row[j] == 1:
            print(abs(i-2) + abs(j-2))
            break

What kind of Data Structure should you use in-order to know how many times that a single word is written.

1722C - Word Game

To quickly check how many times a single word is written, you should store a dictionary and increment the count for each word every time you see it in the input. Then, you can iterate through each guy, find the number of times their word appears, and update their score based on that. For instance, if a word appears only once, it could get a score of +3, twice could get a +1, and otherwise no score is added.

the time complexity is $$$O(n)$$$ per test-case

t = int(input())
for _ in range(t):
    n = int(input())
    words = []
    dict = {}
    for _ in range(3):
        word = list(map(str, input().split()))
        for x in word:
            dict[x] = dict.get(x, 0) + 1
        words.append(word)
    for i in range(3):
        total = 0
        for word in words[i]:
            if dict[word] == 1:
                total += 3
            elif dict[word] == 2:
                total += 1
        # print each guys total
        print(total, end=" ")
    # print a new line
    print()

First Sort the list and try to pair adjacent numbers

1092B - Teams Forming

To minimize the total number of problems students need to solve for forming $$$n/2$$$ teams we should sort the students by their increasing skill $$$a_{i}$$$. Since only students with identical skill can be teammates, we form teams by pairing adjacent students in the sorted list. However, the challenge arises when there's an unequal skill level between students in the same team. To resolve this, some students in these groups need to increase their skill by solving problems. Therefore, the minimum total problems required is simply the sum of difference between students in unequal skill groups within the sorted list.

So if we sort $$$a$$$ in non-decreasing order then the answer is $$$\sum_{i=1}^{n/2} (a_{2i} - a_{2i-1})$$$

The Time complexity for this is $$$O(nlogn)$$$ because of the sorting

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
res = 0
for i in range(0,n,2):
    res += arr[i+1] - arr[i]
print(res)

Start at day 1 and simulate the process until the $$$n^{th}$$$ day

839A - Arya and Bran

Let $$$c$$$ be number of her candies. At $$${i^{th}}$$$ day , we increase $$$c$$$ by $$${a_i}$$$ ,then we give Bran $$$min(8, c)$$$ . So we decrease this value from $$$k$$$ and also from $$$c$$$. We will print the answer once $$$k$$$ becomes smaller or equal to $$$0$$$. Or we will print $$$- 1$$$ if it doesn't happen after $$$n$$$ days.

The Time complexity for this is $$$O(n)$$$

n,k = map(int, input().split())
arr = list(map(int, input().split()))
candies = 0
for i in range(n):
    candies += arr[i]
    k -= min(8,candies)
    candies -= min(8,candies)
    if k <= 0:
        break
if k <= 0:
    print(i+1)
else:
    print(-1)

The optimal way to compress the songs is to compress it in way it gives us a greater decrement in size i.e greater $$${a_i}-{b_i}$$$

1015C - Songs Compression

Let say we will not compress any song, our size will be equal to the sum of all the intial size of songs, So let's call it sum ,now if we compress the $$${j^{th}}$$$ song how do the sum will change?. It will decrease by $$${a_i}-{b_i}$$$,This suggests that the optimal way to compress the songs is to compress it in non-increasing order of $$${a_i}-{b_i}$$$, because we have to compress songs which gives us a greater decrement in size.

Let's create an array $$$arr$$$ where $$${arr_i} = {a_i} - {b_i}$$$ and Let's sort it in non-increasing order, and then iterate over all $$$j$$$ from $$$0$$$ to $$$n-1$$$. If at the current step $$${sum <= m}$$$ we print $$$j$$$ and exit. Otherwise we set $$$ sum := sum− {arr_j}$$$. After all we have to check again if $$${sum <= m}$$$ we print $$$n$$$. Otherwise print $$$-1$$$.

Time complexity is $$$O(nlogn)$$$ because of sorting.

n,m = map(int, input().split())
arr = []
sum = 0
for i in range(n):
    x,y = map(int, input().split())
    arr.append((x-y))
    sum += x
arr.sort(reverse=True)
for i in range(len(arr)):
    if sum <= m:
        print(i)
        exit()
    sum -= arr[i]
if sum <= m:
    print(n)
else:
    print(-1)