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

37A - Башни

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)