Welcome to our weekly review of AtCoder Beginner Contest 435~ In this series, we explore programming problems from AtCoder’s weekly contests and break down complex concepts into simple solutions!
A - Triangular Number
If you are new to AtCoder, check out the official getting-started page!
Problem. You are given a positive integer $N$. Find $1+2+\dots+N$.
Solution. The sum of the first $N$ positive integers is equal to
$$1+2+\dots+N=\frac{(1+N)+(2+N-1)+\dots+(N+1)}2=\frac{N(N+1)}2.$$
We can use the above formula or use a for-loop to solve the problem.
Implementation in Python
N = int(input())
print(N * (N + 1) // 2)
B - No-Divisible Range
Problem. You are given a sequence $A=(A_1, A_2, \dots, A_N)$ of $N$ positive integers.
Find the number of tuples $(\ell, r)$ such that:
- $1\leq\ell\leq r\leq N$, and
- For all integers $\ell\leq i\leq r$, $A_i$ is not a divisor of $A_\ell+A_{\ell+1}+\dots+A_r$.
Solution. We can use a nested loop to iterate through every pair of $(l, r)$. Within each loop, we can compute $A_\ell+A_{\ell+1}+\dots+A_r$, then check whether any $A_i$ is a divisor of the sum.
Implementation in Python
N = int(input())
A = [int(x) for x in input().split()]
result = 0
for l in range(N):
for r in range(l + 1, N + 1):
s = sum(A[l:r])
result += all(s % a != 0 for a in A[l:r])
print(result)
C - Domino
Problem. There are $N\leq5\times10^5$ dominoes placed on a straight line. The $i$-th domino stands at coordinate $i$ and has height $A_i\geq 1$.
When the $i$-th domino falls to the right, every domino with a coordinate at least $i$ and less than $i+A_i$ falls to the right as well.
Find the total number of dominoes that fall to the right after the first domino falls to the right.
Solution. Whenever a domino falls, we can update the rightmost reachable coordinate and sequentially check whether the next domino will fall as well. Since the dominoes only fall to the right, a single iteration is sufficient.
Implementation in Python
N = int(input())
A = [int(x) for x in input().split()]
result = 1
bound_right = A[0]
for i in range(1, N):
if i >= bound_right:
break
result += 1
bound_right = max(bound_right, i + A[i])
print(result)
D - Reachability Query 2
Problem. You are given a directed graph with $N\leq3\times10^5$ vertices and $M\leq3\times10^5$ edges. The vertices are labeled $1$ to $N$. All vertices are initially white.
You are given $Q\leq3\times10^5$ queries to be processed. There are two types of queries:
-
1 v: Color vertexvblack. -
2 v: Output whether it is possible to reach a black vertex from vertexv.
Solution. To process query 2, we can attempt to traverse the entire graph to look for a black vertex. However, doing a BFS/DFS per query leads to $\mathcal{O}(Q(N+M))$ computational time, resulting in TLE for large $Q$.
To reduce computational cost, we should traverse the graph only when a new vertex is colored black in query 1 and update the vertices that reach it. We can reverse the direction of edges in the graph and run BFS or DFS from the new black vertex to find all vertices that can reach it in the original graph.
Moreover, in BFS and DFS, vertices that are already visited do not need to be processed again. Likewise, when we update reachability for query 1, we can ignore vertices that already reach a black vertex as well.
The combined time complexity of graph traversal for query 1 is $\mathcal{O}(N+M)$. Using precomputed results from graph traversal, each query 2 can be answered in $\mathcal{O}(1)$ time.
Implementation in Python
from collections import deque
N, M = (int(x) for x in input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
u, v = (int(x) - 1 for x in input().split())
graph[v].append(u)
reaches_black = [False] * N
for _ in range(int(input())):
t, v = (int(x) for x in input().split())
v -= 1
if t == 2:
if reaches_black[v]:
print("Yes")
else:
print("No")
continue
if reaches_black[v]:
continue
reaches_black[v] = True
q = deque([v])
while q:
u = q.popleft()
for w in graph[u]:
if reaches_black[w]:
continue
reaches_black[w] = True
q.append(w)
E - Cover query
Problem. There are $N\leq10^9$ white cells and $Q\leq2\times10^5$ queries.
Process the $Q$ queries in order. For each query $i\in\{1, \dots, Q\}$, you are given integers $1\leq L_i\leq R_i\leq N$. Color the cells $L_i, L_i+1, \dots, R_i$ black, then output the number of cells that remain white.
Solution. We can manage intervals of black cells in an ordered set and keep track of the number of cells that remain white after each query. For simplicity, we will use half-opened intervals $[\ell, r)$ to represent consecutive black cells $\ell, \ell+1, \dots, r - 1$.
Whenever we add a new interval $[\ell, r)$ to the set:
- If the set already contains an interval $[L, R)$ such that $L\leq\ell\lt r\leq R$, no new cells will be colored black, so we do not need to modify the set.
- Otherwise, we will insert $[\ell, r)$ into the set. To avoid overcounting black cells, we will first remove all intervals $[\ell^\prime, r^\prime)$ for which $\ell\leq\ell^\prime\lt r^\prime\leq r$ from the set. As we remove them, we should also revert the black cells to avoid overcounting. Finally, we insert $[\ell, r)$ into the set and update the number of white cells accordingly.
- Beware of overlapping intervals around the boundaries. For example, if the set contains some interval $[L, r^\prime)$ for which $L\lt\ell\lt r^\prime\lt r$, we can either merge the two intervals or contract the inserted interval to be $[r^\prime, r)$. Both options result in the same time complexity.
Since we only add at most $Q$ intervals to the set, the maximum number of removed intervals is also $Q$, hence the time complexity of inserting and removing intervals is $\mathcal{O}(Q\log Q)$ across all queries.
Implementation in C++
#include <iostream>
#include <set>
int main() {
int N, Q;
std::cin >> N >> Q;
int result = N;
std::set<std::pair<int, int>> intervals;
while (Q--) {
int l, r;
std::cin >> l >> r;
l--;
auto iter = intervals.lower_bound({l, l});
if (iter != intervals.begin()) {
auto [L, R] = *std::prev(iter);
if (r <= R) {
std::cout << result << std::endl;
continue;
}
if (l <= R) l = R;
}
while (iter != intervals.end() && iter->first < r) {
auto [L, R] = *iter;
if (r <= R) {
r = L;
break;
}
result += R - L;
iter = intervals.erase(iter);
}
result -= r - l;
intervals.emplace(l, r);
std::cout << result << std::endl;
}
}
Implementation in Python
The following solution uses SortedSet written by tatyam. You can find the documented source code here. Since this implementation uses square-root decomposition instead of binary trees, the time complexity of our solution is $\mathcal{O}(Q^{1.5})$. However, it is worth noting that tatyam's SortedSet usually performs better than implementations based on balanced trees in Python.
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.py
# paste SortedSet here
N, Q = (int(x) for x in input().split())
queries = [tuple(int(x) for x in input().split()) for _ in range(Q)]
result = N
intervals = SortedSet()
for l, r in queries:
l -= 1
i = intervals.index((l, l))
if i > 0:
L, R = intervals[i - 1]
if r <= R:
print(result)
continue
if l <= R:
l = R
while i < len(intervals):
L, R = intervals[i]
if L >= r:
break
if r <= R:
r = L
break
result += R - L
intervals.discard((L, R))
result -= r - l
intervals.add((l, r))
print(result)
F - Cat exercise
Problem. There are $N\leq2\times10^5$ cat trees arranged in a straight line. Tree $i$ is the $i$-th cat tree from the left and has a height of $P_i$. It is guaranteed that $(P_1, \dots, P_N)$ is a permutation of $(1, \dots, N)$.
Takahashi's cat is sitting on top of the tallest cat tree. Takahashi wants his cat to exercise by sequentially removing the cat trees. They repeat the following actions:
- Takahashi chooses an existing tree $i$ and removes it.
- If the cat is not standing on top of tree $i$, the cat does not move.
- If the cat is standing on top of tree $i$, the cat chooses the second-tallest tree $j$ that can be reached by repeatedly moving among existing adjacent trees. Here, two trees $p$ and $q$ are considered adjacent if $|p-q|=1$. If no such tree exists, the exercise ends. Otherwise, the cat moves to tree $j$ over a distance of $|i-j|$.
Find the maximum total distance the cat moves before the exercise ends.
Solution. Suppose the cat currently stands on tree $i$. When Takahashi removes tree $i$, the cat can move either to the left or to the right. Note that if both directions are possible, Takahashi can guide the cat to either direction by removing the other cat trees first. Thus, we can break the problem into two subproblems: maximizing distance after the cat moves to the left and to the right. We can use recursion to solve both subproblems and answer the original problem.
To solve the subproblems, we also need an efficient method to find the position of the second-tallest cat tree in both directions. We will imagine the cat trees as vertices and add edges from each vertex to the second-tallest trees in its connected region.
- The vertex representing the highest cat tree has two child vertices, each representing the second-tallest cat trees in the two directions. The two children represent disjoint regions after the tallest cat tree is removed.
- Each child represents the highest cat tree in its connected component, and we can recursively define their children as the second-tallest trees in both directions.
The resulting graph is known as a Cartesian tree. We can build a Cartesian tree in $\Theta(N)$ time to find the tallest cat trees in each region, and use it to help us build a recursive solution that runs in $\Theta(N)$ time as well.
Implementation in Python
import sys
sys.setrecursionlimit(300000)
N = int(input())
P = [int(x) for x in input().split()]
parent = [-1] * N
stack = []
for i in range(N):
j = -1
while stack and P[stack[-1]] < P[i]:
j = stack.pop()
if j != -1:
parent[j] = i
if stack:
parent[i] = stack[-1]
stack.append(i)
root = -1
tree = [[] for _ in range(N)]
for i in range(N):
if parent[i] == -1:
root = i
else:
tree[parent[i]].append(i)
def solve(i):
result = 0
for j in tree[i]:
result = max(result, abs(i - j) + solve(j))
return result
print(solve(root))
Want a more challenging problem involving Cartesian trees? Try this one next!
Fabulous work!
Really appreciate that you made it this far into this week's contest. Don't worry, we will be back for more! See you next time, and watch out for those nasty TLEs! ⏱️🚀