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.

628B - New Skateboard

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)