[problem:37A]↵
↵
<spoiler summary="Hint">↵
The Total number of tower is the number of different(Unique) length bar in the array↵
<br/>↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
<h4>[problem:37A]</h4>↵
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.↵
<br/>↵
↵
<spoiler summary="Approach 1: Sorting">↵
We can sort the array so that all the same length value in the array could be grouped together and then traverse on the array to group the same length value bars and while we do that, for each length $x$ we can track the number of bar with $x$ length.↵
↵
The Time complexity will be $O(nlogn)$ with $O(1)$ space complexity↵
<br/>↵
<br/>↵
↵
<spoiler summary="Implementation">↵
```python↵
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)↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Approach 2: Using Hashmap">↵
Another approach is to use a map(dictionary) since we can have information about both the number of unique length bars and the frequency for each unique length bar in the array, we only need to print the number of unique length bar and the maximum number among the frequency of each unique length bar.↵
↵
The Time complexity will be $O(n)$ with $O(n)$ space complexity↵
<br/>↵
<br/>↵
↵
<spoiler summary="Implementation">↵
```python↵
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))↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:981B]↵
↵
<spoiler summary="Hint">↵
If an Element $E$ is found on both companies which one should you choose to get maximum income from element $E$↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
<h4>[problem:981B]</h4>↵
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 <b>Map</b> 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 <b>Map</b>. ↵
↵
The time complexity is $O(n)$ with $O(n)$ space ↵
<br/>↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
```python↵
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()))↵
```↵
</spoiler>↵
↵
[problem:1607C]↵
↵
<spoiler summary="Hint 1">↵
Can we find the smallest value in the array after every operation without simulating ↵
<br/>↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Sort the array and find a way to know how much we subtract from a number until it becomes the smallest in the array ↵
<br/>↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
<h4>[problem:1607C]</h4>↵
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 ↵
<br/>↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
```python↵
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)↵
```↵
</spoiler>↵
↵
[problem:12C]↵
↵
<spoiler summary="Hint">↵
Let's say we need the minimize the cost, So for which fruit should we assign the smallest price to↵
<br/>↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
<h4>[problem:12C]</h4>↵
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 <b>Map</b> to track the fruits that appears most in the array. ↵
↵
The time complexity is $O(nlogn)$ with $O(n)$ space ↵
<br/>↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
```python↵
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)↵
```↵
</spoiler>↵
↵
[problem:628B]↵
↵
<spoiler summary="Hint">↵
Try to simulate the process after sorting it.↵
<br/>↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
<h4>[problem:628B]</h4>↵
We can simulate the process in order to get the maximum <b>MEX</b> value that we can get. We can start by sorting the array and we make the <b>MEX</b> $1$ at the start and increment the <b>MEX</b> by 1 if the current element in the array is greater than or equal to the current <b>MEX</b>, Because we can make the value equal to <b>MEX</b> by decrementing it if it is greater than the <b>MEX</b> value. If current value in the array is less than the <b>MEX</b> we just jump that number and go to the next number in the array.↵
↵
The time complexity is $O(nlogn)$ with $O(1)$ space ↵
<br/>↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
```python↵
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)↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Hint">↵
The Total number of tower is the number of different(Unique) length bar in the array↵
<br/>↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
<h4>[problem:37A]</h4>↵
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.↵
<br/>↵
↵
<spoiler summary="Approach 1: Sorting">↵
We can sort the array so that all the same length value in the array could be grouped together and then traverse on the array to group the same length value bars and while we do that, for each length $x$ we can track the number of bar with $x$ length.↵
↵
The Time complexity will be $O(nlogn)$ with $O(1)$ space complexity↵
<br/>↵
<br/>↵
↵
<spoiler summary="Implementation">↵
```python↵
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)↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Approach 2: Using Hashmap">↵
Another approach is to use a map(dictionary) since we can have information about both the number of unique length bars and the frequency for each unique length bar in the array, we only need to print the number of unique length bar and the maximum number among the frequency of each unique length bar.↵
↵
The Time complexity will be $O(n)$ with $O(n)$ space complexity↵
<br/>↵
<br/>↵
↵
<spoiler summary="Implementation">↵
```python↵
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))↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:981B]↵
↵
<spoiler summary="Hint">↵
If an Element $E$ is found on both companies which one should you choose to get maximum income from element $E$↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
<h4>[problem:981B]</h4>↵
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 <b>Map</b> 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 <b>Map</b>. ↵
↵
The time complexity is $O(n)$ with $O(n)$ space ↵
<br/>↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
```python↵
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()))↵
```↵
</spoiler>↵
↵
[problem:1607C]↵
↵
<spoiler summary="Hint 1">↵
Can we find the smallest value in the array after every operation without simulating ↵
<br/>↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Sort the array and find a way to know how much we subtract from a number until it becomes the smallest in the array ↵
<br/>↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
<h4>[problem:1607C]</h4>↵
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 ↵
<br/>↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
```python↵
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)↵
```↵
</spoiler>↵
↵
[problem:12C]↵
↵
<spoiler summary="Hint">↵
Let's say we need the minimize the cost, So for which fruit should we assign the smallest price to↵
<br/>↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
<h4>[problem:12C]</h4>↵
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 <b>Map</b> to track the fruits that appears most in the array. ↵
↵
The time complexity is $O(nlogn)$ with $O(n)$ space ↵
<br/>↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
```python↵
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)↵
```↵
</spoiler>↵
↵
[problem:628B]↵
↵
<spoiler summary="Hint">↵
Try to simulate the process after sorting it.↵
<br/>↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
<h4>[problem:628B]</h4>↵
We can simulate the process in order to get the maximum <b>MEX</b> value that we can get. We can start by sorting the array and we make the <b>MEX</b> $1$ at the start and increment the <b>MEX</b> by 1 if the current element in the array is greater than or equal to the current <b>MEX</b>, Because we can make the value equal to <b>MEX</b> by decrementing it if it is greater than the <b>MEX</b> value. If current value in the array is less than the <b>MEX</b> we just jump that number and go to the next number in the array.↵
↵
The time complexity is $O(nlogn)$ with $O(1)$ space ↵
<br/>↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
```python↵
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)↵
```↵
</spoiler>↵
↵
