[problem:263A]↵
↵
<spoiler summary="Tutorial">↵
↵
<h4>[problem:263A]</h4>↵
↵
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.↵
<br/>↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
```python↵
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↵
```↵
</spoiler>↵
↵
[problem:1722C]↵
↵
<spoiler summary="Hint">↵
What kind of Data Structure should you use in-order to know how many times that a single word is written.↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
<h4>[problem:1722C]</h4>↵
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 ↵
<br/>↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
```python↵
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()↵
```↵
</spoiler>↵
↵
[problem:1092B]↵
↵
<spoiler summary="Hint">↵
First Sort the list and try to pair adjacent numbers↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
<h4>[problem:1722C092B]</h4>↵
↵
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↵
<br/>↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
```python↵
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)↵
```↵
</spoiler>↵
↵
[problem:839A]↵
↵
<spoiler summary="Hint">↵
Start at day 1 and simulate the process until the $n^{th}$ day↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
<h4>[problem:839A]</h4>↵
↵
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)$↵
<br/>↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
```python↵
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)↵
```↵
</spoiler>↵
↵
[problem:1015C]↵
↵
<spoiler summary="Hint">↵
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}$↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
<h4>[problem:1015C]</h4>↵
↵
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 <b>sum</b> ,now if we compress the ${j^{th}}$ song how do the <b>sum</b> 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.↵
<br/>↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
```python↵
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)↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
↵
<h4>[problem:263A]</h4>↵
↵
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.↵
<br/>↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
```python↵
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↵
```↵
</spoiler>↵
↵
[problem:1722C]↵
↵
<spoiler summary="Hint">↵
What kind of Data Structure should you use in-order to know how many times that a single word is written.↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
<h4>[problem:1722C]</h4>↵
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 ↵
<br/>↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
```python↵
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()↵
```↵
</spoiler>↵
↵
[problem:1092B]↵
↵
<spoiler summary="Hint">↵
First Sort the list and try to pair adjacent numbers↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
<h4>[problem:1
↵
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↵
<br/>↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
```python↵
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)↵
```↵
</spoiler>↵
↵
[problem:839A]↵
↵
<spoiler summary="Hint">↵
Start at day 1 and simulate the process until the $n^{th}$ day↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
<h4>[problem:839A]</h4>↵
↵
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)$↵
<br/>↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
```python↵
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)↵
```↵
</spoiler>↵
↵
[problem:1015C]↵
↵
<spoiler summary="Hint">↵
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}$↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
<h4>[problem:1015C]</h4>↵
↵
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 <b>sum</b> ,now if we compress the ${j^{th}}$ song how do the <b>sum</b> 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.↵
<br/>↵
<br/>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
```python↵
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)↵
```↵
</spoiler>↵
↵
