[ABC429] Let's Review: AtCoder Beginner Contest 429 A~F 🧐

Welcome to our weekly review of AtCoder Beginner Contest 429! In this series, we explore the problems from AtCoder’s weekly programming contests, highlighting the main ideas and providing sample solutions.

A - Too Many Requests

If you are new to AtCoder, check out the official getting-started page!

Problem. You are given positive integers $N$ and $M$. For $i\in\{1, \dots, N\}$, print the following text on the $i$-th line:

• OK if $i\leq M$;
• Too Many Requests otherwise.

Solution.

Implementation in Python

main.py

N, M = (int(x) for x in input().split())
for i in range(1, N + 1):
    if i <= M:
        print("OK")
    else:
        print("Too Many Requests")

B - N - 1

Problem. You are given a sequence $A=(A_1, \dots, A_N)$ of $N$ integers. Determine if it is possible to remove exactly one element from $A$ so that the remaining elements sum to $M$.

Solution. A direct approach is to iterate over each index, remove that element, and compute the sum of the remaining integers. This solution runs in $\mathcal{O}(N^2)$ time.

Implementation in Python

main.py

N, M = (int(x) for x in input().split())
A = [int(x) for x in input().split()]

for i in range(N):
    sum_other = 0
    for j in range(N):
        if i != j:
            sum_other += A[j]
    if sum_other == M:
        print("Yes")
        exit()

print("No")

Alternatively, if removing an element $A_j$ makes the sum equal to $M$, then

$$\sum_{i=1}^N A_i - A_j=M \iff A_j=\sum_{i=1}^N A_i - M.$$

Thus, we can simply check whether $\displaystyle\sum_{i=1}^N A_i - M$ appears in $A$, yielding a more efficient $\mathcal{O}(N)$ solution.

Implementation in Python

main.py

N, M = (int(x) for x in input().split())
A = [int(x) for x in input().split()]
if sum(A) - M in A:
    print("Yes")
else:
    print("No")

C - Odd One Subsequence

Problem. You are given a sequence $A=(A_1, \dots, A_N)$ of $N\leq2\times10^5$ integers between $1$ and $N$. Find the number of triples of integers $(i, j, k)$ such that:

• $1\leq i\lt j\lt k\leq N$, and
• Exactly two of $A_i, A_j, A_k$ are equal to each other.

Solution. Let $c_a$ be the number of times the integer $a$ appears in $A$. To construct a triplet $(i, j, k)$ such that exactly two of $A_i, A_j, A_k$ are equal to $a$, we must first choose two of the $c_a$ elements: there are $\displaystyle\binom{c_a}2=\frac{c_a(c_a-1)}2$ ways to do so. Moreover, we need to choose a third element not equal to $a$ from the rest of the $N-c_a$ elements in $A$. Thus, there are $\displaystyle\frac{c_a(c_a-1)}2\cdot(N-c_a)$ ways to construct our desired $(i, j, k)$.

We can repeat the above calculation for all integers $a$ that appear in the sequence $A$. For example, if we use a dictionary to count the occurrences of each integer, we can give a solution with a time complexity of $\Theta(N)$.

Implementation in Python

main.py

from collections import Counter
N = int(input())
A = Counter(int(x) for x in input().split())
result = 0
for c in A.values():
    result += c * (c - 1) // 2 * (N - c)
print(result)

D - On AtCoder Conference

Problem. Takahashi lives in a hut built on the shore of a circular pond with a circumference of $M\leq10^{12}$ units. Define point $x$ as the point on the circumference that is $x$ units away from the hut, clockwise.

Takahashi has $N\leq5\times10^5$ visitors today. Visitor $i$ is standing at point $A_i$. Here, $A_i$ are integers between $0$ and $M-1$. Multiple people may stand at the same location.

You are given an integer $C\leq N$. Compute $\displaystyle\sum_{i=0}^{M-1}X_i$ where $X_i$ is defined as follows:

• Takahashi starts at point $(i+0.5)$ and begins moving clockwise, greeting visitors he passes.
• Takahashi stops moving whenever he greets at least $C$ visitors. If there are multiple visitors at the location Takahashi stops, Takahashi will still greet everyone, so he may end up greeting more than $C$ people.
• Define $X_i$ as the total number of visitors Takahashi greets.

Solution. Although the problem defines $M$ different $X_i$ values, many of them are identical. For example, if a visitor stands on point $x$ and another stands on point $y$ with nobody between them, then $X_i$ is identical for all $i\in[x, y)$. Thus, after sorting visitors by location, we can group the indices $i$ into intervals without visitors and compute the contribution for each interval.

To determine how many visitors Takahashi greets in total, we can use the two-pointer technique to compute the number of visitors for every given starting point. Another approach is to maintain the prefix sum of the number of visitors around the lake and use binary search to determine the number of visitors greeted.

The time complexity of both approaches is $\mathcal{O}(N\log N)$.

Implementation in Python (two-pointer technique)

main.py

from collections import Counter

N, M, C = (int(x) for x in input().split())
A = Counter(int(x) for x in input().split())

visitors = sorted(A.items())
L = len(visitors)

result = 0
num_greeted = 0
x = visitors[-1][0] - M
stop = 0
for start in range(L):
    y = visitors[start][0]
    while num_greeted < C:
        num_greeted += visitors[stop][1]
        stop = (stop + 1) % L
    result += (y - x) * num_greeted
    num_greeted -= visitors[start][1]
    x = y

print(result)

Implementation in Python (prefix sum & binary search)

main.py

from collections import Counter
import bisect

N, M, C = (int(x) for x in input().split())
A = Counter(int(x) for x in input().split())

visitors = sorted(A.items())
L = len(visitors)
pfxsum = [0] * (L * 2 + 1)
for i in range(L):
    pfxsum[i + 1] = visitors[i][1]
    pfxsum[i + L + 1] = visitors[i][1]
for i in range(L * 2):
    pfxsum[i + 1] += pfxsum[i]

result = 0
x = visitors[-1][0] - M
for i in range(L):
    j = bisect.bisect_left(pfxsum, pfxsum[i] + C)
    num_greeted = pfxsum[j] - pfxsum[i]
    y = visitors[i][0]
    result += (y - x) * num_greeted
    x = y

print(result)

E - Hit and Away

Problem. You are given a simple connected undirected graph with $N\leq2\times10^5$ vertices and $M\leq2\times10^5$ edges. Edge $i$ connects vertices $U_i$ and $V_i$. Each edge has a distance of $1$.

You are also given a string $S$ of $N$ characters. If the $i$-th character is S, vertex $i$ is safe; otherwise, the $i$-th character is D, indicating vertex $i$ is dangerous. At least two vertices are safe, and at least one vertex is dangerous.

For each dangerous vertex $v$, find the minimum distance of a walk between two distinct safe vertices that passes through $v$.

Solution. Consider the following subproblem:

For each dangerous vertex $v$, find the minimum distance of a path from $v$ to any safe vertex.

For this subproblem, we can use multi-source BFS to find the shortest distance from every dangerous vertex to its nearest safe vertex. The solution to this subproblem has a time complexity of $\Theta(M)$.

The original problem effectively requires finding two distinct safe vertices for each dangerous vertex, so we can extend the BFS approach to record the two smallest distances for every node. The new solution needs to process the same vertices and edges twice, but the time complexity will still be $\Theta(M)$.

Implementation in Python

main.py

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[u].append(v)
    graph[v].append(u)
S = input()

distance = [[(-1, -1)] * 2 for _ in range(N)]
q = deque()
for i in range(N):
    if S[i] == 'S':
        q.append((0, i, i))

while q:
    dist, u, source = q.popleft()
    for v in graph[u]:
        if distance[v][0][1] == source or distance[v][1][1] == source:
            continue
        if distance[v][0][0] == -1:
            distance[v][0] = (dist + 1, source)
            q.append((dist + 1, v, source))
        elif distance[v][1][0] == -1:
            distance[v][1] = (dist + 1, source)
            q.append((dist + 1, v, source))

for i in range(N):
    if S[i] == 'D':
        print(distance[i][0][0] + distance[i][1][0])

F - Shortest Path Query

Problem. You are given a grid with three rows and $N\leq2\times10^5$ columns. Cell $(i, j)$ denotes the cell located $i$ rows from the top and $j$ columns from the left. Each cell $(i, j)$ is either a wall cell if $S_{i,j}=$# or an empty cell if $S_{i,j}=$..

You are given $Q\leq2\times10^5$ queries. For each query:

1. You are given a cell $(r, c)$. If cell $(r, c)$ is a wall cell, modify it into an empty cell; otherwise, modify it into a wall cell.
2. Solve the following problem on the modified grid:
   • Takahashi starts at cell $(1, 1)$ and wants to reach $(3, N)$ by repeatedly moving to an adjacent, empty cell in the grid. Determine if Takahashi can reach $(3, N)$. If the cell is not reachable, output $-1$. Otherwise, output the minimum number of moves Takahashi must make before reaching $(3, N)$.

Solution. Observe that in any optimal path, Takahashi never needs to move left, since moving backward would only increase the total distance. A grid would need at least five rows to make leftward movement potentially optimal, as in the example below. Since our grid contains exactly three rows, we will only consider moving up, down, and right.

......#
#####.#
#.....#
#.#####
#......

Since Takahashi never moves to the left, we can use dynamic programming by iterating through the $N$ columns from left to right. The code below is the solution to the problem without the part of modifying the grid. It updates values in the dp array by considering movements from the $x$-th row in the previous column to the $y$-th row in the current column.

main.py

N = int(input())
S = [input() for _ in range(3)]

INF = N * 4
dp = [INF] * 3
dp[0] = -1

for j in range(N):
    ndp = [INF] * 3
    for x in range(3):
        for y in range(3):
            if all(S[i][j] == '.' for i in range(min(x, y), max(x, y) + 1)):
                ndp[y] = min(ndp[y], dp[x] + abs(x - y) + 1)
    dp = ndp

result = dp[2]
if result < INF:
    print(result)
else:
    print(-1)

To also process frequent updates to the grid, we need a data structure that allows us to reuse computed results for parts of the grid that remain unchanged. A solution is to use a segment tree to combine new information with existing results to efficiently answer queries.

The Python solution checks every pair of rows $(x, y)$ to find the solution for each row in the current column. When we generalize this approach for nodes in the segment tree, we should check every transition in the form of:

• starting from the $x$-th row in the first column of the previous node;
• moving to the $z$-th row in the last column of the current node;
• moving to the $z$-th row in the first column of the current node; and
• reaching the $y$-th row in the last column of the next node.

Since the transition always involves the first and last columns of a node, we need to store all nine possible pairs of rows $(x, y)$ in each segment tree node. While the new transition looks complicated, the logic behind the actual implementation below (specifically to_node and op) is completely identical to the Python solution.

The time complexity of our segment tree solution is $\mathcal{O}(N+Q\log N)$.

Implementation in C++

main.cpp

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <atcoder/segtree>

constexpr int INF = 1 << 27;

void chmin(int &a, int b) {
    if (a > b) a = b;
}

using node = std::array<std::array<int, 3>, 3>;

node to_node(const std::vector<std::string> &S, int j) {
    node result{};
    for (int x = 0; x < 3; x++) {
        for (int y = 0; y < 3; y++) {
            bool is_reachable = true;
            for (int i = std::min(x, y); i <= std::max(x, y); i++) {
                is_reachable &= S[i][j] == '.';
            }
            result[x][y] = is_reachable ? std::abs(x - y) : INF;
        }
    }
    return result;
}

node e() {
    node result{};
    result[0][0] = -1;
    return result;
}

node op(node a, node b) {
    if (a == e()) return b;
    if (b == e()) return a;
    node result{{{INF, INF, INF}, {INF, INF, INF}, {INF, INF, INF}}};
    for (int x = 0; x < 3; x++) {
        for (int y = 0; y < 3; y++) {
            for (int z = 0; z < 3; z++) {
                chmin(result[x][y], a[x][z] + b[z][y] + 1);
            }
        }
    }
    return result;
}

int main() {
    int N;
    std::cin >> N;
    std::vector<std::string> S(3);
    for (std::string &s : S) std::cin >> s;
    std::vector<node> vec(N);
    for (int j = 0; j < N; j++) vec[j] = to_node(S, j);
    atcoder::segtree<node, op, e> seg(vec);

    int Q;
    std::cin >> Q;
    while (Q--) {
        int r, c;
        std::cin >> r >> c;
        r--, c--;
        if (S[r][c] == '.') S[r][c] = '#';
        else S[r][c] = '.';
        seg.set(c, to_node(S, c));
        int result = seg.all_prod()[0][2];
        if (result < INF) std::cout << result << std::endl;
        else std::cout << -1 << std::endl;
    }
}

Time to pack up!

This week’s contest wasn’t the easiest, but that’s exactly the kind of challenge we love! See you next time, and watch out for those nasty TLEs! ⏱️🚀