Here is the link to the contest. All problems are from Codeforces' problemset.

#### A. Spris

**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.

**Code**

```
a = int(input())
b = int(input())
c = int(input())
spris = min(a, b//2, c//4)
print(spris*7)
```

#### B. BANless

**Solution**

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.

**Code**

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()

#### C. Coffee Dilemma

**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.

**Code**

```
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))
```

#### D. The Equalizer XOR

**Hints**

**Hint 1**

A number that is inserted as a result of merging is a subarray xor.

**Hint 2**

The resulting array of subarray xor's is exclusive (no overlaps) and exhaustive (covers all original numbers).

**Solution**

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.

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$$$ .

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.

**Code**

```
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')
```

**Optimal Code**

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')

#### E. Voyage Quest

**Hint**

Note, that if we can reach the destination in $$$x$$$ days, so we can reach it in $$$y≥x$$$ days.

**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}$$$.

**Code**

```
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)
```

Auto comment: topic has been updated by A2SV_Group5 (previous revision, new revision, compare).