[Here](https://mirror.codeforces.com/gym/535749) is the link to the contest. All problems are from Codeforces' problemset.↵
↵
↵
#### [A. A2SV Contest #25](https://mirror.codeforces.com/gym/535749/problem/A)0↵
↵
<spoiler summary="Solution">↵
<p>↵
We can compute the points gained by each person using the formula provided and compare their points.↵
</p>↵
<p>↵
In the formula, for $Misha$, $p = a$ and $t = c$; and for $Vasya$, $p = b$ and $t = d$. ↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
a, b, c, d = map(int, input().split())↵
↵
def find_points(p, t):↵
return max((3*p)//10, p - (p*t)//250)↵
↵
↵
Misha = find_points(a, c)↵
Vasya = find_points(b, d)↵
↵
if Misha > Vasya:↵
print('Misha')↵
↵
elif Misha < Vasya:↵
print('Vasya')↵
↵
else:↵
print('Tie')↵
↵
```↵
</spoiler>↵
↵
#### [B. Optimal Point](https://mirror.codeforces.com/gym/535749/problem/B)↵
↵
<spoiler summary="Solution">↵
↵
We just have to check if $k$ is equal to at least one $l_i$ and at least one $r_i$. If both conditions satisfy, we can take those intervals with $l_i = k$ and $r_i = k$ and remove the rest. Then, $k$ will have a frequency of $2$ and the rest will have a frequency of $1$ or $k$ will have a frequency of $1$ and the rest will have a frequency of $0$. If one or two of the conditions fail, we can be sure that $k$ will always have less or equal frequency with at least one of it's neighbors. ↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
T = int(input())↵
↵
for _ in range(T):↵
N, K = map(int, input().split())↵
↵
l_ok = r_ok = False↵
for _ in range(N):↵
l, r = map(int, input().split())↵
↵
if l == K:↵
l_ok = True↵
if r == K:↵
r_ok = True↵
↵
if l_ok and r_ok:↵
print("YES")↵
else:↵
print("NO")↵
↵
```↵
</spoiler>↵
↵
#### [C. Selecting Theatre Troupe](https://mirror.codeforces.com/gym/535749/problem/C)↵
↵
<spoiler summary = "Solution">↵
↵
Since the constraints are small, let's just iterate through all possible numbers $b$ of boys in the group and count how many ways we can form the group with $b$ boys.↵
↵
↵
First, consider only the values where $b >= 4$. Given $b$, it's clear that the number of girls in the group must be $g = t - b$. If $g < 1$, don't consider this case. Given the values of $b$ and $g$, there are $comb(n, b)$* $comb(m, g)$ ways to form the group, since we can combine the boys independently of the girls. Just sum $comb(n, b)$* $comb(m, g)$ for each pair $(b, g)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
↵
from math import comb↵
↵
n, m, t = map(int, sys.stdin.readline().strip().split())↵
↵
ans = 0↵
for b in range(4, t):↵
ans += comb(n, b) * comb(m, t - b)↵
↵
print(ans)↵
```↵
</spoiler>↵
↵
↵
#### [D. Remoteness](https://mirror.codeforces.com/gym/535749/problem/D)↵
↵
<spoiler summary="Solution">↵
↵
↵
A graph-related problem. The statement makes you sure that the given graph is connected and contains one (and exactly one) cycle. What you have to do is to compute the distance, in number of edges, from all vertices to the cycle (print 0 for the vertex that are in the cycle. We will call these vertices 'in-cycle').↵
↵
First, let's find the cycle and find the vertices whose answer is 0. The cycle can be found with a regular Depth-First-Search (DFS), storing the fathers of the vertices. Notice that, during the search, there will be exactly one back edge, say $(v_i, v_j)$. When this edge is found, iterate from $v_i$ to $v_j$ (using the father array) and label the vertices as 'in-cycle'.↵
↵
After that, let's compute the answers for the other vertices. One could "compact" the graph by merging all the 'in-cycle' vertices into a single vertex. Then, just do another search starting with this vertex and compute the distances, knowing that the distance of a vertex vi is the distance of $father[vi]$ plus one.↵
↵
Also, it's also possible to do as many searches as the number of 'in-cycle' vertices if you don't consider others 'in-cycle' vertices during the search. The running time would still be $O(n + m)$, that, in this problem, is $O(n + n) = O(n)$.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
import math↵
↵
n=int(input())↵
e=[[] for _ in range(n)]↵
for _ in range(n):↵
x,y=map(int,input().split())↵
e[x-1].append(y-1)↵
e[y-1].append(x-1)↵
d=[len(x) for x in e]↵
q=[i for i in range(n) if d[i]==1]↵
↵
c=[0]*n↵
for u in q:↵
c[u]=n↵
for v in e[u]:↵
d[v]-=1↵
if d[v]==1:↵
q.append(v)↵
q.extend(i for i in range(n) if not c[i])↵
for u in q[::-1]:↵
for v in e[u]:↵
c[v]=min(c[v],c[u]+1)↵
print(" ".join(map(str,c)))↵
↵
```↵
</spoiler>↵
↵
↵
#### [E. Candies](https://mirror.codeforces.com/gym/535749/problem/E)↵
↵
<spoiler summary="Solution">↵
<p>↵
If the number of candies is less than $k$, Marmot can only eat red candies, which means the answer is always $1$. If the number of candies is equal to $k$, Marmot can eat $k$ red candies at once or $k$ white candies at once, making the answer $2$. We can consider these two cases as the base case.↵
↵
Now, the problem arises when the number of candies is greater than $k$. The $(ith)$ candy sequences can be either red or white, so we have two options at each sequence of candies. Let’s look at those options one by one:↵
↵
1. If the $(ith)$ sequence of candies is red, the remaining $(i - 1)$ candies can be red and white.↵
2. If the $(ith)$ sequence of candie is white, the remaining $(k - 1)$ candies should be white and the rest $(i - k)$ candies can be red and white.↵
↵
Since our target is to find the number different ways of candies sequences in which Marmot can eat, the answer for the $(ith$) sequence will be the summation of the number of ways at $(i - 1)$ and the number of ways at $(i - k)$.↵
↵
We can utilize prefix sum to answer with constant time complexity for each given input query or test case without recalculating again.↵
↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
↵
MAX = 10 ** 5 + 1↵
MOD = 10 ** 9 + 7↵
t, k = map(int, input().split())↵
↵
# it is obvious that the number of ways to in which Marmont can eat his dinner is 1 if the number of candies is less than k ↵
prfx = [1] * MAX↵
prfx[0] = 0↵
↵
# if the number of candies is equal to k the number of ways to eat his dinner is 2↵
prfx[k] = 2↵
↵
# if the number of candies is greater than k the number of ways to eat his dinner is prfx[ith - 1] + prfx[ith - k] ↵
for i in range(k + 1, MAX):↵
prfx[i] = (prfx[i - 1] + prfx[i - k]) % MOD ↵
↵
# calculating the prefix sum of the number of ways to eat his dinner to minimize the time complexity from O(t * (b - a)) to O(MAX)↵
for i in range(1, MAX):↵
prfx[i] = (prfx[i] + prfx[i - 1]) % MOD↵
↵
for _ in range(t):↵
a, b = map(int, input().split())↵
print((prfx[b] - prfx[a - 1]) % (10 ** 9 + 7))↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
#### [A. A2SV Contest #25](https://mirror.codeforces.com/gym/535749/problem/A)
↵
<spoiler summary="Solution">↵
<p>↵
We can compute the points gained by each person using the formula provided and compare their points.↵
</p>↵
<p>↵
In the formula, for $Misha$, $p = a$ and $t = c$; and for $Vasya$, $p = b$ and $t = d$. ↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
input = lambda: sys.stdin.readline().rstrip()↵
↵
a, b, c, d = map(int, input().split())↵
↵
def find_points(p, t):↵
return max((3*p)//10, p - (p*t)//250)↵
↵
↵
Misha = find_points(a, c)↵
Vasya = find_points(b, d)↵
↵
if Misha > Vasya:↵
print('Misha')↵
↵
elif Misha < Vasya:↵
print('Vasya')↵
↵
else:↵
print('Tie')↵
↵
```↵
</spoiler>↵
↵
#### [B. Optimal Point](https://mirror.codeforces.com/gym/535749/problem/B)↵
↵
<spoiler summary="Solution">↵
↵
We just have to check if $k$ is equal to at least one $l_i$ and at least one $r_i$. If both conditions satisfy, we can take those intervals with $l_i = k$ and $r_i = k$ and remove the rest. Then, $k$ will have a frequency of $2$ and the rest will have a frequency of $1$ or $k$ will have a frequency of $1$ and the rest will have a frequency of $0$. If one or two of the conditions fail, we can be sure that $k$ will always have less or equal frequency with at least one of it's neighbors. ↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
T = int(input())↵
↵
for _ in range(T):↵
N, K = map(int, input().split())↵
↵
l_ok = r_ok = False↵
for _ in range(N):↵
l, r = map(int, input().split())↵
↵
if l == K:↵
l_ok = True↵
if r == K:↵
r_ok = True↵
↵
if l_ok and r_ok:↵
print("YES")↵
else:↵
print("NO")↵
↵
```↵
</spoiler>↵
↵
#### [C. Selecting Theatre Troupe](https://mirror.codeforces.com/gym/535749/problem/C)↵
↵
<spoiler summary = "Solution">↵
↵
Since the constraints are small, let's just iterate through all possible numbers $b$ of boys in the group and count how many ways we can form the group with $b$ boys.↵
↵
↵
First, consider only the values where $b >= 4$. Given $b$, it's clear that the number of girls in the group must be $g = t - b$. If $g < 1$, don't consider this case. Given the values of $b$ and $g$, there are $comb(n, b)$* $comb(m, g)$ ways to form the group, since we can combine the boys independently of the girls. Just sum $comb(n, b)$* $comb(m, g)$ for each pair $(b, g)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
↵
from math import comb↵
↵
n, m, t = map(int, sys.stdin.readline().strip().split())↵
↵
ans = 0↵
for b in range(4, t):↵
ans += comb(n, b) * comb(m, t - b)↵
↵
print(ans)↵
```↵
</spoiler>↵
↵
↵
#### [D. Remoteness](https://mirror.codeforces.com/gym/535749/problem/D)↵
↵
<spoiler summary="Solution">↵
↵
↵
A graph-related problem. The statement makes you sure that the given graph is connected and contains one (and exactly one) cycle. What you have to do is to compute the distance, in number of edges, from all vertices to the cycle (print 0 for the vertex that are in the cycle. We will call these vertices 'in-cycle').↵
↵
First, let's find the cycle and find the vertices whose answer is 0. The cycle can be found with a regular Depth-First-Search (DFS), storing the fathers of the vertices. Notice that, during the search, there will be exactly one back edge, say $(v_i, v_j)$. When this edge is found, iterate from $v_i$ to $v_j$ (using the father array) and label the vertices as 'in-cycle'.↵
↵
After that, let's compute the answers for the other vertices. One could "compact" the graph by merging all the 'in-cycle' vertices into a single vertex. Then, just do another search starting with this vertex and compute the distances, knowing that the distance of a vertex vi is the distance of $father[vi]$ plus one.↵
↵
Also, it's also possible to do as many searches as the number of 'in-cycle' vertices if you don't consider others 'in-cycle' vertices during the search. The running time would still be $O(n + m)$, that, in this problem, is $O(n + n) = O(n)$.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
import math↵
↵
n=int(input())↵
e=[[] for _ in range(n)]↵
for _ in range(n):↵
x,y=map(int,input().split())↵
e[x-1].append(y-1)↵
e[y-1].append(x-1)↵
d=[len(x) for x in e]↵
q=[i for i in range(n) if d[i]==1]↵
↵
c=[0]*n↵
for u in q:↵
c[u]=n↵
for v in e[u]:↵
d[v]-=1↵
if d[v]==1:↵
q.append(v)↵
q.extend(i for i in range(n) if not c[i])↵
for u in q[::-1]:↵
for v in e[u]:↵
c[v]=min(c[v],c[u]+1)↵
print(" ".join(map(str,c)))↵
↵
```↵
</spoiler>↵
↵
↵
#### [E. Candies](https://mirror.codeforces.com/gym/535749/problem/E)↵
↵
<spoiler summary="Solution">↵
<p>↵
If the number of candies is less than $k$, Marmot can only eat red candies, which means the answer is always $1$. If the number of candies is equal to $k$, Marmot can eat $k$ red candies at once or $k$ white candies at once, making the answer $2$. We can consider these two cases as the base case.↵
↵
Now, the problem arises when the number of candies is greater than $k$. The $(ith)$ candy sequences can be either red or white, so we have two options at each sequence of candies. Let’s look at those options one by one:↵
↵
1. If the $(ith)$ sequence of candies is red, the remaining $(i - 1)$ candies can be red and white.↵
2. If the $(ith)$ sequence of candie is white, the remaining $(k - 1)$ candies should be white and the rest $(i - k)$ candies can be red and white.↵
↵
Since our target is to find the number different ways of candies sequences in which Marmot can eat, the answer for the $(ith$) sequence will be the summation of the number of ways at $(i - 1)$ and the number of ways at $(i - k)$.↵
↵
We can utilize prefix sum to answer with constant time complexity for each given input query or test case without recalculating again.↵
↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
↵
MAX = 10 ** 5 + 1↵
MOD = 10 ** 9 + 7↵
t, k = map(int, input().split())↵
↵
# it is obvious that the number of ways to in which Marmont can eat his dinner is 1 if the number of candies is less than k ↵
prfx = [1] * MAX↵
prfx[0] = 0↵
↵
# if the number of candies is equal to k the number of ways to eat his dinner is 2↵
prfx[k] = 2↵
↵
# if the number of candies is greater than k the number of ways to eat his dinner is prfx[ith - 1] + prfx[ith - k] ↵
for i in range(k + 1, MAX):↵
prfx[i] = (prfx[i - 1] + prfx[i - k]) % MOD ↵
↵
# calculating the prefix sum of the number of ways to eat his dinner to minimize the time complexity from O(t * (b - a)) to O(MAX)↵
for i in range(1, MAX):↵
prfx[i] = (prfx[i] + prfx[i - 1]) % MOD↵
↵
for _ in range(t):↵
a, b = map(int, input().split())↵
print((prfx[b] - prfx[a - 1]) % (10 ** 9 + 7))↵
↵
↵
```↵
</spoiler>↵
↵
↵
