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

1722C - Word Game

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)