May 11, 2026 AtCoder Beginner Contest 457 A very cute, balanced, and educational problem set. #competitive programming #atcoder IntroductionThe 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. ArrayProblem. Given an array 𝐴 of length 𝑁 and integer 𝑋, find 𝐴𝑋.Analysis. Ask a toddler on the street.B. ArraysProblem. Given an array 𝐴 consisting of 𝑁 arrays and two integers 𝑋 and 𝑌, output 𝐴𝑋,𝑌.Analysis. Ask a Chinese kindergarten student.C. Long SequenceProblem. 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,…,𝑁 in this order, find 𝐵𝐾.Constraints. ∑𝑁𝑖=1|𝐴𝑖|≤2×105, 1≤𝐴𝑖,𝑗≤109, 1≤𝐶𝑖≤109.Analysis. Simulating can take over 1014 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𝑅𝑚=(𝐾−1)−∑𝑚𝑖=1(|𝐴𝑖|𝐶𝑖)as the number of elements remaining after skipping over 𝐴1,…,𝐴𝑚. There must exist a unique 𝑚 such that𝑅𝑚<|𝐴𝑚+1|𝐶𝑚+1,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 MinimumProblem. You are given an array 𝐴 of length 𝑁 and an integer 𝐾. In one operation, you can choose some 1≤𝑖≤𝑁 and set 𝐴𝑖≔𝐴𝑖+𝑖. After at most 𝐾 operations, what is the maximum possible value of min1≤𝑖≤𝑁𝐴𝑖?Constraints. 1≤𝑁≤2×105, 1≤𝐴𝑖≤1018, 1≤𝐾≤1018.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𝐶𝑖=max{0,⌈𝐿−𝐴𝑖𝑖⌉}operations to raise 𝐴𝑖 to at least 𝐿 (which should hold for all 𝑖). Therefore, the minimum number of operations needed is ∑𝑁𝑖=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 = 0Lvar hi = Long.MAX_VALUE - 1while (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 ClothProblem. You are given 𝑀 segments on the cells 1,2,…,𝑁. For each of the 𝑄 queries, given integers 𝑆≤𝑇, determine whether or not there exist exactly two segments such that their union is exactly [𝑆,𝑇].Constraints. 1≤𝑁≤2×105, 2≤𝑀≤2×105, 1≤𝑄≤2×105.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 [𝑆,𝑇]. Hence, it suffices to check if there exists another segment lying completely inside [𝑆,𝑇]. This is the same as checking whether there are at least two different segments in [𝑆,𝑇].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 [𝐿,𝑅)):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 arraysfor (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 Sval queries = Array(q) { Triple(nextInt(), nextInt(), it) } .sortedByDescending { it.first }intervals.sortByDescending { it.first }// Maintain a pointer to update the Fenwick Tree using two-pointervar pt = 0val 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 GapProblem. Given an integer array 𝐷 of length 𝑁−1, count the number of permutations 𝑃 of 1 through 𝑁, modulo 998244353, such that for each 1≤𝑖≤𝑁−1, if 𝑃𝑎 and 𝑃𝑏 are the largest and second-largest values among 𝑃𝑖,…,𝑃𝑁, then |𝑎−𝑏|=𝐷𝑖.Constraints. 2≤𝑁≤2×105, 1≤𝐷𝑖≤𝑁−𝑖.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 𝑑𝑝[𝑖][𝑗] 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 (𝑁−𝑗−1) choices for the elements, so 𝐷[𝑖][𝑘]=(𝑁−𝑗−1)⋅𝐷[𝑖][𝑘] for all 𝑘>𝑖. If 𝐷𝑗≠𝐷𝑗+1, then set 𝐷[𝑖][𝑘]=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 𝑑𝑝[𝑖][𝑗]≔𝑑𝑝[𝑖][𝑗]+𝑑𝑝[𝑖+1][𝑗+𝐷𝑗].If the second-largest element is at position 𝑗, then the largest element (which is also previously the largest element) must be at position 𝑗+𝐷𝑗, so 𝑑𝑝[𝑖][𝑗+𝐷𝑗]≔𝑑𝑝[𝑖][𝑗+𝐷𝑗]+𝑑𝑝[𝑖+1][𝑗+𝐷𝑗].This is correct but runs in 𝑂(𝑁2), 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 𝑂(𝑁log𝑁) time, which is fast enough.My code (note that my Segment Tree operates on half-open intervals [𝐿,𝑅)):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 𝑂(𝑁), by applying a similar lazy idea and using some modular arithmetic tricks. However, the implementation is uglier. See my submission.G. Catch All ApplesProblem. 𝑁 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≤𝑁≤3×105, 𝑇𝑖≤3×105, 𝑋𝑖≤3×105.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−𝑋𝑖|≤𝑇𝑖+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 |𝑋𝑗−𝑋𝑖|≤𝑇𝑗−𝑇𝑖⟺𝑢𝑖≤𝑢𝑗∧𝑣𝑖≤𝑣𝑗.Now define the partial relation ≤ on a pair by (𝑎,𝑏)≤(𝑐,𝑑) if 𝑎≤𝑐∧𝑏≤𝑑. We can check that ≤ is reflexive, symmetric, and transitive, so it is an equivalence relation. Hence the (𝑢𝑖,𝑣𝑖) 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 (𝑢𝑖,𝑣𝑖).Note that by definition, (𝑢𝑖,𝑣𝑖),(𝑢𝑗,𝑣𝑗) are incomparable if and only if 𝑢𝑖≤𝑢𝑗∧𝑣𝑖>𝑣𝑗 or 𝑢𝑖>𝑢𝑗∧𝑣𝑖≤𝑣𝑗. 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,…,𝑢𝑁, 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 (𝑢,𝑣) 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 𝑂(𝑁log𝑁), and the preprocessing is 𝑂(𝑁log𝑁) bottlenecked by sorting, the full solution to this problem runs in 𝑂(𝑁log𝑁), 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 coordinateval 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 coordinateval dp = Array(n + 1) { Int.MIN_VALUE }dp[0] = Int.MAX_VALUEvar ans = 0for (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) IntroductionThe 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. ArrayProblem. Given an array 𝐴 of length 𝑁 and integer 𝑋, find 𝐴𝑋.Analysis. Ask a toddler on the street.B. ArraysProblem. Given an array 𝐴 consisting of 𝑁 arrays and two integers 𝑋 and 𝑌, output 𝐴𝑋,𝑌.Analysis. Ask a Chinese kindergarten student.C. Long SequenceProblem. 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,…,𝑁 in this order, find 𝐵𝐾.Constraints. ∑𝑁𝑖=1|𝐴𝑖|≤2×105, 1≤𝐴𝑖,𝑗≤109, 1≤𝐶𝑖≤109.Analysis. Simulating can take over 1014 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𝑅𝑚=(𝐾−1)−∑𝑚𝑖=1(|𝐴𝑖|𝐶𝑖)as the number of elements remaining after skipping over 𝐴1,…,𝐴𝑚. There must exist a unique 𝑚 such that𝑅𝑚<|𝐴𝑚+1|𝐶𝑚+1,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 MinimumProblem. You are given an array 𝐴 of length 𝑁 and an integer 𝐾. In one operation, you can choose some 1≤𝑖≤𝑁 and set 𝐴𝑖≔𝐴𝑖+𝑖. After at most 𝐾 operations, what is the maximum possible value of min1≤𝑖≤𝑁𝐴𝑖?Constraints. 1≤𝑁≤2×105, 1≤𝐴𝑖≤1018, 1≤𝐾≤1018.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𝐶𝑖=max{0,⌈𝐿−𝐴𝑖𝑖⌉}operations to raise 𝐴𝑖 to at least 𝐿 (which should hold for all 𝑖). Therefore, the minimum number of operations needed is ∑𝑁𝑖=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 = 0Lvar hi = Long.MAX_VALUE - 1while (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 ClothProblem. You are given 𝑀 segments on the cells 1,2,…,𝑁. For each of the 𝑄 queries, given integers 𝑆≤𝑇, determine whether or not there exist exactly two segments such that their union is exactly [𝑆,𝑇].Constraints. 1≤𝑁≤2×105, 2≤𝑀≤2×105, 1≤𝑄≤2×105.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 [𝑆,𝑇]. Hence, it suffices to check if there exists another segment lying completely inside [𝑆,𝑇]. This is the same as checking whether there are at least two different segments in [𝑆,𝑇].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 [𝐿,𝑅)):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 arraysfor (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 Sval queries = Array(q) { Triple(nextInt(), nextInt(), it) } .sortedByDescending { it.first }intervals.sortByDescending { it.first }// Maintain a pointer to update the Fenwick Tree using two-pointervar pt = 0val 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 GapProblem. Given an integer array 𝐷 of length 𝑁−1, count the number of permutations 𝑃 of 1 through 𝑁, modulo 998244353, such that for each 1≤𝑖≤𝑁−1, if 𝑃𝑎 and 𝑃𝑏 are the largest and second-largest values among 𝑃𝑖,…,𝑃𝑁, then |𝑎−𝑏|=𝐷𝑖.Constraints. 2≤𝑁≤2×105, 1≤𝐷𝑖≤𝑁−𝑖.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 𝑑𝑝[𝑖][𝑗] 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 (𝑁−𝑗−1) choices for the elements, so 𝐷[𝑖][𝑘]=(𝑁−𝑗−1)⋅𝐷[𝑖][𝑘] for all 𝑘>𝑖. If 𝐷𝑗≠𝐷𝑗+1, then set 𝐷[𝑖][𝑘]=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 𝑑𝑝[𝑖][𝑗]≔𝑑𝑝[𝑖][𝑗]+𝑑𝑝[𝑖+1][𝑗+𝐷𝑗].If the second-largest element is at position 𝑗, then the largest element (which is also previously the largest element) must be at position 𝑗+𝐷𝑗, so 𝑑𝑝[𝑖][𝑗+𝐷𝑗]≔𝑑𝑝[𝑖][𝑗+𝐷𝑗]+𝑑𝑝[𝑖+1][𝑗+𝐷𝑗].This is correct but runs in 𝑂(𝑁2), 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 𝑂(𝑁log𝑁) time, which is fast enough.My code (note that my Segment Tree operates on half-open intervals [𝐿,𝑅)):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 𝑂(𝑁), by applying a similar lazy idea and using some modular arithmetic tricks. However, the implementation is uglier. See my submission.G. Catch All ApplesProblem. 𝑁 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≤𝑁≤3×105, 𝑇𝑖≤3×105, 𝑋𝑖≤3×105.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−𝑋𝑖|≤𝑇𝑖+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 |𝑋𝑗−𝑋𝑖|≤𝑇𝑗−𝑇𝑖⟺𝑢𝑖≤𝑢𝑗∧𝑣𝑖≤𝑣𝑗.Now define the partial relation ≤ on a pair by (𝑎,𝑏)≤(𝑐,𝑑) if 𝑎≤𝑐∧𝑏≤𝑑. We can check that ≤ is reflexive, symmetric, and transitive, so it is an equivalence relation. Hence the (𝑢𝑖,𝑣𝑖) 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 (𝑢𝑖,𝑣𝑖).Note that by definition, (𝑢𝑖,𝑣𝑖),(𝑢𝑗,𝑣𝑗) are incomparable if and only if 𝑢𝑖≤𝑢𝑗∧𝑣𝑖>𝑣𝑗 or 𝑢𝑖>𝑢𝑗∧𝑣𝑖≤𝑣𝑗. 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,…,𝑢𝑁, 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 (𝑢,𝑣) 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 𝑂(𝑁log𝑁), and the preprocessing is 𝑂(𝑁log𝑁) bottlenecked by sorting, the full solution to this problem runs in 𝑂(𝑁log𝑁), 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 coordinateval 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 coordinateval dp = Array(n + 1) { Int.MIN_VALUE }dp[0] = Int.MAX_VALUEvar ans = 0for (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)