[Here](https://codeforces.net/contestInvitation/255862732d6b680f4d8bba55cf0c744a1b4226f1) is the link to the contest. All problems are from Codeforces' problemset.↵
↵
↵
#### [A. Chocolate Bar](https://codeforces.net/gym/557458/problem/A)↵
↵
<spoiler summary="Solution">↵
<p>↵
To solve this problem, let's use the following greedy algorithm.↵
</p>↵
<p>↵
Let's sort the prices of chocolate bars in increasing order, after which we will go from left to right and take chocolates that have a price not less than $l$, but not more than $r$ until we run out of money.↵
</p>↵
<p>↵
The number of chocolate bars that we took will be the answer to the problem.↵
</p>↵
<p>↵
Time complexity: $O(nlogn)$.↵
</p>↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
from collections import Counter↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
t = int(input())↵
for _ in range(t):↵
n, l, r, k = map(int, input().split())↵
a = list(map(int, input().split()))↵
a.sort()↵
↵
ans = 0↵
cur_sum = 0↵
↵
for num in a:↵
if l <= num <= r and cur_sum + num <= k:↵
cur_sum += num↵
ans += 1↵
↵
print(ans)↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [B. Secret Code](https://codeforces.net/gym/557458/problem/B)↵
↵
<spoiler summary="Solution">↵
To decode the encoded string, we can observe the following pattern:↵
If the length of the encoded string is odd:↵
The decoded string is formed by first taking and reversing the sequence of characters at odd indices (1st, 3rd, 5th, etc.) from the encoded string, followed by the sequence of characters at even indices (0th, 2nd, 4th, 6th, etc.). The entire sequence is then the final decoded string.↵
If the length of the encoded string is even:↵
The decoded string is formed by first taking and reversing the sequence characters at even indices (0th, 2nd, 4th, 6th, etc.), concatenated with the sequence characters at odd indices (1st, 3rd, 5th, etc.). The entire sequence is then the final decoded string.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
n = int(input())↵
string = input()↵
if n % 2 == 0:↵
part1 = [string[i] for i in range(n) if i % 2 == 0][::-1]↵
part2 = [string[i] for i in range(n) if i % 2]↵
print(''.join(part1 + part2))↵
else:↵
part1 = [string[i] for i in range(n) if i % 2][::-1]↵
part2 = [string[i] for i in range(n) if i % 2 == 0]↵
print(''.join(part1 + part2)) ↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
#### [C. Delta T](https://codeforces.net/gym/557458/problem/C)↵
↵
<spoiler summary = "Solution">↵
First let's consider the cases when the answer exists:↵
↵
If $a=b$, then the thermostat is already set up and the answer is $0$.↵
else if $|a−b|≥x$, then it is enough to reconfigure the thermostat in $1$ operation.↵
else if exist such temperature $c$, that $|a−c|≥x$ and $|b−c|≥x$, then you can configure the thermostat in 2 operations. If such $c$ exists between $l$ and $r$, we can chose one of bounds: $a→l→b$ or $a→r→b$.↵
we need to make $3$ operations if times if we cannot reconfigure through one of the boundaries as above, but we can through both: $a→l→r→b$ or $a→r→l→b$ ↵
↵
If we can't get the temperature b in one of these ways, the answer is $−1$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
def solve():↵
l, r, x = map(int, input().split())↵
a, b = map(int, input().split())↵
if a == b:↵
return 0↵
if abs(a - b) >= x:↵
return 1↵
if r - max(a, b) >= x or min(a, b) - l >= x:↵
return 2↵
if r - b >= x and a - l >= x or r - a >= x and b - l >= x:↵
return 3↵
return -1↵
↵
↵
t = int(input())↵
for _ in range(t):↵
print(solve())↵
```↵
</spoiler>↵
↵
↵
↵
↵
#### [D. Hackathon Games](https://codeforces.net/gym/557458/problem/D)↵
↵
<spoiler summary="Solution">↵
Suppose we are trying to find out the minimum time to get the hands from vertices 1 and k to the same vertex. If both hands end up on some vertex $v$, then the time required is $d(1,v)+d(k,v)$, with $d(x,y)$ being the minimum distance to go from vertex $x$ to $y$. Suppose $d′(x,y)$ is the minimum distance to go from vertex $x$ to $y$ in the reversed graph (i.e. all edges' directions are reversed). Then $d(1,v)+d(k,v)=d(1,v)+d′(v,k)$.↵
↵
The minimum time if both hands are initially on vertices $1$↵
and $k$ is the minimum value of $d(1,v)+d′(v,k)$ for all vertices $v$. This is the same as the minimum distance to go from vertex $1$ to $k$where in the middle of our path, we can reverse the graph at most once.↵
↵
Therefore we can set up a graph like the following:↵
↵
Each vertex is a pair $(x,b)$, where x is a vertex in the original graph and $b$↵
is a boolean determining whether we have already reversed the graph or not.↵
For each edge $i$↵
in the original graph, there is an edge from $(Ui,0)$ to $(Vi,0)$ and an edge from $(Vi,1)$ to $(Ui,1)$, both with weight $Wi$ . For each vertex $x$↵
in the original graph, there is a edge from $(x,0)$ to $(x,1)$ with weight $0$.↵
↵
After this, we do the Dijkstra algorithm once on the new graph from vertex $(1,0)$↵
. Then, the optimal time if both hands start from vertices $1$ and $k$ in the original graph is equal to $d((1,0),(k,1))$in the new graph.↵
↵
Time complexity: $O(N+MlogM)$↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
↵
from collections import defaultdict↵
from heapq import heapify, heappop, heappush↵
from sys import stdin↵
↵
↵
def input(): return stdin.readline().strip()↵
↵
N, M = map(int, input().split())↵
adj = defaultdict(list)↵
↵
for _ in range(M):↵
u, v, w = map(int, input().split())↵
u -= 1↵
v -= 1↵
adj[u].append((v, w))↵
adj[v + N].append((u + N, w))↵
for i in range(N):↵
adj[i].append((i + N, 0))↵
↵
dist = [float('inf')]*(2*N)↵
visited = [False]*(2*N)↵
dist[0] = 0↵
pq = [(0, 0)]↵
while pq:↵
d, v = heappop(pq)↵
if visited[v]:↵
continue↵
visited[v] = True↵
for ch, w in adj[v]:↵
new_d = d + w↵
if new_d < dist[ch]:↵
dist[ch] = new_d↵
heappush(pq, (new_d, ch))↵
↵
for i in range(N + 1, 2*N):↵
if dist[i] == float('inf'):↵
print("-1", end=" ")↵
else:↵
print(dist[i], end=" ")↵
```↵
</spoiler>↵
↵
↵
↵
↵
#### [E. Safe Roads](https://codeforces.net/gym/557458/problem/E)↵
↵
<spoiler summary = "Solution">↵
In this problem we will find the sought quantity for every vertex and find the maximum value. For this for every vertex $v$ count two values: $cnt1[v]$ and $cnt2[v]$ — number of shortest paths from vertex $v$ to $n$-th and $1$-st vertices respectively. For this you should construct graph of shortest paths and use dynamic programming on the constructed graph (because the new graph will be acyclic). To construct the graph of shortest paths you should leave only useful edges in original graph. It can be done, for example, using breadth-first search launched from vertices $1$ and $n$ respectively.↵
↵
After values $cnt1[v]$ and $cnt2[v]$ are found consider every useful edge $(u, v)$ and add to vertices $u$ and $v$ value $(cnt2[u] * cnt1[v]) / (cnt2[n–1])$, which is the contribution of this edge in the sought quantity for the vertices $u$ and $v$. Note that value $(cnt2[n–1])$ is the number of shortest paths between $1$ and $n$. All said values can be found in time $O(N + M)$. The complexity of solution is $O(N + M)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from collections import deque, defaultdict↵
↵
def solve():↵
n, m = map(int, input().split())↵
g = defaultdict(list)↵
↵
for _ in range(m):↵
u, v = map(int, input().split())↵
g[u].append(v)↵
g[v].append(u)↵
↵
que = deque([1])↵
vis = [-1] * (n + 1)↵
visr = [-1] * (n + 1)↵
ways = [0] * (n + 1)↵
waysr = [0] * (n + 1)↵
↵
vis[1] = 0↵
ways[1] = 1↵
dis = 1↵
↵
while que:↵
cur_s = len(que)↵
for _ in range(cur_s):↵
node = que.popleft()↵
for child in g[node]:↵
if vis[child] == -1:↵
que.append(child)↵
vis[child] = dis↵
ways[child] = ways[node]↵
elif dis == vis[child]:↵
ways[child] += ways[node]↵
dis += 1↵
↵
que.append(n)↵
dis = 1↵
visr[n] = 0↵
waysr[n] = 1↵
↵
while que:↵
cur_s = len(que)↵
for _ in range(cur_s):↵
node = que.popleft()↵
for child in g[node]:↵
if visr[child] == -1:↵
que.append(child)↵
visr[child] = dis↵
waysr[child] = waysr[node]↵
elif dis == visr[child]:↵
waysr[child] += waysr[node]↵
dis += 1↵
↵
ans = 1.0↵
div = vis[n]↵
↵
for i in range(2, n):↵
cur_total = 0↵
for child in g[i]:↵
if vis[i] + visr[child] + 1 == vis[n]:↵
cur_total += ways[i] * waysr[child]↵
↵
ans = max(ans, (cur_total / ways[n]) * 2)↵
↵
print(ans)↵
↵
if __name__ == "__main__":↵
solve()↵
```↵
</spoiler>↵
↵
↵
↵
#### [A. Chocolate Bar](https://codeforces.net/gym/557458/problem/A)↵
↵
<spoiler summary="Solution">↵
<p>↵
To solve this problem, let's use the following greedy algorithm.↵
</p>↵
<p>↵
Let's sort the prices of chocolate bars in increasing order, after which we will go from left to right and take chocolates that have a price not less than $l$, but not more than $r$ until we run out of money.↵
</p>↵
<p>↵
The number of chocolate bars that we took will be the answer to the problem.↵
</p>↵
<p>↵
Time complexity: $O(nlogn)$.↵
</p>↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
from collections import Counter↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
t = int(input())↵
for _ in range(t):↵
n, l, r, k = map(int, input().split())↵
a = list(map(int, input().split()))↵
a.sort()↵
↵
ans = 0↵
cur_sum = 0↵
↵
for num in a:↵
if l <= num <= r and cur_sum + num <= k:↵
cur_sum += num↵
ans += 1↵
↵
print(ans)↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [B. Secret Code](https://codeforces.net/gym/557458/problem/B)↵
↵
<spoiler summary="Solution">↵
To decode the encoded string, we can observe the following pattern:↵
If the length of the encoded string is odd:↵
The decoded string is formed by first taking and reversing the sequence of characters at odd indices (1st, 3rd, 5th, etc.) from the encoded string, followed by the sequence of characters at even indices (0th, 2nd, 4th, 6th, etc.). The entire sequence is then the final decoded string.↵
If the length of the encoded string is even:↵
The decoded string is formed by first taking and reversing the sequence characters at even indices (0th, 2nd, 4th, 6th, etc.), concatenated with the sequence characters at odd indices (1st, 3rd, 5th, etc.). The entire sequence is then the final decoded string.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
n = int(input())↵
string = input()↵
if n % 2 == 0:↵
part1 = [string[i] for i in range(n) if i % 2 == 0][::-1]↵
part2 = [string[i] for i in range(n) if i % 2]↵
print(''.join(part1 + part2))↵
else:↵
part1 = [string[i] for i in range(n) if i % 2][::-1]↵
part2 = [string[i] for i in range(n) if i % 2 == 0]↵
print(''.join(part1 + part2)) ↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
#### [C. Delta T](https://codeforces.net/gym/557458/problem/C)↵
↵
<spoiler summary = "Solution">↵
First let's consider the cases when the answer exists:↵
↵
If $a=b$, then the thermostat is already set up and the answer is $0$.↵
else if $|a−b|≥x$, then it is enough to reconfigure the thermostat in $1$ operation.↵
else if exist such temperature $c$, that $|a−c|≥x$ and $|b−c|≥x$, then you can configure the thermostat in 2 operations. If such $c$ exists between $l$ and $r$, we can chose one of bounds: $a→l→b$ or $a→r→b$.↵
we need to make $3$ operations if times if we cannot reconfigure through one of the boundaries as above, but we can through both: $a→l→r→b$ or $a→r→l→b$ ↵
↵
If we can't get the temperature b in one of these ways, the answer is $−1$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
def solve():↵
l, r, x = map(int, input().split())↵
a, b = map(int, input().split())↵
if a == b:↵
return 0↵
if abs(a - b) >= x:↵
return 1↵
if r - max(a, b) >= x or min(a, b) - l >= x:↵
return 2↵
if r - b >= x and a - l >= x or r - a >= x and b - l >= x:↵
return 3↵
return -1↵
↵
↵
t = int(input())↵
for _ in range(t):↵
print(solve())↵
```↵
</spoiler>↵
↵
↵
↵
↵
#### [D. Hackathon Games](https://codeforces.net/gym/557458/problem/D)↵
↵
<spoiler summary="Solution">↵
Suppose we are trying to find out the minimum time to get the hands from vertices 1 and k to the same vertex. If both hands end up on some vertex $v$, then the time required is $d(1,v)+d(k,v)$, with $d(x,y)$ being the minimum distance to go from vertex $x$ to $y$. Suppose $d′(x,y)$ is the minimum distance to go from vertex $x$ to $y$ in the reversed graph (i.e. all edges' directions are reversed). Then $d(1,v)+d(k,v)=d(1,v)+d′(v,k)$.↵
↵
The minimum time if both hands are initially on vertices $1$↵
and $k$ is the minimum value of $d(1,v)+d′(v,k)$ for all vertices $v$. This is the same as the minimum distance to go from vertex $1$ to $k$where in the middle of our path, we can reverse the graph at most once.↵
↵
Therefore we can set up a graph like the following:↵
↵
Each vertex is a pair $(x,b)$, where x is a vertex in the original graph and $b$↵
is a boolean determining whether we have already reversed the graph or not.↵
For each edge $i$↵
in the original graph, there is an edge from $(Ui,0)$ to $(Vi,0)$ and an edge from $(Vi,1)$ to $(Ui,1)$, both with weight $Wi$ . For each vertex $x$↵
in the original graph, there is a edge from $(x,0)$ to $(x,1)$ with weight $0$.↵
↵
After this, we do the Dijkstra algorithm once on the new graph from vertex $(1,0)$↵
. Then, the optimal time if both hands start from vertices $1$ and $k$ in the original graph is equal to $d((1,0),(k,1))$in the new graph.↵
↵
Time complexity: $O(N+MlogM)$↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
↵
from collections import defaultdict↵
from heapq import heapify, heappop, heappush↵
from sys import stdin↵
↵
↵
def input(): return stdin.readline().strip()↵
↵
N, M = map(int, input().split())↵
adj = defaultdict(list)↵
↵
for _ in range(M):↵
u, v, w = map(int, input().split())↵
u -= 1↵
v -= 1↵
adj[u].append((v, w))↵
adj[v + N].append((u + N, w))↵
for i in range(N):↵
adj[i].append((i + N, 0))↵
↵
dist = [float('inf')]*(2*N)↵
visited = [False]*(2*N)↵
dist[0] = 0↵
pq = [(0, 0)]↵
while pq:↵
d, v = heappop(pq)↵
if visited[v]:↵
continue↵
visited[v] = True↵
for ch, w in adj[v]:↵
new_d = d + w↵
if new_d < dist[ch]:↵
dist[ch] = new_d↵
heappush(pq, (new_d, ch))↵
↵
for i in range(N + 1, 2*N):↵
if dist[i] == float('inf'):↵
print("-1", end=" ")↵
else:↵
print(dist[i], end=" ")↵
```↵
</spoiler>↵
↵
↵
↵
↵
#### [E. Safe Roads](https://codeforces.net/gym/557458/problem/E)↵
↵
<spoiler summary = "Solution">↵
In this problem we will find the sought quantity for every vertex and find the maximum value. For this for every vertex $v$ count two values: $cnt1[v]$ and $cnt2[v]$ — number of shortest paths from vertex $v$ to $n$-th and $1$-st vertices respectively. For this you should construct graph of shortest paths and use dynamic programming on the constructed graph (because the new graph will be acyclic). To construct the graph of shortest paths you should leave only useful edges in original graph. It can be done, for example, using breadth-first search launched from vertices $1$ and $n$ respectively.↵
↵
After values $cnt1[v]$ and $cnt2[v]$ are found consider every useful edge $(u, v)$ and add to vertices $u$ and $v$ value $(cnt2[u] * cnt1[v]) / (cnt2[n–1])$, which is the contribution of this edge in the sought quantity for the vertices $u$ and $v$. Note that value $(cnt2[n–1])$ is the number of shortest paths between $1$ and $n$. All said values can be found in time $O(N + M)$. The complexity of solution is $O(N + M)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from collections import deque, defaultdict↵
↵
def solve():↵
n, m = map(int, input().split())↵
g = defaultdict(list)↵
↵
for _ in range(m):↵
u, v = map(int, input().split())↵
g[u].append(v)↵
g[v].append(u)↵
↵
que = deque([1])↵
vis = [-1] * (n + 1)↵
visr = [-1] * (n + 1)↵
ways = [0] * (n + 1)↵
waysr = [0] * (n + 1)↵
↵
vis[1] = 0↵
ways[1] = 1↵
dis = 1↵
↵
while que:↵
cur_s = len(que)↵
for _ in range(cur_s):↵
node = que.popleft()↵
for child in g[node]:↵
if vis[child] == -1:↵
que.append(child)↵
vis[child] = dis↵
ways[child] = ways[node]↵
elif dis == vis[child]:↵
ways[child] += ways[node]↵
dis += 1↵
↵
que.append(n)↵
dis = 1↵
visr[n] = 0↵
waysr[n] = 1↵
↵
while que:↵
cur_s = len(que)↵
for _ in range(cur_s):↵
node = que.popleft()↵
for child in g[node]:↵
if visr[child] == -1:↵
que.append(child)↵
visr[child] = dis↵
waysr[child] = waysr[node]↵
elif dis == visr[child]:↵
waysr[child] += waysr[node]↵
dis += 1↵
↵
ans = 1.0↵
div = vis[n]↵
↵
for i in range(2, n):↵
cur_total = 0↵
for child in g[i]:↵
if vis[i] + visr[child] + 1 == vis[n]:↵
cur_total += ways[i] * waysr[child]↵
↵
ans = max(ans, (cur_total / ways[n]) * 2)↵
↵
print(ans)↵
↵
if __name__ == "__main__":↵
solve()↵
```↵
</spoiler>↵
↵
