It's time for our weekly review of AtCoder Beginner Contest 415!

We will highlight the main ideas and present possible solutions using (mostly) Python and pseudocode.

A - Unsupported Type

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

Problem. You are given a sequence $A=(A_1, A_2, \dots, A_N)$ of $N$ numbers. Determine if $A$ contains the number $X$.

Solution.

Implementation in Python

main.py

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

B - Pick Two

Problem. You are given a string $S$ consisting of hashes (#) and dots (.) only. The number of hashes is positive and even. Repeat the following operation until $S$ no longer contains any hashes:

Find the two leftmost hashes in $S$ and output their indices separated by a comma. Replace the two hashes with dots.

Solution.

Implementation in Python

main.py

S = input()
flag = True
for i in range(len(S)):
    if S[i] == '#':
        print(i + 1, end="")
        if flag:
            print(',', end="")
        else:
            print()
        flag = not flag

C - Mixture

Problem. A scientist wants to combine chemicals into a mixture. There are $N\leq18$ types of chemicals labelled $1$ to $N$. The scientist labels every possible mixture with a corresponding number $i$ using the following rule:

Mixture $i$ contains chemical $k$ if the $k$-th least significant bit of $i$ in binary is $1$.

For example, $13$ in binary is $1101_2$, so mixture $13$ contains only chemicals $1$, $3$ and $4$.

The scientist starts with an empty container and adds chemicals one by one. However, certain mixtures are dangerous and should be avoided. Specifically, given a binary string $S$ of length $2^N-1$, mixture $i$ is safe only when the $i$-th character of $S$ is 0.

You are given $T$ test cases. In each test case, determine if the scientist can safely combine every chemical. The total length of $S$ in all test cases is at most $5\times10^5$.

Solution. We rephrase the original problem as the following graph problem:

Determine if there exists a sequence $(i_0, i_1, i_2, \dots, i_N)$ where
- Mixture $i_j$ is safe and contains exactly $j$ chemicals; and
- for $j\in\{0, 1, \dots, N - 1\}$, mixture $i_{j+1}$ can be obtained by adding exactly one chemical to mixture $i_j$.

We can construct a graph and run traversal algorithms (such as BFS) to solve the rephrased problem. In this case, since the labels are given to us in binary, we can leverage the power of bit manipulation to write efficient solutions.

Bit manipulation quick reference

The following statements use 0-indexing.

1 << N computes $2^N$. In binary, this is 1 followed by $N$ 0's.
i >> k & 1 is equal to the $k$-th least significant bit of $i$.
i | 1 << k computes $i$ with its $k$-th least significant bit set to $1$.
Bitwise operations and arithmetic operations (such as + and *) have different order of operations. If you are unsure, always use parentheses () to avoid confusion!

Implementation in Python

main.py

for _ in range(int(input())):
    N = int(input())
    S = input()
    reachable = [False for _ in range(1 << N)]
    reachable[0] = True
    for i in range(1 << N):
        if not reachable[i]:                   # There is no safe way to obtain mixture i
            continue
        for k in range(N):
            if i >> k & 1:                     # Mixture i already contains chemical k
                continue
            if S[(i | 1 << k) - 1] == '0':     # The new mixture is safe
                reachable[i | 1 << k] = True
    if reachable[-1]:
        print("Yes")
    else:
        print("No")

D - Get Many Stickers

Problem. A mysterious cola shop lets its customers exchange empty bottles for new bottled cola. There are $M\leq2\times10^5$ ways a customer can exchange bottles:

The customer chooses $i\in\{1, 2, \dots, M\}$ and gives $A_i$ bottles to the shop;
The shop then provides $B_i$ new bottles of cola and a commemorative sticker in return.
For all $i$, $1\leq B_i\lt A_i\leq10^{18}$.

Takahashi initially has $N\leq10^{18}$ bottles of cola. By drinking cola and repeatedly exchanging bottles with the shop, what is the maximum number of stickers he can receive?

Solution. To maximize the number of stickers, Takahashi should try to keep as many bottles as possible after each exchange. Since each exchange decrements the number of bottles by $A_i-B_i$, a greedy approach is to always choose $i$ that minimizes $A_i-B_i$ as long as Takahashi has at least $A_i$ bottles remaining.

To process the $M$ exchange methods effectively, we should traverse every value of $i$ in ascending order of $A_i-B_i$, each time exchanging as many bottles as possible as long as at least $A_i$ bottles remain. In particular, if Takahashi has $n\geq A_i$ bottles, he can exchange up to $\displaystyle \Bigl\lfloor\frac{n-A_i}{A_i-B_i}\Bigr\rfloor+1$ times before moving to the next value of $i$.

This approach results in a time complexity of $\mathcal{O}(M\log M)$.

Implementation in Python

main.py

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

offers = []
for i in range(M):
    A, B = (int(x) for x in input().split())
    offers.append((A - B, A))
offers.sort()

num_stickers = 0
for diff, A in offers:
    if N < A:
        continue
    num_exchanged = (N - A) // diff + 1
    num_stickers += num_exchanged
    N -= num_exchanged * diff

print(num_stickers)

E - Hungry Takahashi

Problem. Takahashi lives in a grid of size $H\times W\leq2\times10^5$. Let $(i, j)$ denote the cell at the $i$-th row from the top and $j$-th column from the left. Initially, $A_{i,j}\leq10^9$ coins are placed on cell $(i, j)$.

Takahashi brings $x\geq0$ coins and starts on cell $(1, 1)$, planning to reach cell $(H, W)$ over the next $H+W-1$ days. On day $k\in\{1, 2, \dots, H+W-1\}$, the following events happen in order:

Takahashi collects every coin placed on his current cell.
Takahashi pays $P_k\leq 10^9$ coins for food. If he has fewer than $P_k$ coins, he collapses from hunger.
If $k\lt H+W-1$, Takahashi moves either one cell right or one cell down while staying in the grid.

What is the minimum number of coins $x$ Takahashi must bring to avoid collapsing from hunger?

Solution. Since Takahashi always moves towards $(H, W)$, cell $(i, j)$ is only reachable on day $i+j-1$. We can use BFS or dynamic programming to determine whether Takahashi can reach $(H, W)$ with $x$ initial coins in $\mathcal{O}(HW)$ time.

From here, we can perform a binary search to determine the minimum value of $x$ that prevents Takahashi from collapsing. As Takahashi can lose up to $\max P$ coins for food each day, the minimum value of $x$ is at most $(H+W-1)\max P$.

Thus, we can determine the minimum value of $x$ in $\Theta(HW(\log(H+W)+\log\max P))$ time.

Binary search template

The following algorithm outputs two values $(\ell, h)$. Here, $h$ is the minimum value satisfying the predicate, whereas $\ell$ gives the maximum value not satisfying the predicate.

input integers low, high
input predicate p
require there exists low < x <= high such that p(y) is true iff y >= x

while low + 1 < high:
    let mid = floor((low + high) / 2)
    if p(mid) is true:
        set high = mid
    else:
        set low = mid

output low, high

Pseudocode

input integers H, W
input integers A[i][j]
input integers P[k]

let low = -1
let high = (H + W - 1) * max(P[k])
run binary search to find minimum x in (low, high] satisfying the following DP:
    let budget be a 2D array of size H * W, initialized with -1
    set budget[1][1] = x + A[1][1] - P[1]
    for i = 1, ..., H:
        for j = 1, ..., W:
            if budget[i][j] < 0:
                continue
            if i < H:
                set budget[i+1][j] = max{budget[i+1][j], budget[i][j] + A[i+1][j] - P[i+j]}
            if j < W:
                set budget[i][j+1] = max{budget[i][j+1], budget[i][j] + A[i][j+1] - P[i+j]}
    if budget[H][W] >= 0:
        accept
    else:
        reject

output x

F - Max Combo

Problem. You are given a string $S$ consisting of $N\leq5\times10^5$ characters. You must process $Q\leq5\times10^5$ queries in order. There are two types of queries:

1 i x: Change the $i$-th character of $S$ to x; or
2 l r: Output the length of the longest substring between the indices $\ell$ and $r$ consisting of identical characters.

Solution. The following solution is based on rsk0315's editorial in Japanese and uses 0-indexing.

We can encode $S$ as an integer sequence $A$ of length $2N-1$. For $i\in\{0, 1, \dots, N-1\}$, $A_{2i}=1$ represents the length of the individual letter $S_i$. For $i\in\{1, \dots, N-1\}$, $A_{2i-1}$ represents the border between $S_{i-1}$ and $S_i$. If $S_{i-1}=S_i$, then $A_{2i-1}=0$; otherwise, $A_{2i-1}=-\infty$.

For example, if $S$ is abbcccb, its encoding is

$$A=(1, -\infty, 1, 0, 1, -\infty, 1, 0, 1, 0, 1, -\infty, 1).$$

Here, the length of the longest substring with identical characters would be $3$, corresponding to ccc in $S$ and the sum of the contiguous subsequence $(1, 0, 1, 0, 1)$.

In general, the length of the longest substring between $\ell$ and $r$ corresponds to the maximum sum of $A$ in the subinterval $[2\ell, 2r]$. We now outline a method using segment tree to efficiently update values in $A$ and compute maximum sums of subintervals.

Each node in our segment tree represents a subinterval $[\ell, r]$ of $A$ and has four attributes:

sum: the sum of elements in the interval;
max_prefix: the maximum sum of subintervals $[\ell, v]$ for $\ell\leq v\leq r$;
max_suffix: the maximum sum of subintervals $[u, r]$ for $\ell\leq u\leq r$;
max_infix: the maximum sum of subintervals $[u, v]$ for $\ell\leq u\leq v\leq r$.

Each internal node has two nodes, left and right. The attributes of the internal node can be computed using:

sum = left.sum + right.sum is the sum of all elements in the interval;
max_prefix = max(left.max_prefix, left.sum + right.max_prefix) for subintervals starting from the left node's lower bound;
max_suffix = max(right.max_suffix, right.sum + left.max_suffix) for subintervals ending on the right node's upper bound;
max_infix = max(left.max_infix, right.max_infix, left.max_suffix + right.max_prefix) comes from either one of the children's subintervals or a combination of the two.

Other details about the segment tree

The identity node should have its attributes set to $0$.
- For general problems about the maximum sums of subintervals, if empty intervals are not allowed, only sum should be set to $0$ and all other attributes to $-\infty$.
Every attribute of a leaf node representing $[i, i]$ should be set to $A_i$.
Whenever a character in $S$ is updated, compare it with its neighbors and update relevant values in $A$ to $0$ or $-\infty$ accordingly.

When implemented properly, the original problem can be solved in $\mathcal{O}(N+Q\log N)$ time.

The AtCoder Library has a segtree header and is available in every AtCoder contest. See the documentation here.

Implementation in C++

main.cpp

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

struct node {
    int64_t sum, max_prefix, max_suffix, max_infix;
    node(int64_t s, int64_t pre, int64_t suf, int64_t inf)
        : sum(s),
          max_prefix(pre),
          max_suffix(suf),
          max_infix(inf) {}
    node(int64_t val) {
        sum = max_prefix = max_suffix = max_infix = val;
    }
};

node op (node a, node b) {
    return node{
        a.sum + b.sum,
        std::max(a.max_prefix, a.sum + b.max_prefix),
        std::max(b.max_suffix, b.sum + a.max_suffix),
        std::max(a.max_suffix + b.max_prefix, std::max(a.max_infix, b.max_infix))
    };
}

node e() {
    return node{0};
}

constexpr int64_t MIN = -1000000;

int main() {
    int N, Q;
    std::string S;
    std::cin >> N >> Q >> S;
    atcoder::segtree<node, op, e> seg(N * 2 - 1);
    for (int i = 0; i < N; i++) {
        seg.set(i * 2, node{1});
        if (i < N - 1) {
            if (S[i] == S[i + 1]) seg.set(i * 2 + 1, node{0});
            else seg.set(i * 2 + 1, node{MIN});
        }
    }
    while (Q--) {
        int t;
        std::cin >> t;
        if (t == 1) {
            int i;
            char x;
            std::cin >> i >> x;
            i--;
            S[i] = x;
            if (i > 0) {
                if (S[i - 1] == S[i]) seg.set(i * 2 - 1, node{0});
                else seg.set(i * 2 - 1, node{MIN});
            }
            if (i < N - 1) {
                if (S[i] == S[i + 1]) seg.set(i * 2 + 1, node{0});
                else seg.set(i * 2 + 1, node{MIN});
            }
        } else {
            int l, r;
            std::cin >> l >> r;
            std::cout << seg.prod(l * 2 - 2, r * 2 - 1).max_infix << std::endl;
        }
    }
}

Related problems

That wraps up this week’s review!

Thanks for making it this far with me. Have a nice day and stay alert to TLEs! ⏱️🚀