Happy New Year! After a well-deserved break, we are excited to be back and ready to take on a challenging contest. This week, we will review AtCoder Beginner Contest 439.
In this series, we explore programming problems from AtCoder’s weekly contests and break down complex concepts into simple solutions!
A - 2^n - 2*n
If you are new to AtCoder, check out the official getting-started page!
Problem. You are given a positive integer $N$ between $1$ and $11$. Find the value of $2^N-2N$.
Solution. We can use loops or other built-in functions for computing exponents. Most languages also support bit shifts, giving us a concise way to write $2^N$ as 1 << N. Since the order of operations for bitwise operations is not the same as arithmetic operations, remember to surround bitwise operations with parentheses to avoid incorrect results.
Implementation in Python
N = int(input())
print((1 << N) - N * 2)
B - Happy Number
Problem. Given a positive integer $M$, let $f(M)$ be the sum of squares of digits in $M$.
- For example, $f(2026)=2^2+0^2+2^2+6^2=44$.
A number $M$ is said to be a happy number if it can become $1$ by repeatedly replacing $M$ with $f(M)$ a finite number of times.
You are given an integer $1\leq N\leq2026$. Determine if $N$ is a happy number.
Solution. We can simulate the process by replacing $N$ with $f(N)$ until it becomes $1$. However, there may also exist values of $N$ that never reach $1$. For example, $37$ is not a happy number because it can only reach values in the cycle
$$37\rightarrow58\rightarrow89\rightarrow145\rightarrow42\rightarrow20\rightarrow4\rightarrow16\rightarrow37\rightarrow\cdots$$
If $N$ reaches the same number twice, it will stay in the cycle and never become $1$, so we can terminate the program immediately.
We should also prove that our solution always terminates after visiting a finite number of values. Under the problem constraints, $N$ has at most $4$ digits, so $f(N)$ is at most $4\times9^2=324$, containing at most $3$ digits. From here, applying $f$ always yields a value with at most $3$ digits. Since there is only a finite number of integers with $3$ digits, our program also halts after a finite number of steps by the pigeonhole principle.
Implementation in Python
N = int(input())
visited = set()
while N not in visited:
if N == 1:
print("Yes")
exit()
visited.add(N)
N = sum(int(c) ** 2 for c in str(N))
print("No")
C - 2026
Problem. Say a positive integer $M$ is a good integer if it satisfies the following condition:
- There exists a unique pair of positive integers $x\lt y$ such that $x^2+y^2=M$.
You are given a positive integer $N\leq10^7$. Output the number of good integers at most $N$ and print them in ascending order.
Solution. Since $x$ and $y$ are positive integers, we obtain $y^2\lt N$, so there can only be at most $\sqrt{N}$ possible values of $y$ contributing to some good integers. Since $x\lt y$, the number of possible values of $x$ is also at most $\sqrt{N}$. As there are at most $\sqrt{N}\cdot\sqrt{N}=N$ possible pairs, we can search every candidate in $\mathcal{O}(N)$ time.
Implementation in Python
N = int(input())
count = [0] * (N + 1)
for y in range(1, N + 1):
if y * y > N:
break
for x in range(1, y):
if x * x + y * y > N:
break
count[x * x + y * y] += 1
result = [i for i in range(N + 1) if count[i] == 1]
print(len(result))
print(*result)
D - Kadomatsu Subsequence
Problem. You are given a sequence $A=(A_1, \dots, A_N)$ of $N\leq3\times10^5$ positive integers at most $10^9$.
Find the number of triples of integers $(i, j, k)$ such that:
- $1\leq i, j, k\leq N$,
- $A_i:A_j:A_k=7:5:3$, and
- $\min(i, j, k)=j$ or $\max(i, j, k)=j$.
Solution. Since elements in $A$ are positive, we know that $i, j, k$ must be distinct to meet the second condition. Moreover, the third condition requires that $j$ is either the minimum or the maximum of the three values.
We will fix $j$ and consider the case where $j$ is the maximum. Let $c(x)$ be the number of times the value $x$ appears before index $j$. The number of satisfying triples becomes
$$c\left(\frac{7A_j}5\right)\cdot c\left(\frac{3A_j}5\right).$$
Thus, by maintaining a counter for $c$ and iterating through the elements of $A$, we can find the total number of satisfying triples where $j$ is greater than $i$ and $k$. We can use the same logic to find the number of triples where $j$ is minimum.
By using an appropriate data structure for maintaining counters, we can solve the problem in $\Theta(N)$ or $\Theta(N\log N)$ time.
Implementation in Python
from collections import Counter
N = int(input())
A = [int(x) for x in input().split()]
count_l = Counter()
count_r = Counter(A)
result = 0
for a in A:
count_l[a] += 1
count_r[a] -= 1
if a % 5 != 0:
continue
result += count_l[a // 5 * 3] * count_l[a // 5 * 7]
result += count_r[a // 5 * 3] * count_r[a // 5 * 7]
print(result)
E - Kite
Problem. $N\leq2\times10^5$ people are trying to fly kites on a two-dimensional plane.
Person $i$ is standing at coordinates $(A_i, 0)$, and they want to fly a kite at coordinates $(B_i, 1)$.
To avoid collisions, person $i$ and person $j$ cannot fly kites together if the line segment connecting $(A_i, 0)$ and $(B_i, 1)$ intersects with the line segment containing $(A_j, 0)$ and $(B_j, 1)$. The line segments are considered intersecting if $A_i=A_j$ or $B_i=B_j$.
Find the maximum number of people who can fly kites together.
Solution. Without loss of generality, we will sort the $N$ people in ascending order of $A_i$. For simplicity, also suppose $A_i$ are distinct.
We can define $f_i$ as the maximum number of people flying a kite where person $i$ has the largest value of $A_i$. Since the kite at $(B_i, 1)$ must be included, we can use dynamic programming to look for the maximum number of kites appearing before $(B_i, 1)$. In fact, this approach reduces to finding the longest increasing subsequence (LIS) of the sequence $B$. There is a simple method that finds the length of LIS in $\mathcal{O}(N\log N)$ time, which is sufficient to find the maximum number of people in the original problem.
Now suppose two people $i$ and $j$ share the same coordinates at $A_i=A_j$. Since only one person can fly a kite, we should process their kites in descending order of $B$ to avoid counting kites flown by people at the same coordinates. Thus, our solution works regardless of repeated coordinates.
Implementation in Python
import bisect
N = int(input())
kites = []
for _ in range(N):
a, b = (int(x) for x in input().split())
kites.append((a, -b))
kites.sort()
lis_dp = []
for _, b in kites:
b = -b
i = bisect.bisect_left(lis_dp, b)
if i == len(lis_dp):
lis_dp.append(b)
else:
lis_dp[i] = b
print(len(lis_dp))
F - Beautiful Kadomatsu
Problem. Given a sequence $A=(A_1, \dots, A_k)$ of length $k$, let $x$ be the number of indices $1\lt i\lt k$ for which $A_{i-1}\lt A_i$ and $A_i\gt A_{i+1}$, and let $y$ be the number of indices $1\lt i\lt k$ for which $A_{i-1}\gt A_i$ and $A_i\lt A_{i+1}$. The sequence $A$ is said to be kadomatsu-like if $x\gt y$.
You are given a permutation $P=(P_1, \dots, P_N)$ of $(1, \dots, N)$ where $N\leq3\times10^5$. Find the number, modulo $998244353$, of subsequences of $P$ that are kadomatsu-like.
Solution. Given a sequence $A$, we will call index $i$ a "hill" if $A_{i-1}\lt A_i$ and $A_i\gt A_{i+1}$, and a "valley" if $A_{i-1}\gt A_i$ and $A_i\lt A_{i+1}$. Moreover, we will also say $i$ is a "key index" if it is either a hill or a valley. We make the following observations:
- The difference between the number of hills and valleys is at most $1$.
- The first key index of a kadomatsu-like sequence is a hill.
- The last key index of a kadomatsu-like sequence is a hill.
Observation 1 follows from the fact that every sequence has to alternate between hills and valleys. Since the difference is at most $1$, the number of hills in a kadomatsu-like sequence must be one more than the number of valleys. To fit more hills than valleys into a kadomatsu-like sequence, the first and last key indices must therefore be hills. Conversely, if the first and last key indices of a sequence are hills, it must be a kadomatsu-like sequence. Thus, it suffices to count the number of subsequences of $P$ whose first and last key indices are hills.
There are many possible ways to count such subsequences. The official editorial (in Japanese) makes a further simplifying claim that a sequence $A$ containing $k$ distinct integers is kadomatsu-like if and only if $A_1\lt A_2$ and $A_{k-1}\gt A_k$. This is consistent with the earlier observations that a kadomatsu-like sequence must begin and end with hills.
Therefore, by maintaining a prefix sum of the number of possible combinations of subsequences beginning with $(A_1, A_2)$, we can iterate through the possible values of $(A_{k-1}, A_k)$ to compute the total number of kadomatsu-like subsequences. Remember to also account for length-$3$ subsequences containing exactly one hill.
The implementation below uses Fenwick trees to efficiently compute the number of elements less than $A_2$ and $A_{k-1}$, giving a solution that runs in $\Theta(N\log N)$ time. The AtCoder Library also offers a C++ implementation of Fenwick trees.
Implementation in Python
MOD = 998244353
class FenwickTree:
... # omitted for brevity
N = int(input())
P = [int(x) - 1 for x in input().split()]
result = 0
prefix_sum = 0
count_left = FenwickTree(N)
count_right = FenwickTree(N)
for i in range(N):
count_right.add(i, 1)
for p in P:
cl = count_left.sum(0, p)
cr = count_right.sum(0, p)
result += cl * cr # length 3 subsequences
result += prefix_sum * cr # length 4+ subsequences
result %= MOD
prefix_sum *= 2 # subsequences where p is in the middle
prefix_sum += cl # subsequences where p is the second element
prefix_sum %= MOD
count_left.add(p, 1)
count_right.add(p, -1)
print(result)
Be ready for a whole new year!
Now that we've enjoyed our break, we are ready again for even more challenges. See you around next time, and watch out for those nasty TLEs! ⏱️🚀