Welcome to our weekly review of ✧･ﾟ: ✧･ﾟ: AtCoder Beginner Contest 437 :･ﾟ✧:･ﾟ✧

In this series, we explore programming problems from AtCoder’s weekly contests and break down complex concepts into simple solutions!

A - Feet

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

Problem. One foot is $12$ inches. How many inches is $A$ foot $B$ inches?

Solution.

Implementation in Python

main.py

A, B = (int(x) for x in input().split())
print(A * 12 + B)

B - Tombola

Problem. You are playing a game involving a grid with $H$ rows and $W$ columns. Each square in the grid has a unique integer between $1$ and $90$ written on it. The number on the square $i$ rows from the top and $j$ columns from the left is $A_{i,j}$.

The game host reads out $N$ distinct integers $B_1, \dots, B_N$ between $1$ and $90$. For each integer read by the host, if the integer is also on the grid, the integer is crossed out.

Find the maximum number of integers crossed out in a single row.

Solution. For each integer $B_i$, we check each row to see if the integer appears in that row, and increment a counter for the row that contains it.

Implementation in Python

main.py

H, W, N = (int(x) for x in input().split())
A = [[int(x) for x in input().split()] for _ in range(H)]

num_crossed = [0] * H
for _ in range(N):
    b = int(input())
    for i in range(H):
        if b in A[i]:
            num_crossed[i] += 1

print(max(num_crossed))

Since the integers are distinct, it is slightly more efficient to keep track of the position of each possible integer in the grid. This optimization is not necessary when there are only at most $90$ possible values, but it can be helpful for harder problems.

Implementation in Python

main.py

H, W, N = (int(x) for x in input().split())
A = [[int(x) for x in input().split()] for _ in range(H)]

row = [-1] * 91
for i in range(H):
    for a in A[i]:
        row[a] = i

num_crossed = [0] * H
for _ in range(N):
    b = int(input())
    if row[b] == -1:
        continue
    num_crossed[row[b]] += 1

print(max(num_crossed))

C - Reindeer and Sleigh 2

Problem. There are $N$ reindeer and a sled. The $i$-th reindeer has weight $1\leq W_i\leq10^9$ and strength $1\leq P_i\leq10^9$.

Each reindeer can either "pull the sled" or "ride the sled". If the total weight of reindeer riding the sled must not exceed the total strength of reindeer pulling the sled, what is the maximum number of reindeer that can ride the sled?

You are given $T$ test cases. The sum of $N$ in all $T$ test cases is at most $3\times10^5$.

Solution. We will refer to the reindeer as "riders" and "pullers". We will also define $X$ as the difference between the strength of pullers and the weight of riders. Since the weight of riders must not exceed the strength of pullers, our assignment should result in a non-negative $X$.

We start by considering the scenario in which all $N$ reindeer are pulling the sled. Initially, the difference between strength and weight is $\displaystyle X=\sum_{k=1}^N P_k$.

What happens if we assign reindeer $i$ to ride the sled instead? The weight of riding reindeer now increases by $W_i$, while the strength of pulling reindeer decreases by $P_i$. Thus, the new assignment results in a decrease of $W_i+P_i$ in $X$.

Using these observations, we can rephrase the problem as:

There are $N$ reindeer pulling a sled with a total strength of $\displaystyle X^\prime=\sum_{k=1}^N P_k$. Each reindeer can keep pulling the sled or stop pulling. If reindeer $i$ stops pulling, the total strength $X^\prime$ decreases by $D_i=W_i+P_i$. What is the maximum number of reindeer that can stop pulling the sled if $X^\prime$ must remain non-negative?

The rephrased problem can be solved by greedily choosing reindeer with the smallest $D_i$ as long as the total strength $X^\prime$ remains non-negative. This follows from an exchange argument: if a chosen reindeer $i$ has a larger $D_i$ than an unchosen one, swapping them does not decrease the total strength $X^\prime$, so it is always optimal to choose reindeer with a smaller $D_i$ first.

Thus, the original problem can also be solved in $\mathcal{O}(N\log N)$ time by sorting reindeer in ascending order of $W_i+P_i$.

Implementation in Python

main.py

for _ in range(int(input())):
    N = int(input())
    X = 0
    D = []
    for _ in range(N):
        w, p = (int(x) for x in input().split())
        X += p
        D.append(w + p)
    D.sort()

    result = 0
    for d in D:
        if X - d >= 0:
            result += 1
            X -= d
        else:
            break
    print(result)

D - Sum of Differences

Problem. You are given sequences $A=(A_1, \dots, A_N)$ of $N\leq3\times10^5$ integers and $B=(B_1, \dots, B_M)$ of $M\leq3\times10^5$ integers. The integers are guaranteed to be between $1$ and $998244352$.

Evaluate $\displaystyle\sum_{i=1}^N\sum_{j=1}^M|A_i-B_j|$ and output its value modulo $998244353$.

Solution. We will fix $A_i$ and consider the quantity $\displaystyle\sum_{j=1}^M |A_i-B_j|$. Since $|A_i-B_j|$ equals $A_i-B_j$ if $A_i\gt B_j$ and otherwise equals $B_j-A_i$, we can partition $B_j$ into the two cases and evaluate their sum separately.

More precisely, let $X=\{B_j\ |\ A_i\gt B_j\}$ and $Y=\{B_j\ |\ A_i\leq B_j\}$. The sum of $A_i-B_j$ in the first case is

$$\sum_{B_j\in X}(A_i-B_j)=A_i\cdot |X| - \sum_{B_j\in X}B_j.$$

Similarly, the sum of $B_j-A_i$ in the second case becomes

$$\sum_{B_j\in Y}(B_j-A_i)=\sum_{B_j\in Y}B_j - A_i\cdot |Y|.$$

To solve the original problem, we need to compute this sum for all $A_i$. It is not efficient enough to directly calculate the sum of $B_j$ every time. Instead, we can sort $B_j$ in ascending order and precompute its prefix sum array, allowing us to use binary search and partition $B_j$ efficiently for all $A_i$. The time complexity of this solution is $\mathcal{O}((N+M)\log M)$.

A similar solution using the two-pointer technique is also possible with time complexity $\mathcal{O}(N\log N+M\log M)$.

Implementation in Python

main.py

import bisect

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

prefix_sum = [0] * (M + 1)
for i in range(M):
    prefix_sum[i + 1] = prefix_sum[i] + B[i]

result = 0
for a in A:
    k = bisect.bisect_right(B, a)
    result += a * k - prefix_sum[k]
    result += prefix_sum[-1] - prefix_sum[k] - a * (M - k)
    result %= MOD

print(result)

E - Sort Arrays

Problem. You are given a positive integer $N\leq3\times10^5$.

Define sequence $A_0$ as the empty sequence.

For $i\in\{1, \dots, N\}$, you are given two integers $0\leq x_i\lt i$ and $1\leq y_i\leq10^9$. Define $A_i$ as the sequence obtained by appending the integer $y_i$ to the end of sequence $A_{x_i}$.

Find the permutation $P=(P_1, \dots, P_N)$ of $(1, \dots, N)$ that minimizes the lexicographical order of $A_{P_1}, \dots, A_{P_N}$. More precisely, find the permutation $P$ that satisfies the following condition:

For all $i\in\{1, \dots, N-1\}$, $A_{P_i}$ is either lexicographically smaller than $A_{P_{i+1}}$, or $A_{P_i}=A_{P_{i+1}}$ and $P_i\lt P_{i+1}$.

Solution. A trie is a data structure commonly used to manage strings or sequences in lexicographical order. If we perform a DFS preorder traversal of a trie while visiting children in lexicographical order, the order of the visited sequences will also be in lexicographical order.

In the original problem, the sequences $A_i$ are defined as appending an integer $y_i$ to an existing sequence $A_{x_i}$, so we should add $A_i$ as a child of $A_{x_i}$ in the trie. By adding sequences in ascending order of $i$, we ensure that identical sequences will still follow the tie-breaking rule $P_i\lt P_{i+1}$. Since $y_i$ can be large, we should use a sorted dictionary to maintain the children of a trie node. The time complexity is $\mathcal{O}(N\log N)$.

Implementation in Python

main.py

N = int(input())
pos = [0] * (N + 1)
trie_indices = [[]]
trie_children = [{}]
for i in range(1, N + 1):
    x, y = (int(x) for x in input().split())
    if y not in trie_children[pos[x]]:
        trie_children[pos[x]][y] = len(trie_children)
        trie_indices.append([])
        trie_children.append({})
    pos[i] = trie_children[pos[x]][y]
    trie_indices[pos[i]].append(i)

stack = [0]
while stack:
    u = stack.pop()
    for i in trie_indices[u]:
        print(i)
    for _, v in sorted(trie_children[u].items(), reverse=True):
        stack.append(v)

F - Manhattan Christmas Tree 2

Problem. There are $N\leq2\times10^5$ Christmas trees on a two-dimensional plane $[-10^9, 10^9]^2$. The $i$-th tree is located at coordinates $(X_i, Y_i)$.

You are given $Q\leq2\times10^5$ queries. Process these queries in order. There are two types of queries:

1 i x y: Relocate the $i$-th tree to coordinates $(x, y)$.
2 L R x y: Output the maximum Manhattan distance between coordinates $(x, y)$ and one of the trees among the $L, L+1, \dots, R$-th Christmas trees.

Here, the Manhattan distance between two coordinates $(x, y)$ and $(z, w)$ is defined as $|x-z|+|y-w|$.

Solution. The most important problem is finding the maximum Manhattan distance between a point $p$ and a group of points. Since there can be multiple queries for different points $p$, it is not fast enough to directly compute the distance between every pair.

A useful technique is to rotate the points $45°$ about the origin. More precisely, the transformation involves redefining the two-dimensional planes in the coordinates of $u=x-y$ and $v=x+y$. (The transformation also scales the points by a factor of $\sqrt2$, but this does not affect the following discussion.)

Before rotation, the Manhattan distance between a point $p=(x, y)$ and the origin is $|x|+|y|$. After rotation, the coordinates of $p$ are $(x-y,x+y)$, and its Chebyshev distance from the origin becomes $\max(|x-y|, |x+y|)$. We can prove that $\max(|x-y|, |x+y|)=|x|+|y|$ via exhaustion on the signs of $x$ and $y$. Thus, the Manhattan distance before rotation is identical to the Chebyshev distance after rotation.

We can generalize this for any two points $p$ and $q$ on the plane. If the coordinates of $p$ and $q$ are $(s, t)$ and $(u, v)$ after rotation, their Chebyshev distance is equal to $\max(|s-u|, |t-v|)$.

Moreover, the maximum Chebyshev distance between $(s, t)$ and any point in a set $\{(u_1, v_1), \dots, (u_N, v_N)\}$ is $\max\{|s-u_i|, |t-v_i|\}$. Since $|s-u_i|$ is maximum if $u_i$ is minimum or maximum, we can also write $\max\{|s-u_i|\}=\max(s-\min u_i, \max u_i - s)$. Similarly, we obtain $\max\{|t-v_i|\}=\max(t-\min v_i, \max v_i - t)$. Thus, if we keep track of the minimum and maximum values of $u_i$ and $v_i$, we only need to compute $4$ values to solve for the maximum Manhattan distance for each query. This is much better than computing the distance between every pair in the naive approach!

Since the problem involves modifying elements and querying intervals, we can use a segment tree to manage the minimum and maximum coordinates of Christmas trees over an interval. The time complexity is $\mathcal{O}(N+Q\log N)$.

The maximum Manhattan distance can be as large as $4\times10^9$, so watch out for integer overflow.

Implementation in C++

main.cpp

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

using ll = long long;

struct node {
    ll umin = 1LL << 60;
    ll umax = -1LL << 60;
    ll vmin = 1LL << 60;
    ll vmax = -1LL << 60;
};

node op(node a, node b) {
    return {
        std::min(a.umin, b.umin),
        std::max(a.umax, b.umax),
        std::min(a.vmin, b.vmin),
        std::max(a.vmax, b.vmax)
    };
}

node e() {
    return {};
}

int main() {
    int N, Q;
    std::cin >> N >> Q;
    std::vector<node> vec(N);
    for (int i = 0; i < N; i++) {
        int x, y;
        std::cin >> x >> y;
        vec[i] = {x - y, x - y, x + y, x + y};
    }
    atcoder::segtree<node, op, e> seg(vec);

    while (Q--) {
        int t;
        std::cin >> t;
        if (t == 1) {
            int i, x, y;
            std::cin >> i >> x >> y;
            i--;
            seg.set(i, {x - y, x - y, x + y, x + y});
        } else {
            int L, R, x, y;
            std::cin >> L >> R >> x >> y;
            L--;
            long long s = x - y, t = x + y;
            auto [umin, umax, vmin, vmax] = seg.prod(L, R);
            ll result = std::max({s - umin, umax - s, t - vmin, vmax - t});
            std::cout << result << std::endl;
        }
    }
}

Have a fun break!

It's the holiday season, but make sure to get enough rest before we meet again for future contests! Be it this year or next year, see you next time, and watch out for those nasty TLEs! ⏱️🚀