AtCoder Beginner Contest 457

Introduction

The Polaris.AI Programming Contest 2026 (AtCoder Beginner Contest 457) concluded this past Saturday. After taking a virtual contest, I find the problems very cute and interesting. For problems A, B, C, D, and E, I was comfortable with the ideas and solved the problems fairly quickly. Problems F and G were harder but contain some nice ideas. Here I will share some of my thought processes.

By the way, as part of my journey of learning new programming languages, I write all my code in Kotlin. I am also working on a snippet collection for competitive programming in Kotlin as I go.

A. Array

Problem. Given an array $𝐴$ of length $𝑁$ and integer $𝑋$, find ${𝐴}_{𝑋}$.

Analysis. Ask a toddler on the street.

B. Arrays

Problem. Given an array $𝐴$ consisting of $𝑁$ arrays and two integers $𝑋$ and $𝑌$, output ${𝐴}_{𝑋,𝑌}$.

Analysis. Ask a Chinese kindergarten student.

C. Long Sequence

Problem. You are given an array $𝐴$ consisting of $𝑁$ arrays, an integer array $𝐶$ of length $𝑁$, and an integer $𝐾$. If $𝐵$ is the array constructed by joining ${𝐶}_{𝑖}$ copies of ${𝐴}_{𝑖}$ for each $𝑖=1,2,\dots ,𝑁$ in this order, find ${𝐵}_{𝐾}$.

Constraints. ${\sum }_{𝑖=1}^{𝑁}\left|{𝐴}_{𝑖}\right|\le 2\times {10}^5$, $1\le {𝐴}_{𝑖,𝑗}\le {10}^9$, $1\le {𝐶}_{𝑖}\le {10}^9$.

Analysis. Simulating can take over ${10}^{14}$ steps, which is not feasible. However, we only need to find a single element, so we can use modular arithmetic to skip over almost all of the copies. Let us first find out which array contains the answer; then, we can figure out where in that array the answer lies using the remainder. For some $𝑚$, define

as the number of elements remaining after skipping over ${𝐴}_1,\dots ,{𝐴}_{𝑚}$. There must exist a unique $𝑚$ such that

so the answer will be an element of ${𝐴}_{𝑚+1}$. To find which one it is, we can take $𝑖={𝑅}_{𝑚}mod|{𝐴}_{𝑚+1}|$, and ${𝐴}_{𝑚+1,𝑖}$ is our answer.

D. Raise Minimum

Problem. You are given an array $𝐴$ of length $𝑁$ and an integer $𝐾$. In one operation, you can choose some $1\le 𝑖\le 𝑁$ and set ${𝐴}_{𝑖}≔{𝐴}_{𝑖}+𝑖$. After at most $𝐾$ operations, what is the maximum possible value of ${min}_{1\le 𝑖\le 𝑁}{𝐴}_{𝑖}$?

Constraints. $1\le 𝑁\le 2\times {10}^5$, $1\le {𝐴}_{𝑖}\le {10}^{18}$, $1\le 𝐾\le {10}^{18}$.

Analysis. This problem immediately reminded me of the example problem about maximum median from the binary search section on USACO Guide. The core idea in that problem was to binary search on the answer, and then count how many operations we need. The same technique applies to this problem. Suppose we fix some $𝐿$. Then, for each $𝑖$, we need

operations to raise ${𝐴}_{𝑖}$ to at least $𝐿$ (which should hold for all $𝑖$). Therefore, the minimum number of operations needed is ${\sum }_{𝑖=1}^{𝑁}{𝐶}_{𝑖}$, and the answer is at least $𝐿$ if and only if this sum is at most $𝐾$.

Increasing the minimum can only require more operations, so this subproblem is monotonic in $𝐿$. Hence, we binary search on $𝐿$ to find the answer.

My code:

val n = nextInt()
val k = nextLong()
val a = LongArray(n) { nextLong() }
var lo = 0L
var hi = Long.MAX_VALUE - 1
while (lo < hi) {
    // thanks 15-122
    val mid = lo + (hi - lo + 1) / 2
    var cost = 0L
    for (i in 0 until n) {
        val diff = mid - a[i]
        if (diff <= 0) continue
        cost += (diff + i) / (i + 1)
        if (cost > k) break
    }
    if (cost > k) hi = mid - 1
    else lo = mid
}
println(lo)

E. Crossing Table Cloth

Problem. You are given $𝑀$ segments on the cells $1,2,\dots ,𝑁$. For each of the $𝑄$ queries, given integers $𝑆\le 𝑇$, determine whether or not there exist exactly two segments such that their union is exactly $\left[𝑆,𝑇\right]$.

Constraints. $1\le 𝑁\le 2\times {10}^5$, $2\le 𝑀\le 2\times {10}^5$, $1\le 𝑄\le 2\times {10}^5$.

Analysis. I immediately noticed that for the answer to be “Yes,” one of the two segments must have an endpoint at $𝑆$ and extends rightwards, and one of the two segments must have an endpoint at $𝑇$ and extends leftwards. To maximize the coverage greedily, we should make the former extend as much to the right as possible and make the latter extend as much to the left as possible. This motivates us to maintain a list of segments for each start index and each end index. Then, by sorting each of the lists, we can use binary search to efficiently compute the rightmost-extending segment that starts at $𝑆$ and ends before $𝑇$, and the leftmost-extending segment that starts after $𝑆$ and ends at $𝑇$.

There is one edge case where the two aforementioned greedily chosen segments are the same one. In that case, it must be that the segment is already exactly $\left[𝑆,𝑇\right]$. Hence, it suffices to check if there exists another segment lying completely inside $\left[𝑆,𝑇\right]$. This is the same as checking whether there are at least two different segments in $\left[𝑆,𝑇\right]$.

I recalled that this subproblem can be solved using a Fenwick Tree: sort the queries by descending order in $𝑆$, and maintain a Fenwick Tree on the values of $𝑇$.

This problem overall feels very, very natural, as the steps come out one at a time very logically, and the problem reduces to solving a few well-known subproblems one by one using standard techniques, while still having a fun and quick observation.

My code (note that my Fenwick Tree operates on half-open intervals $\left[𝐿,𝑅\right)$):

val n = nextInt()
val m = nextInt()
val start = Array(n + 1) { mutableListOf<Pair<Int, Int>>() }
val end = Array(n + 1) { mutableListOf<Pair<Int, Int>>() }
val intervals = Array(m) {
    val l = nextInt()
    val r = nextInt()
    start[l].add(Pair(r, it))
    end[r].add(Pair(l, it))
    Pair(l, r)
}
// Sort the start and end arrays
for (i in 1..n) {
    start[i].sortWith { x, y ->
        if (x.first == y.first) x.second.compareTo(y.second)
        else x.first.compareTo(y.first)
    }
    end[i].sortWith { x, y ->
        if (x.first == y.first) x.second.compareTo(y.second)
        else x.first.compareTo(y.first)
    }
}
val fw = FenwickTree(n + 1)
val q = nextInt()
// Sort the queries by descending order in S
val queries = Array(q) { Triple(nextInt(), nextInt(), it) }
             .sortedByDescending { it.first }
intervals.sortByDescending { it.first }
// Maintain a pointer to update the Fenwick Tree using two-pointer
var pt = 0
val ans = BooleanArray(q)
for (query in queries) {
    val (s, t, j) = query
    // Add the remaining segments that start after S
    while (pt < m && intervals[pt].first >= s)
        fw.update(intervals[pt++].second, 1)

    var a = start[s].binarySearch { if (it.first > t) 1 else -1 }
    if (a < 0) a = -a - 1
    a--
    var b = end[t].binarySearch { if (it.first >= s) 1 else -1 }
    if (b < 0) b = -b - 1

    if (a < 0 || b >= end[t].size)
        ans[j] = false
    else if (start[s][a].second == end[t][b].second)
        ans[j] = fw.query(t + 1) >= 2L
    else
        ans[j] = start[s][a].first + 1 >= end[t][b].first
}
for (j in 0 until q)
    println(if (ans[j]) "Yes" else "No")

F. Second Gap

Problem. Given an integer array $𝐷$ of length $𝑁-1$, count the number of permutations $𝑃$ of $1$ through $𝑁$, modulo $998244353$, such that for each $1\le 𝑖\le 𝑁-1$, if ${𝑃}_{𝑎}$ and ${𝑃}_{𝑏}$ are the largest and second-largest values among ${𝑃}_{𝑖},\dots ,{𝑃}_{𝑁}$, then $|𝑎-𝑏|={𝐷}_{𝑖}$.

Constraints. $2\le 𝑁\le 2\times {10}^5$, $1\le {𝐷}_{𝑖}\le 𝑁-𝑖$.

Analysis. For these types of counting problems, the idea is almost always to use some sort of DP. Furthermore, since the problem is about suffixes, it reminded me that I should consider solving backwards.

I first came up with a naive solution. Let $𝑑𝑝\left[𝑖\right]\left[𝑗\right]$ denote the number of possible suffixes that start from $𝑖$ and has a maximum at index $𝑗$.

Fix some $𝑖$. Now we can case on whether the largest element or the second-largest element in a suffix appears at position $𝑗$.

If neither is true, then the rest of the suffix only contributes a nonzero count from this transition if and only if ${𝐷}_{𝑗}={𝐷}_{𝑗+1}$. Hence, if ${𝐷}_{𝑗}={𝐷}_{𝑗+1}$, then there are $\left(𝑁-𝑗-1\right)$ choices for the elements, so $𝐷\left[𝑖\right]\left[𝑘\right]=\left(𝑁-𝑗-1\right)\cdot 𝐷\left[𝑖\right]\left[𝑘\right]$ for all $𝑘>𝑖$. If ${𝐷}_{𝑗}\ne {𝐷}_{𝑗+1}$, then set $𝐷\left[𝑖\right]\left[𝑘\right]=0$ for all $𝑘>𝑖$.

If the largest element is at position $𝑗$, then the second-largest element (which is previously the largest element) must be at position $𝑗+{𝐷}_{𝑗}$, so $𝑑𝑝\left[𝑖\right]\left[𝑗\right]≔𝑑𝑝\left[𝑖\right]\left[𝑗\right]+𝑑𝑝\left[𝑖+1\right]\left[𝑗+{𝐷}_{𝑗}\right]$.

If the second-largest element is at position $𝑗$, then the largest element (which is also previously the largest element) must be at position $𝑗+{𝐷}_{𝑗}$, so $𝑑𝑝\left[𝑖\right]\left[𝑗+{𝐷}_{𝑗}\right]≔𝑑𝑝\left[𝑖\right]\left[𝑗+{𝐷}_{𝑗}\right]+𝑑𝑝\left[𝑖+1\right]\left[𝑗+{𝐷}_{𝑗}\right]$.

This is correct but runs in $𝑂\left({𝑁}^2\right)$, which is not good. The observation is that most of the updates are “global” (i.e. similar for all the elements). We notice that the transitions are just range multiplication updates and point addition updates, which reminds us of a Lazy Segment Tree. Hence the problem can be solved in $𝑂\left(𝑁log𝑁\right)$ time, which is fast enough.

My code (note that my Segment Tree operates on half-open intervals $\left[𝐿,𝑅\right)$):

val n = nextInt()
val d = IntArray(n - 1) { nextInt() }
val dp = LazySegmentTree(
    n = n + 1,
    e = ModLong(0L),
    id = ModLong(1L),
    defaultValue = ModLong(0L),
    op = { a, b -> a + b },
    mapping = { f, x -> f * x },
    composition = { f, g -> f * g }
)
dp.set(n - 1, ModLong(1L))
dp.set(n, ModLong(1L))
for (i in n - 2 downTo 1) {
    val k = i + d[i - 1]
    val prev = dp.get(k)
    if (d[i] == d[i - 1])
        dp.apply(0, n + 1, ModLong((n - i - 1).toLong()))
    else
        dp.apply(0, n + 1, ModLong(0L))
    dp.set(i, dp.get(i) + prev)
    dp.set(k, dp.get(k) + prev)
}
val ans = dp.query(0, n + 1)
println(ans)

Remark. This problem can also be solved in $𝑂\left(𝑁\right)$, by applying a similar lazy idea and using some modular arithmetic tricks. However, the implementation is uglier. See my submission.

G. Catch All Apples

Problem. $𝑁$ apples fall on a number line. Apple $𝑖$ reaches coordinate ${𝑋}_{𝑖}$ at time ${𝑇}_{𝑖}$ and must be collected exactly at time ${𝑇}_{𝑖}$. Find the minimum number of robots you need to place so that if the robots have a speed of at most $1$ at each moment, there is a way for the robots to collect all $𝑁$ apples.

Constraints. $1\le 𝑁\le 3\times {10}^5$, ${𝑇}_{𝑖}\le 3\times {10}^5$, ${𝑋}_{𝑖}\le 3\times {10}^5$.

Analysis. This is the most fun problem in this set in my opinion. The task feels very “realistic” and natural.

First, I rephrased the problem as follows: what is the minimum number of partitions of the apples we need, such that within each partition, if we sort the apples by increasing $𝑇$, then $|{𝑋}_{𝑖+1}-{𝑋}_{𝑖}|\le {𝑇}_{𝑖+1}-{𝑇}_{𝑖}$ holds for all $𝑖$.

Now, we can apply the sum-difference substitution trick, which states that if $𝑎>𝑏$, then

This can be proven with some simple algebra manipulations. Now suppose ${𝑢}_{𝑖}={𝑇}_{𝑖}+{𝑋}_{𝑖}$ and ${𝑣}_{𝑖}={𝑇}_{𝑖}-{𝑋}_{𝑖}$. Then by above, if ${𝑇}_{𝑗}-{𝑇}_{𝑖}>0$, then $|{𝑋}_{𝑗}-{𝑋}_{𝑖}|\le {𝑇}_{𝑗}-{𝑇}_{𝑖}⟺{𝑢}_{𝑖}\le {𝑢}_{𝑗}\wedge {𝑣}_{𝑖}\le {𝑣}_{𝑗}$.

Now define the partial relation $\le$ on a pair by $\left(𝑎,𝑏\right)\le \left(𝑐,𝑑\right)$ if $𝑎\le 𝑐\wedge 𝑏\le 𝑑$. We can check that $\le$ is reflexive, symmetric, and transitive, so it is an equivalence relation. Hence the $\left({𝑢}_{𝑖},{𝑣}_{𝑖}\right)$ pairs from the apples form a finite partially ordered set, also known as a poset. The problem now reduces to computing the minimum number of chains needed to cover this poset!

We need to recall some Set Theory. By Dilworth’s theorem, the minimum number of chains needed to cover a poset is equal to the maximum length of an antichain. Hence, it suffices to compute the maximum length of an antichain in the pairs $\left({𝑢}_{𝑖},{𝑣}_{𝑖}\right)$.

Note that by definition, $\left({𝑢}_{𝑖},{𝑣}_{𝑖}\right),\left({𝑢}_{𝑗},{𝑣}_{𝑗}\right)$ are incomparable if and only if ${𝑢}_{𝑖}\le {𝑢}_{𝑗}\wedge {𝑣}_{𝑖}>{𝑣}_{𝑗}$ or ${𝑢}_{𝑖}>{𝑢}_{𝑗}\wedge {𝑣}_{𝑖}\le {𝑣}_{𝑗}$. If we sort them by $𝑣$, then if $𝑖<𝑗$, items $𝑖$ and $𝑗$ are incomparable if and only if ${𝑢}_{𝑖}>{𝑢}_{𝑗}$. The problems further reduces to the following: given an array $𝑈={𝑢}_1,{𝑢}_2,\dots ,{𝑢}_{𝑁}$, what is the longest subsequence $𝐿$ of $𝑈$ such that ${𝐿}_{𝑖}>{𝐿}_{𝑖+1}$ for all $𝑖$?

This is exactly the Longest Decreasing Subsequence (LDS) problem! The solution to this is well-known. For example, we can use dynamic programming with binary search optimization.

To summarize, we transform the apples into pairs $\left(𝑢,𝑣\right)$ where $𝑢=𝑇+𝑋$ and $𝑣=𝑇-𝑋$. After sorting the pairs by $𝑣$ in increasing order, the answer is the longest decreasing subsequence in $𝑢$ by Dilworth’s theorem.

Since the LIS/LDS problem can be solved in $𝑂\left(𝑁log𝑁\right)$, and the preprocessing is $𝑂\left(𝑁log𝑁\right)$ bottlenecked by sorting, the full solution to this problem runs in $𝑂\left(𝑁log𝑁\right)$, which is fast enough.

My code (here I sorted by $𝑢$ and ran LDS on $𝑣$, but the same idea works):

val n = nextInt()
// Substitution and sort in the first coordinate
val a = Array(n) {
    val t = nextInt()
    val x = nextInt()
    Pair(t + x, t - x)
}.sortedWith { a, b ->
    if (a.first == b.first)
          a.second.compareTo(b.second)
    else
          a.first.compareTo(b.first)
}
// Compute LDS in the second coordinate
val dp = Array(n + 1) { Int.MIN_VALUE }
dp[0] = Int.MAX_VALUE
var ans = 0
for (i in 0 until n) {
    val v = a[i].second
    var lo = 0
    var hi = ans + 1
    while (hi - lo > 1) {
        val mid = lo + (hi - lo) / 2
        if (dp[mid] <= v)
            hi = mid
        else
            lo = mid
    }
    dp[hi] = v
    if (hi > ans) ans = hi
}
println(ans)