[Here](https://mirror.codeforces.com/contestInvitation/36eb2e48dc8f6c03c97ce6219e6954a71aceaf7d) is the link to the contest. The problems are from Codeforces' problemset.↵
↵
#### [A. Your Hackathon Project — Chat Feature](https://mirror.codeforces.com/gym/534160/problem/A)↵
↵
<spoiler summary="Solution">↵
↵
You should count the number of parentheses at the end of the string, suppose there are $x$ such parentheses. Then if $x>n/2$, the message is bad. Note that you should divide n by 2 without rounding. Or you can compare $2\cdot x$ and $n$ instead. If $2 \cdot x>n$, the message is bad.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
for _ in range(int(input())):↵
n = int(input())↵
word = input()↵
ind = n - 1↵
↵
while ind >= 0 and word[ind] == ')':↵
ind -= 1↵
↵
print("NO" if ind >= (n - 1)//2 else "YES")↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [B. Your Hackathon Project — a Game](https://mirror.codeforces.com/gym/534160/problem/B)↵
↵
<spoiler summary = "Solution">↵
So, the first idea that is coming into mind is prefix sums. Let's define two values $l_i=max(0,a_i−a_i+1)$ and $r_i=max(0,a_i+1−a_i)$. The value $l_i$ means the amount of fall damage when we are going to the right from the column $i$ to the column $i$+$1$, and $r_i$ means the amount of fall damage when we are going to the left from the column $i$+$1$ to the column $i$. Then let's build prefix sums on these two arrays. Now let $p_{l_i}$ be the sum of all li on a prefix [0;i) (i. e. $p_{l_0}$=0), and $p_{r_i}$ be the sum of all $r_i$ on a $prefix [0;i)$. Then if $s<t$ in a query, the answer is $pl_{t−1}$ − ↵
$pl_{s−1}$, otherwise (if $s>t$) the answer is $pr_{s−1}$ − $pr_{t−1}$.↵
↵
Time complexity: $O(n)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n, m = map(int, input().split())↵
a = list(map(int, input().split()))↵
l = [0] + [max(0, a[i] - a[i + 1]) for i in range(n - 1)]↵
r = [0] + [max(0, a[i] - a[i - 1]) for i in range(1, n)]↵
for i in range(n - 1):↵
l[i + 1] += l[i]↵
r[i + 1] += r[i]↵
for _ in range(m):↵
s, t = map(int, input().split())↵
if s < t:↵
print(l[t - 1] - l[s - 1])↵
else:↵
print(r[s - 1] - r[t - 1])↵
```↵
</spoiler>↵
↵
↵
#### [C. Removal Hack](https://mirror.codeforces.com/gym/534160/problem/C)↵
↵
<spoiler summary="Solution">↵
From the condition about the fact that each vertex equally respects all its ancestors, we can understand that each vertex is either always a candidate for deletion or it can never be deleted. That is because when we delete some vertex all new vertices which become sons of it's parent are also disrespecting it.↵
↵
Now we can iterate over all vertices and if it respects it's parent, we will remember that it's parent can not be deleted. And so we will get the answer.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
from collections import defaultdict↵
from sys import stdin↵
↵
↵
def input(): return stdin.readline().strip()↵
↵
N = int(input())↵
↵
child = defaultdict(list)↵
respect = [0]*N↵
↵
root = 0↵
↵
for ch in range(N):↵
p, c = map(int, input().split())↵
p -= 1↵
respect[ch] = c↵
if p == -2:↵
root = ch↵
continue↵
child[p].append(ch)↵
↵
stack = [root]↵
↵
ans = []↵
↵
while stack:↵
v = stack.pop()↵
ok = respect[v]↵
for ch in child[v]:↵
stack.append(ch)↵
if respect[ch] == 0:↵
ok = False↵
if ok:↵
ans.append(v + 1)↵
if not ans:↵
print(-1)↵
else:↵
print(*sorted(ans))↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [D. Counting Hack](https://mirror.codeforces.com/gym/534160/problem/D)↵
↵
↵
<spoiler summary="Hint">↵
<p>↵
A unique subarray is created only if its leftmost element is the first occurrence in the input array and its rightmost element is the last occurrence, regardless of the elements in between.↵
</p>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
<p>↵
Note that a subarray suits us if $al$ is the leftmost occurrence of the number $al$ in the array and $ar$ is the rightmost occurrence of the number $ar$ in the array. Let's create an array$br$ filled with zeros and set $br=1$ if $ar$ is the rightmost occurrence of the number $ar$ in the array (this can be done using sets or dictionaries). Now we need to consider all suitable left boundaries and see how many suitable right boundaries we have on the prefix, by precomputing a prefix sum of the right boundaries.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
for _ in range(int(input())):↵
n = int(input())↵
arr = list(map(int, input().split()))↵
↵
visited = set()↵
right_most = [0] * (n + 1)↵
for i in range(n - 1, -1, -1):↵
if arr[i] not in visited:↵
visited.add(arr[i])↵
right_most[i + 1] = 1↵
visited.add(arr[i])↵
↵
for i in range(1, len(right_most)):↵
right_most[i] += right_most[i - 1]↵
↵
visited.clear()↵
ans = 0↵
for i in range(n):↵
if arr[i] not in visited:↵
ans += right_most[-1] - right_most[i]↵
visited.add(arr[i])↵
↵
print(ans)↵
↵
```↵
</spoiler>↵
↵
↵
#### [E. Segment Hack](https://mirror.codeforces.com/gym/534160/problem/E)↵
↵
<spoiler summary="Hint">↵
<p>↵
We only need two segments to check if the answer is $YES$.↵
</p>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
<p>↵
The claim is that if the answer exists, we can take the segment with the minimum right boundary and the segment with the maximum left boundary (let's denote these boundaries as $r_{1}$ and $l_{2}$). Therefore, if $r_{1}<l_{2}$, it is obvious that this pair of segments is suitable for us. Otherwise, all pairs of segments intersect because they have common points in the range $l_{2}…r_{1}$↵
.↵
</p>↵
↵
<p>↵
To keep track of the maximum left and minimum right boundaries, we can use max heap and min heap respectively. Since we might lose track of some segments, we can keep the count of a segment using its boundaries.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
from collections import defaultdict↵
from heapq import heappush, heappop↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
q = int(input())↵
↵
# to keep track of deleted and duplicate segments↵
sgt_count = defaultdict(int)↵
mxheap = [] # to store the largest l value↵
mnheap = [] # to store the smallest r value↵
↵
for _ in range(q):↵
operation, l, r = input().split()↵
l, r = int(l), int(r)↵
↵
if operation == '+':↵
heappush(mxheap, (-l, r))↵
heappush(mnheap, (r, l))↵
sgt_count[(l, r)] += 1↵
else:↵
sgt_count[(l, r)] -= 1↵
↵
# remove segments from max heap if they no longer exists on sgt_count↵
while mxheap:↵
neg_left, right = mxheap[0]↵
if sgt_count[(-neg_left, right)]:↵
break↵
↵
else:↵
heappop(mxheap)↵
↵
# remove segments from min heap if they no longer exists on sgt_count↵
while mnheap:↵
right, left = mnheap[0]↵
if sgt_count[(left, right)]:↵
break↵
↵
else:↵
heappop(mnheap)↵
↵
# compare the smallest r value with the largest l value↵
if mxheap and mnheap and -mxheap[0][0] > mnheap[0][0]:↵
print('YES')↵
else:↵
print('NO')↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [A. Your Hackathon Project — Chat Feature](https://mirror.codeforces.com/gym/534160/problem/A)↵
↵
<spoiler summary="Solution">↵
↵
You should count the number of parentheses at the end of the string, suppose there are $x$ such parentheses. Then if $x>n/2$, the message is bad. Note that you should divide n by 2 without rounding. Or you can compare $2\cdot x$ and $n$ instead. If $2 \cdot x>n$, the message is bad.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
for _ in range(int(input())):↵
n = int(input())↵
word = input()↵
ind = n - 1↵
↵
while ind >= 0 and word[ind] == ')':↵
ind -= 1↵
↵
print("NO" if ind >= (n - 1)//2 else "YES")↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [B. Your Hackathon Project — a Game](https://mirror.codeforces.com/gym/534160/problem/B)↵
↵
<spoiler summary = "Solution">↵
So, the first idea that is coming into mind is prefix sums. Let's define two values $l_i=max(0,a_i−a_i+1)$ and $r_i=max(0,a_i+1−a_i)$. The value $l_i$ means the amount of fall damage when we are going to the right from the column $i$ to the column $i$+$1$, and $r_i$ means the amount of fall damage when we are going to the left from the column $i$+$1$ to the column $i$. Then let's build prefix sums on these two arrays. Now let $p_{l_i}$ be the sum of all li on a prefix [0;i) (i. e. $p_{l_0}$=0), and $p_{r_i}$ be the sum of all $r_i$ on a $prefix [0;i)$. Then if $s<t$ in a query, the answer is $pl_{t−1}$ − ↵
$pl_{s−1}$, otherwise (if $s>t$) the answer is $pr_{s−1}$ − $pr_{t−1}$.↵
↵
Time complexity: $O(n)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n, m = map(int, input().split())↵
a = list(map(int, input().split()))↵
l = [0] + [max(0, a[i] - a[i + 1]) for i in range(n - 1)]↵
r = [0] + [max(0, a[i] - a[i - 1]) for i in range(1, n)]↵
for i in range(n - 1):↵
l[i + 1] += l[i]↵
r[i + 1] += r[i]↵
for _ in range(m):↵
s, t = map(int, input().split())↵
if s < t:↵
print(l[t - 1] - l[s - 1])↵
else:↵
print(r[s - 1] - r[t - 1])↵
```↵
</spoiler>↵
↵
↵
#### [C. Removal Hack](https://mirror.codeforces.com/gym/534160/problem/C)↵
↵
<spoiler summary="Solution">↵
From the condition about the fact that each vertex equally respects all its ancestors, we can understand that each vertex is either always a candidate for deletion or it can never be deleted. That is because when we delete some vertex all new vertices which become sons of it's parent are also disrespecting it.↵
↵
Now we can iterate over all vertices and if it respects it's parent, we will remember that it's parent can not be deleted. And so we will get the answer.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
from collections import defaultdict↵
from sys import stdin↵
↵
↵
def input(): return stdin.readline().strip()↵
↵
N = int(input())↵
↵
child = defaultdict(list)↵
respect = [0]*N↵
↵
root = 0↵
↵
for ch in range(N):↵
p, c = map(int, input().split())↵
p -= 1↵
respect[ch] = c↵
if p == -2:↵
root = ch↵
continue↵
child[p].append(ch)↵
↵
stack = [root]↵
↵
ans = []↵
↵
while stack:↵
v = stack.pop()↵
ok = respect[v]↵
for ch in child[v]:↵
stack.append(ch)↵
if respect[ch] == 0:↵
ok = False↵
if ok:↵
ans.append(v + 1)↵
if not ans:↵
print(-1)↵
else:↵
print(*sorted(ans))↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [D. Counting Hack](https://mirror.codeforces.com/gym/534160/problem/D)↵
↵
↵
<spoiler summary="Hint">↵
<p>↵
A unique subarray is created only if its leftmost element is the first occurrence in the input array and its rightmost element is the last occurrence, regardless of the elements in between.↵
</p>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
<p>↵
Note that a subarray suits us if $al$ is the leftmost occurrence of the number $al$ in the array and $ar$ is the rightmost occurrence of the number $ar$ in the array. Let's create an array$br$ filled with zeros and set $br=1$ if $ar$ is the rightmost occurrence of the number $ar$ in the array (this can be done using sets or dictionaries). Now we need to consider all suitable left boundaries and see how many suitable right boundaries we have on the prefix, by precomputing a prefix sum of the right boundaries.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
for _ in range(int(input())):↵
n = int(input())↵
arr = list(map(int, input().split()))↵
↵
visited = set()↵
right_most = [0] * (n + 1)↵
for i in range(n - 1, -1, -1):↵
if arr[i] not in visited:↵
visited.add(arr[i])↵
right_most[i + 1] = 1↵
visited.add(arr[i])↵
↵
for i in range(1, len(right_most)):↵
right_most[i] += right_most[i - 1]↵
↵
visited.clear()↵
ans = 0↵
for i in range(n):↵
if arr[i] not in visited:↵
ans += right_most[-1] - right_most[i]↵
visited.add(arr[i])↵
↵
print(ans)↵
↵
```↵
</spoiler>↵
↵
↵
#### [E. Segment Hack](https://mirror.codeforces.com/gym/534160/problem/E)↵
↵
<spoiler summary="Hint">↵
<p>↵
We only need two segments to check if the answer is $YES$.↵
</p>↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
<p>↵
The claim is that if the answer exists, we can take the segment with the minimum right boundary and the segment with the maximum left boundary (let's denote these boundaries as $r_{1}$ and $l_{2}$). Therefore, if $r_{1}<l_{2}$, it is obvious that this pair of segments is suitable for us. Otherwise, all pairs of segments intersect because they have common points in the range $l_{2}…r_{1}$↵
.↵
</p>↵
↵
<p>↵
To keep track of the maximum left and minimum right boundaries, we can use max heap and min heap respectively. Since we might lose track of some segments, we can keep the count of a segment using its boundaries.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
from collections import defaultdict↵
from heapq import heappush, heappop↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
q = int(input())↵
↵
# to keep track of deleted and duplicate segments↵
sgt_count = defaultdict(int)↵
mxheap = [] # to store the largest l value↵
mnheap = [] # to store the smallest r value↵
↵
for _ in range(q):↵
operation, l, r = input().split()↵
l, r = int(l), int(r)↵
↵
if operation == '+':↵
heappush(mxheap, (-l, r))↵
heappush(mnheap, (r, l))↵
sgt_count[(l, r)] += 1↵
else:↵
sgt_count[(l, r)] -= 1↵
↵
# remove segments from max heap if they no longer exists on sgt_count↵
while mxheap:↵
neg_left, right = mxheap[0]↵
if sgt_count[(-neg_left, right)]:↵
break↵
↵
else:↵
heappop(mxheap)↵
↵
# remove segments from min heap if they no longer exists on sgt_count↵
while mnheap:↵
right, left = mnheap[0]↵
if sgt_count[(left, right)]:↵
break↵
↵
else:↵
heappop(mnheap)↵
↵
# compare the smallest r value with the largest l value↵
if mxheap and mnheap and -mxheap[0][0] > mnheap[0][0]:↵
print('YES')↵
else:↵
print('NO')↵
↵
↵
```↵
</spoiler>↵
↵
↵
