Buckle up, folks. It's time to review AtCoder Beginner Contest 413!
We will only highlight main ideas and present possible solutions using Python and pseudocode.
A - Content Too Large
If this is your first time with AtCoder, make sure to check out their official get-started page at https://atcoder.jp/contests/practice/?lang=en.
Problem. You are given a number $M$ and a sequence $A=(A_1, A_2, \dots, A_N)$ of $N$ numbers. Determine if the sum of these numbers is at most $M$.
Solution.
Implementation in Python
N, M = (int(x) for x in input().split())
total = sum(int(x) for x in input().split())
if total <= M:
print("Yes")
else:
print("No")
B - cat 2
Problem. You are given a collection $S=(S_1, S_2, \dots, S_N)$ of $N$ distinct strings. By choosing two distinct strings from $S$ and concatenating them, how many unique strings can you make?
Solution. Python's set data type is a perfect choice for counting unique elements. Also, make sure not to accidentally choose the same string from $S$ in your code!
Implementation in Python
N = int(input())
S = [input() for _ in range(N)]
new_strings = {S[i] + S[j] for i in range(N) for j in range(N) if i != j}
print(len(new_strings))
C - Large Queue
Problem. You are given an empty integer sequence $A$ and must process $Q\leq2\times10^5$ queries in order. There are two types of queries:
-
1 c x: Add $c\leq10^9$ copies of integer $x\leq10^9$ to the end of $A$; or -
2 k: Remove the first $k$ integers from $A$ and output their sum. (It is guaranteed that the size of $A$ is at least $k$)
Solution. Since the sequence can contain up to $2\times10^5\times10^9=2\times10^{14}$ items, storing them directly is inefficient and will result in TLE.
Instead, we can store information from the queries as pairs $(c, x)$ to avoid repeated computation. To remove the first $k$ elements, we should repeatedly retrieve the first pairs from the list and decrement $k$ accordingly until $k$ reaches $0$. If the current pair contains more elements than needed, we use only the required portion and push the remaining part back to the front of the queue.
Since we will frequently add and remove items to both ends of the list, a double-ended queue like Python's collections.deque will serve exactly what we need.
Implementation in Python
from collections import deque
A = deque()
for _ in range(int(input())):
query = [int(x) for x in input().split()]
if query[0] == 1:
A.append((query[1], query[2]))
else:
k = query[1]
total = 0
while k:
c, x = A.popleft()
if c <= k:
k -= c
total += c * x
else:
total += k * x
A.appendleft((c - k, x))
break
print(total)
D - Make Geometric Sequence
Problem. You are given $T\leq10^5$ test cases. In each test case, you are given a sequence $A = (A_1, A_2, \dots, A_N)$ of $N\geq2$ non-zero integers. Is it possible to rearrange $A$ into a geometric sequence?
The total length of sequences in all test cases is at most $2\times10^5$.
A sequence $S=(S_1, S_2, \dots, S_N)$ is a geometric sequence if there exists a common ratio $r$ such that $S_{i+1} = r\cdot S_i$ for $i\in\{1, 2, \dots, N - 1\}$.
Sequences of length $2$ qualify as a geometric sequence.
Solution. If sequence $A$ contains only positive values or only negative values, the possible common ratio $r$ must be positive. We can determine if $r$ exists by sorting $A$ and compare adjacent pairs of integers using the fact that $S_i\cdot S_{i+2}=(S_{i+1})^2$ for $i\in\{1, 2, \dots, N - 2\}$ in a geometric sequence $S$ of $N$ elements.
On the other hand, if $A$ contains both positive and negative values, the possible $r$ must be negative. Consequently, numbers in a suitable rearrangement must alternate between positive and negative values. Let $n$ be the number of negative numbers in $A$. Since the difference of the number of positive values and negative values must not exceed $1$, we obtain $|n-(N-n)|=|2n-N|\leq1$. If $n$ satisfies this inequality, we can sort the numbers in $A$ using their absolute values and compare neighbors with $S_i\cdot S_{i+2}=(S_{i+1})^2$.
However, if $r=-1$, the sequence will not sort into the correct order. To fix this, we need a separate check on whether every number in $A$ has the same absolute value.
The time complexity for each test case is $\mathcal O(N\log N)$.
Implementation in Python
for _ in range(int(input())):
N = int(input())
A = [int(x) for x in input().split()]
num_negative = sum(1 for x in A if x < 0)
if 0 < num_negative < N and abs(num_negative * 2 - N) > 1:
print("No")
continue
if all(abs(x) == abs(A[0]) for x in A):
print("Yes")
continue
A.sort(key=abs)
if all(A[i] * A[i + 2] == A[i+1] ** 2 for i in range(N - 2)):
print("Yes")
else:
print("No")
A note on non-integer computations
If your solution compares neighbors using $\displaystyle\frac{S_{i+1}}{S_i}=\frac{S_{i+2}}{S_{i+1}}$, it might output "No" on some geometric sequences. This is because computers use floating-point numbers to estimate non-integers. In general, unless the problem asks for decimal outputs, you should always use integers for arithmetic.E - Reverse 2^i
Problem. You are given $T\leq10^5$ test cases. In each test case, you are given a positive integer $N$ and a permutation $P = (P_0, P_1, \dots, P_{2^N-1})$ rearranged from the numbers $(1, 2, \dots, 2^N)$. You can perform the following operation as many times as you like:
- Choose an integer $0\leq n<N$ and divide $P$ into $2^n$ contiguous sections, each of size $2^{N-n}$. Choose one section and reverse it.
For example, if $P=(3, 4, 5, 6, 7, 8, 1, 2)$, choosing $n=1$ and reversing the second section yields $(3, 4, 5, 6, 2, 1, 8, 7)$.
What is the lexicographically smallest permutation you can obtain from repeating the above operation?
The total length of permutations in all test cases is at most $3\times10^5$.
Solution. We claim that if $P^\prime$ is the lexicographically smallest permutation of $P$, then $P_0^\prime$ is the smallest element of $P$.
Proof
For $n\in(0, 1, \dots, N - 1)$, choose the first section and reverse it if the smallest element of the section is in the second half. This guarantees the smallest element is always in the first half and can be "moved" towards the head of the sequence. Since there are no smaller elements, $P_0^\prime$ must be the smallest element of $P$.This claim allows us to devise a divide-and-conquer approach. In the base case, a permutation of size $1$ is indeed the lexicographically smallest. In a subproblem for a permutation of size $2^M$, we can reverse the entire permutation if its smallest element is in the second half, before solving each half as a subproblem of size $2^{M-1}$. If both halves are the lexicographically smallest after solving, so is the original permutation of size $2^M$.
The overall time complexity of this approach is $\Theta(N2^N)$ for each test case.
Pseudocode
input integer T
define solve(P, left, right):
if the size of P[left:right] is at most 1:
return
if the smallest element of P[left:right] is in the second half:
reverse P[left:right]
let mid = (left + right) / 2
solve(P, left, mid)
solve(P, mid, right)
do T times:
input integer N
input list P of size 2^N
solve(P, 0, 2^N)
output P
F - No Passage
Problem. Takahashi and Aoki are playing on a grid of size $H\times W$ for some integers $2\leq H, W\leq3000$. Takahashi starts on a cell and wins by reaching one of the $K\leq3000$ goal cells in the grid. Aoki tries to prevent Takahashi from winning. They play in turns until Takahashi reaches a goal cell.
- Aoki first chooses one of Takahashi's neighboring cells and blocks it;
- Takahashi then chooses an available neighboring cell in the grid and moves there.
Two cells $(z, w)$ and $(z^\prime, w^\prime)$ are neighbors if $|z - z^\prime| + |w - w^\prime| = 1$.
For each cell $(x, y)$ in the grid, if Takahashi starts on $(x, y)$, what is the minimum number of moves he must make before winning, if he can win at all? Find the sum of moves of all winnable starting cells.
Solution. The following solution is based on kyopro_friends's editorial in Japanese.
Since Aoki can always block one neighbor per turn, a cell $(x, y)$ is winnable if and only if
- it is a goal cell, or
- at least two neighboring cells are also winning.
Thus, we can use BFS to look for winnable cells and record their respective minimum number of moves. Since at least two neighbors have to be winnable, we will record the number of times a cell is visited and qualify it as winnable only if it is visited twice. The time complexity of this algorithm is $\mathcal O(HW)$.
Pseudocode
input integers H, W, K
input goals as a list of K cells
let dist and num_visits be 2D lists of size H * W, initially containing 0s
let q be a queue of pairs (distance, cells)
for cell (x, y) in goals:
set num_visits[x][y] = 2
push (0, (x, y)) to q
while q is not empty:
let (d, (x, y)) = head of q
pop q
for each neighbor (z, w) of (x, y):
increment num_visits[z][w] by 1
if num_visits[z][w] == 2:
set dist[z][w] = dist[x][y] + 1
push (d + 1, (z, w)) to q
output sum of elements in dist
G - Big Banned Grid
Problem. Takahashi is in a grid of size $H\times W$ for some integers $1\leq H, W\leq 2\times10^5$. Let $(x, y)$ denote the cell at the $x$-th row from the top and $y$-th column from the left. Among the cells, $K\leq2\times10^5$ are blocked off. Determine if Takahashi can start on $(1, 1)$ and reach $(H, W)$ by repeatedly moving between available neighbors.
Solution. An ordinary traversal algorithm takes $\mathcal O(HW)$ time and is insufficient under the given constraints. We instead take advantage of the fact that there are at most $2\times10^5$ blocked cells.
To prevent Takahashi from finding a path between $(1, 1)$ and $(N, N)$, the blocked cells must form an 8-connected path between any cell on the left or bottom border and any cell on the right or top border. Sample input 1 from the original problem is an example of blocked cells connecting the bottom and top borders.
By choosing an appropriate container to record blocked cells, we can determine their connectivity in $\mathcal O(K)$ time and solve the original problem.
Pseudocode
input integers H, W, K
input blocked_cells as a set of K cells
let q be a queue of cells
for cell (x, y) in blocked_cells:
if x == H or y == 1:
push (x, y) to q
let visited_cells be an empty set
while q is not empty:
let (x, y) = head of q
pop q
if x == 1 or y == W:
output "No"
halt program
if visited_cells contain (x, y):
continue
add (x, y) to visited_cells
for each 8-neighbor (z, w) of (x, y):
if blocked_cells contain (z, w):
push (z, w) to q
output "Yes"
That is all for this week!
Have a nice day and stay alert to TLEs! ⏱️🚀