Here is the link to the contest.
A. Shalamagando's workout
Initialize three variables $$$chest$$$, $$$biceps$$$, and $$$back$$$ to $$$0$$$, representing the total repetitions for each muscle group. Loop through the repetitions of exercises, and for each exercise: If the $$$index$$$ is divisible by $$$3$$$ (chest exercises), add the repetitions to the $$$chest$$$ variable. If the $$$index$$$ modulo $$$3$$$ is $$$1$$$ (biceps exercises), add the repetitions to the $$$biceps$$$ variable. If the $$$index$$$ modulo $$$3$$$ is $$$2$$$ (back exercises), add the repetitions to the $$$back$$$ variable Compare the values of $$$chest$$$, $$$biceps$$$, and $$$back$$$ to determine which muscle group has the highest total repetitions.
Time Complexity: $$$O(n)$$$, $$$n$$$ is input size
Space Complexity: $$$O(1)$$$
def main():
n = int(input())
routine = list(map(int, input().split()))
exercises = [0, 0, 0]
for turn in range(n):
exercises[turn % 3] += routine[turn]
if exercises[0] > exercises[1] and exercises[0] > exercises[2]:
print('chest')
elif exercises[1] > exercises[2]:
print('biceps')
else:
print('back')
if __name__ == '__main__':
main()
B. Path Finder
Since we know the start of the path, we can begin our DFS or BFS from 0 while tracking the distance covered so far. Whenever we add a new node to our path, we include the distance between the parent node and the current node, maximizing our answer because we seek the maximum distance. Finally, output the maximum distance that we found.
V = int(input())
adj = [[] for __ in range(V)]
for _ in range(V - 1):
u, v, c = list(map(int, input().split()))
adj[u].append((v, c))
adj[v].append((u, c))
stack = [(0, 0)]
visited = set([0])
max_cost = 0
while stack:
curr, cost = stack.pop()
max_cost = max(max_cost, cost)
for ed, nxt_cost in adj[curr]:
if ed not in visited:
visited.add(ed)
stack.append((ed, cost + nxt_cost))
print(max_cost)
C. Painting Class
Consider the process from the end, we will "delete" any subtree from the tree, whose color of the ancestor of the highest vertex differs from the color of the highest vertex and the colors of all vertices in the subtree are the same. Thus, we can show that the answer is the number of edges whose ends have different colors + 1.
from collections import deque
from sys import stdin
def input(): return stdin.readline().strip()
N = int(input())
parents = list(map(int, input().split()))
color = list(map(int, input().split()))
adj = [[] for _ in range(N)]
for ch, p in enumerate(parents, 1):
adj[p - 1].append(ch)
q = deque([(0, color[0])])
ans = 1
while q:
v, c = q.popleft()
for ch in adj[v]:
q.append((ch, color[ch]))
ans += (color[ch] != c)
print(ans)
D. Moving the Bishop
Let's label the diagonal that goes from the top-left to the bottom-right as "diagonal 1" and the diagonal that goes from the bottom-left to the top-right as "diagonal 2". Any cell $$$s_{i,j}$$$ can be visited in these two different diagonals. If the cell was visited with diagonal 1 with a cost of $$$d$$$, all the cells it can reach in diagonal 2 will have a cost of $$$d + 1$$$. Similarly, if the cell was visited with diagonal 2, the cells it can reach on diagonal 1 will have a cost of $$$d + 1$$$. Since the cost of the reachable cells differs based on the diagonal that their parent was visited from, we need to calculate the shortest path for each visited cell for both diagonals.
To calculate the shortest path, we can use BFS starting at the current position of the bishop for both diagonals in our queue. For every element in the queue, if it was visited with diagonal 1, since the cell that visited it will visit all the nodes in that diagonal, we only need to calculate for diagonal 2, and vice versa. While we are calculating for one diagonal, we will calculate for all nodes until we encounter an obstacle, reach a cell that was visited with that diagonal, go out of bounds, or reach the target cell. We return the answer when we reach the target or -1 if we can't reach it.
from collections import deque
from sys import stdin
def input(): return stdin.readline().strip()
N = int(input())
start_x, start_y = map(int, input().split())
target_x, target_y = map(int, input().split())
start_x -= 1
start_y -= 1
target_x -= 1
target_y -= 1
grid = []
for _ in range(N):
grid.append(input())
visited = [[[False, False] for _ in range(N)] for _ in range(N)]
queue = deque([(start_x, start_y, 1, 1), (start_x, start_y, -1, 1)])
moves = 0
while queue:
queue_length = len(queue)
for _ in range(queue_length):
x, y, dx, dy = queue.popleft()
if x == target_x and y == target_y:
print(moves)
exit()
visited[x][y][0] = visited[x][y][1] = True
is_diagonal = (dx == dy)
for direction in [1, -1]:
for i in range(1, 2 * N):
nx = x + i * dx * direction
ny = y + i * dy * direction
if nx < 0 or nx >= N or ny < 0 or ny >= N or grid[nx][ny] == '#' or visited[nx][ny][is_diagonal]:
break
if not visited[nx][ny][0] and not visited[nx][ny][1]:
queue.append((nx, ny, -dx, dy))
visited[nx][ny][is_diagonal] = True
moves += 1
print(-1)
E. Chasing Parity
Let's try to solve the problem for odd numbers and then just run the same algorithm with even numbers.
In this problem, we have directed graph consisting of $$$n$$$ vertices (indices of the array) and at most $$$2n−2$$$ edges. Our problem is to find for every vertex the nearest vertex having the opposite parity. Let's try to solve the problem for odd numbers and then just run the same algorithm with even numbers.
We have multiple odd vertices and we need to find the nearest even vertex for each of these vertices. This problem can be solved with the standard and simple but pretty idea. Let's inverse our graph and run a multi-source breadth-first search from all even vertices. The only difference between standard bfs and multi-source bfs is that the second one have many vertices at the first step (vertices having zero distance).
Now we can notice that because of bfs every odd vertex of our graph has the distance equal to the minimum distance to some even vertex in the initial graph. This is exactly what we need. Then just run the same algorithm for even numbers and print the answer.
Time complexity: $$$O(n)$$$ .
import sys
from collections import defaultdict, deque
n = int(sys.stdin.readline().strip())
arr = list(map(int, sys.stdin.readline().strip().split()))
graph = defaultdict(list)
for i in range(n):
left, right = i - arr[i], i + arr[i]
if left > -1:
graph[left].append(i)
if right < n:
graph[right].append(i)
def bfs(start, _end):
_value = [-1] * n
queue = deque()
for num in start:
queue.append(num)
_value[num] = 0
while queue:
cur = queue.popleft()
for to in graph[cur]:
if _value[to] == -1:
_value[to] = _value[cur] + 1
queue.append(to)
for num in _end:
ans[num] = _value[num]
odd = []
even = []
for i, num in enumerate(arr):
if num % 2:
odd.append(i)
else:
even.append(i)
ans = [-1] * n
bfs(odd, even)
bfs(even, odd)
print(*ans)