[Here](https://codeforces.me/gym/528792) is the link to the contest. All problems are from Codeforces' problemset.↵
↵
↵
#### [A. Spris](https://codeforces.me/gym/528792/problem/A)↵
↵
<spoiler summary="Solution">↵
At first let's calculate how many portions of stewed fruit (in one portion — $1$ lemon, $2$ apples and $4$ pears) we can cook. This number equals to $min(a, b\ div\ 2, c\ div\ 4)$, where $x\ div\ y$ is integer part of $x / y$. After that we need to multiply this number of $7$, because there is $7$ fruits in $1$ portion, and print the result.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
a = int(input())↵
b = int(input())↵
c = int(input())↵
↵
spris = min(a, b//2, c//4)↵
print(spris*7)↵
↵
```↵
</spoiler>↵
↵
↵
#### [B. BANless](https://codeforces.me/gym/528792/problem/B)↵
↵
<spoiler summary="Solution">↵
<p>↵
We can easily remove any $BAN$ sequences in the given input string by bringing all $Ns$ to the beginning and all $Bs$ to the end of the input string. To minimize the number of operations needed, we can consider at each step two $BAN$ sequences: the leftmost one and the rightmost one. Then we can swap the letter $B$ of the leftmost one with the letter $N$ of the rightmost one.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
↵
def main():↵
for _ in range(int(input())):↵
n = int(input())↵
k = []↵
↵
start, end = 1, 3 * n ↵
while start < end:↵
k.append([start, end])↵
start += 3↵
end -= 3 ↵
↵
print(len(k))↵
for each in k:↵
print(*each) ↵
↵
if __name__ == "__main__":↵
main()↵
↵
```↵
</spoiler>↵
↵
↵
#### [C. Coffee Dilemma](https://codeforces.me/gym/528792/problem/C)↵
↵
<spoiler summary="Solution">↵
We process the potions from left to right. At the same time, we maintain the list of potions we have taken so far. When processing potion $i$, if we can take $i$ without dying, then we take it. Otherwise, if the most negative potion we've taken is more negative than potion $i$, then we can swap out potion $i$ for that potion. To find the most negative potion we've taken, we can maintain the values of all potions in a heap. This runs in $O(n \log n)$.↵
↵
To prove that this works, let's consider the best solution where we take exactly $k$ potions (best as in max total health). The solution involves taking the $k$ largest values in our heap. Then when considering a new potion, we should see whether swapping out the new potion for the $k$ th largest potion will improve the answer.↵
↵
Since the heap is strictly decreasing, there will be a cutoff $K$, where for $k$ at most $K$, the answer is not affected, and for larger than $K$, we swap out the $k$th largest potion. It turns out this process is equivalent to inserting the new potion's value into the heap. For those positions at most $K$, they are not affected. For the positions larger than $K$, the elements get pushed back one space, meaning that the smallest element is undrinked.↵
↵
This can also be seen as an efficient way to transition from one layer of the $dp$ table to the next.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import heapq↵
↵
n = int(input())↵
a = list(map(int, input().split()))↵
↵
h = []↵
total_sum = 0↵
↵
for potion in a:↵
total_sum += potion↵
heapq.heappush(h, potion)↵
while total_sum < 0:↵
total_sum -= heapq.heappop(h)↵
↵
print(len(h))↵
↵
↵
```↵
</spoiler>↵
↵
↵
#### [D. The Equalizer XOR](https://codeforces.me/gym/528792/problem/D)↵
↵
<spoiler summary="Hints">↵
↵
<spoiler summary="Hint 1">↵
<p>↵
A number that is inserted as a result of merging is a subarray xor.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
<p>↵
The resulting array of subarray xor's is exclusive (no overlaps) and exhaustive (covers all original numbers). ↵
</p>↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
<p>↵
So let's try to understand what the final array looks like in terms of the initial array. The best way to see this is to look at the process backwards. Basically, start with the final array, and keep replacing an element with the $2$↵
elements that xor-ed down to it, until you get the initial array. You'll see that the first element turns into a prefix, the second element turns into a subarray that follows this prefix, and so on. Hence, the whole process of moving from the initial to the final array is like we divide the array into pieces, and then replace each piece with its xor, and we want these xors to be equal. ↵
</p>↵
<p>↵
A nice observation is: we need at most $3$↵
pieces. That's because if we have $4$↵
or more pieces, we can take $3$↵
pieces and merge them into one. Its xor will be the same, but the total piece count will decrease by $2$↵
. ↵
</p>↵
<p>↵
Now, checking if you can divide it into $2$↵
or $3$↵
pieces is a simple task that can be done by bruteforce. You can iterate over the positions you'll split the array, and then check the xors are equal using a prefix-xor array.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
a = list(map(int, input().split()))↵
↵
pref_xor = [a[0]]↵
for i in range(1, n):↵
pref_xor.append(pref_xor[-1] ^ a[i])↵
↵
yes = False↵
↵
# if we can create two subarrays of equal xor,↵
# the total xor should be zero.↵
if pref_xor[-1] == 0:↵
yes = True↵
↵
# check for three subarrays↵
for i in range(n):↵
if yes:↵
break↵
↵
first_subarray = pref_xor[i]↵
for j in range(i + 1, n):↵
second_subarray = pref_xor[j] ^ pref_xor[i]↵
third_subarray = pref_xor[-1] ^ pref_xor[j]↵
↵
if first_subarray == second_subarray == third_subarray:↵
yes = True↵
break↵
↵
print('YES' if yes else 'NO')↵
↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Optimal Code">↵
```python↵
↵
import sys↵
from collections import defaultdict↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
a = list(map(int, input().split()))↵
↵
pref_xor = [a[0]]↵
for i in range(1, n):↵
pref_xor.append(pref_xor[-1] ^ a[i])↵
↵
↵
suf_xor = 0↵
last_idx = defaultdict(lambda : -1) ↵
↵
for i in range(n - 1, -1, -1):↵
suf_xor ^= a[i]↵
last_idx[suf_xor] = max(last_idx[suf_xor], i)↵
↵
yes = False↵
↵
for i in range(n):↵
# two subarrays↵
first = pref_xor[i]↵
second = pref_xor[-1] ^ first↵
if first == second:↵
yes = True↵
break↵
↵
# three subarrys↵
# the prefix xor should occur as a sufix after this index ↵
if pref_xor[-1] ^ first == 0 and last_idx[first] > i:↵
yes = True↵
break↵
↵
print('YES' if yes else 'NO')↵
↵
↵
```↵
</spoiler>↵
↵
↵
#### [E. Voyage Quest](https://codeforces.me/gym/528792/problem/E)↵
↵
<spoiler summary = "Hint">↵
Note, that if we can reach the destination in $x$ days, so we can reach it in $y≥x$ days.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
Note, that if we can reach the destination in $x$ days, so we can reach it in $y≥x$ days, since we can stay in the destination point by moving to the opposite to the wind direction. So, we can $binary search$ the answer.↵
↵
To check the possibility to reach the destination point $(x_2,y_2)$ in $k$ days we should at first look at the position $(x_3,y_3)$ the wind moves ship to. Now we can calculate where we can go: since each day we can move in one of four directions or not move at all, we can reach any point $(x,y)$ with Manhattan distance $|x−x_3|+|y−y_3|≤k$. So we need to check that↵
$|x_2−x_3|+|y_2−y_3|≤k$.↵
↵
To calculate $(x_3,y_3)$ we can note, that there were $\left\lfloor \frac{k}{n} \right\rfloor$ full cycles and $k \bmod n$↵
extra days. So it can be calculated using running sum.↵
↵
Finally, about borders of binary search: to reach the destination point we need to move closer at least by one (it terms of Manhattan distance) from the full cycle of the wind. So, if answer exists then it doesn't exceed↵
$(|x_1−x_2|+|y_1−y_2|)⋅n≤2⋅10^{14}$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
↵
x_1, y_1 = map(int, sys.stdin.readline().strip().split())↵
x_2, y_2 = map(int, sys.stdin.readline().strip().split())↵
n = int(sys.stdin.readline().strip())↵
s = sys.stdin.readline().strip()↵
↵
def find(ch):↵
↵
if ch == "U":↵
return [0, 1]↵
↵
if ch == "D":↵
return [0, -1]↵
↵
if ch == "L":↵
return [-1, 0]↵
↵
if ch == "R":↵
return [1, 0]↵
↵
def checker(k):↵
↵
x_3, y_3 = x_1, y_1↵
full_cycles = k // n↵
extra_days = k % n↵
↵
for ch in s:↵
x_3 += find(ch)[0] * full_cycles↵
y_3 += find(ch)[1] * full_cycles↵
↵
for i in range(extra_days):↵
x_3 += find(s[i])[0]↵
y_3 += find(s[i])[1]↵
↵
return abs(x_2 - x_3) + abs(y_2 - y_3) <= k↵
↵
low = 1↵
high = 10**15↵
↵
while low <= high:↵
↵
mid = (low + high) // 2↵
↵
if checker(mid):↵
high = mid - 1↵
else:↵
low = mid + 1↵
↵
if low > 10**15:↵
print(-1)↵
else:↵
print(low)↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [A. Spris](https://codeforces.me/gym/528792/problem/A)↵
↵
<spoiler summary="Solution">↵
At first let's calculate how many portions of stewed fruit (in one portion — $1$ lemon, $2$ apples and $4$ pears) we can cook. This number equals to $min(a, b\ div\ 2, c\ div\ 4)$, where $x\ div\ y$ is integer part of $x / y$. After that we need to multiply this number of $7$, because there is $7$ fruits in $1$ portion, and print the result.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
a = int(input())↵
b = int(input())↵
c = int(input())↵
↵
spris = min(a, b//2, c//4)↵
print(spris*7)↵
↵
```↵
</spoiler>↵
↵
↵
#### [B. BANless](https://codeforces.me/gym/528792/problem/B)↵
↵
<spoiler summary="Solution">↵
<p>↵
We can easily remove any $BAN$ sequences in the given input string by bringing all $Ns$ to the beginning and all $Bs$ to the end of the input string. To minimize the number of operations needed, we can consider at each step two $BAN$ sequences: the leftmost one and the rightmost one. Then we can swap the letter $B$ of the leftmost one with the letter $N$ of the rightmost one.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
↵
def main():↵
for _ in range(int(input())):↵
n = int(input())↵
k = []↵
↵
start, end = 1, 3 * n ↵
while start < end:↵
k.append([start, end])↵
start += 3↵
end -= 3 ↵
↵
print(len(k))↵
for each in k:↵
print(*each) ↵
↵
if __name__ == "__main__":↵
main()↵
↵
```↵
</spoiler>↵
↵
↵
#### [C. Coffee Dilemma](https://codeforces.me/gym/528792/problem/C)↵
↵
<spoiler summary="Solution">↵
We process the potions from left to right. At the same time, we maintain the list of potions we have taken so far. When processing potion $i$, if we can take $i$ without dying, then we take it. Otherwise, if the most negative potion we've taken is more negative than potion $i$, then we can swap out potion $i$ for that potion. To find the most negative potion we've taken, we can maintain the values of all potions in a heap. This runs in $O(n \log n)$.↵
↵
To prove that this works, let's consider the best solution where we take exactly $k$ potions (best as in max total health). The solution involves taking the $k$ largest values in our heap. Then when considering a new potion, we should see whether swapping out the new potion for the $k$ th largest potion will improve the answer.↵
↵
Since the heap is strictly decreasing, there will be a cutoff $K$, where for $k$ at most $K$, the answer is not affected, and for larger than $K$, we swap out the $k$th largest potion. It turns out this process is equivalent to inserting the new potion's value into the heap. For those positions at most $K$, they are not affected. For the positions larger than $K$, the elements get pushed back one space, meaning that the smallest element is undrinked.↵
↵
This can also be seen as an efficient way to transition from one layer of the $dp$ table to the next.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import heapq↵
↵
n = int(input())↵
a = list(map(int, input().split()))↵
↵
h = []↵
total_sum = 0↵
↵
for potion in a:↵
total_sum += potion↵
heapq.heappush(h, potion)↵
while total_sum < 0:↵
total_sum -= heapq.heappop(h)↵
↵
print(len(h))↵
↵
↵
```↵
</spoiler>↵
↵
↵
#### [D. The Equalizer XOR](https://codeforces.me/gym/528792/problem/D)↵
↵
<spoiler summary="Hints">↵
↵
<spoiler summary="Hint 1">↵
<p>↵
A number that is inserted as a result of merging is a subarray xor.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
<p>↵
The resulting array of subarray xor's is exclusive (no overlaps) and exhaustive (covers all original numbers). ↵
</p>↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
<p>↵
So let's try to understand what the final array looks like in terms of the initial array. The best way to see this is to look at the process backwards. Basically, start with the final array, and keep replacing an element with the $2$↵
elements that xor-ed down to it, until you get the initial array. You'll see that the first element turns into a prefix, the second element turns into a subarray that follows this prefix, and so on. Hence, the whole process of moving from the initial to the final array is like we divide the array into pieces, and then replace each piece with its xor, and we want these xors to be equal. ↵
</p>↵
<p>↵
A nice observation is: we need at most $3$↵
pieces. That's because if we have $4$↵
or more pieces, we can take $3$↵
pieces and merge them into one. Its xor will be the same, but the total piece count will decrease by $2$↵
. ↵
</p>↵
<p>↵
Now, checking if you can divide it into $2$↵
or $3$↵
pieces is a simple task that can be done by bruteforce. You can iterate over the positions you'll split the array, and then check the xors are equal using a prefix-xor array.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
a = list(map(int, input().split()))↵
↵
pref_xor = [a[0]]↵
for i in range(1, n):↵
pref_xor.append(pref_xor[-1] ^ a[i])↵
↵
yes = False↵
↵
# if we can create two subarrays of equal xor,↵
# the total xor should be zero.↵
if pref_xor[-1] == 0:↵
yes = True↵
↵
# check for three subarrays↵
for i in range(n):↵
if yes:↵
break↵
↵
first_subarray = pref_xor[i]↵
for j in range(i + 1, n):↵
second_subarray = pref_xor[j] ^ pref_xor[i]↵
third_subarray = pref_xor[-1] ^ pref_xor[j]↵
↵
if first_subarray == second_subarray == third_subarray:↵
yes = True↵
break↵
↵
print('YES' if yes else 'NO')↵
↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Optimal Code">↵
```python↵
↵
import sys↵
from collections import defaultdict↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
a = list(map(int, input().split()))↵
↵
pref_xor = [a[0]]↵
for i in range(1, n):↵
pref_xor.append(pref_xor[-1] ^ a[i])↵
↵
↵
suf_xor = 0↵
last_idx = defaultdict(lambda : -1) ↵
↵
for i in range(n - 1, -1, -1):↵
suf_xor ^= a[i]↵
last_idx[suf_xor] = max(last_idx[suf_xor], i)↵
↵
yes = False↵
↵
for i in range(n):↵
# two subarrays↵
first = pref_xor[i]↵
second = pref_xor[-1] ^ first↵
if first == second:↵
yes = True↵
break↵
↵
# three subarrys↵
# the prefix xor should occur as a sufix after this index ↵
if pref_xor[-1] ^ first == 0 and last_idx[first] > i:↵
yes = True↵
break↵
↵
print('YES' if yes else 'NO')↵
↵
↵
```↵
</spoiler>↵
↵
↵
#### [E. Voyage Quest](https://codeforces.me/gym/528792/problem/E)↵
↵
<spoiler summary = "Hint">↵
Note, that if we can reach the destination in $x$ days, so we can reach it in $y≥x$ days.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
Note, that if we can reach the destination in $x$ days, so we can reach it in $y≥x$ days, since we can stay in the destination point by moving to the opposite to the wind direction. So, we can $binary search$ the answer.↵
↵
To check the possibility to reach the destination point $(x_2,y_2)$ in $k$ days we should at first look at the position $(x_3,y_3)$ the wind moves ship to. Now we can calculate where we can go: since each day we can move in one of four directions or not move at all, we can reach any point $(x,y)$ with Manhattan distance $|x−x_3|+|y−y_3|≤k$. So we need to check that↵
$|x_2−x_3|+|y_2−y_3|≤k$.↵
↵
To calculate $(x_3,y_3)$ we can note, that there were $\left\lfloor \frac{k}{n} \right\rfloor$ full cycles and $k \bmod n$↵
extra days. So it can be calculated using running sum.↵
↵
Finally, about borders of binary search: to reach the destination point we need to move closer at least by one (it terms of Manhattan distance) from the full cycle of the wind. So, if answer exists then it doesn't exceed↵
$(|x_1−x_2|+|y_1−y_2|)⋅n≤2⋅10^{14}$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
↵
x_1, y_1 = map(int, sys.stdin.readline().strip().split())↵
x_2, y_2 = map(int, sys.stdin.readline().strip().split())↵
n = int(sys.stdin.readline().strip())↵
s = sys.stdin.readline().strip()↵
↵
def find(ch):↵
↵
if ch == "U":↵
return [0, 1]↵
↵
if ch == "D":↵
return [0, -1]↵
↵
if ch == "L":↵
return [-1, 0]↵
↵
if ch == "R":↵
return [1, 0]↵
↵
def checker(k):↵
↵
x_3, y_3 = x_1, y_1↵
full_cycles = k // n↵
extra_days = k % n↵
↵
for ch in s:↵
x_3 += find(ch)[0] * full_cycles↵
y_3 += find(ch)[1] * full_cycles↵
↵
for i in range(extra_days):↵
x_3 += find(s[i])[0]↵
y_3 += find(s[i])[1]↵
↵
return abs(x_2 - x_3) + abs(y_2 - y_3) <= k↵
↵
low = 1↵
high = 10**15↵
↵
while low <= high:↵
↵
mid = (low + high) // 2↵
↵
if checker(mid):↵
high = mid - 1↵
else:↵
low = mid + 1↵
↵
if low > 10**15:↵
print(-1)↵
else:↵
print(low)↵
↵
```↵
</spoiler>↵
↵
