1575A. Another Sorting Problem
Author: hocky
Developer: richiesenlia
Editorialist: hocky
1575B. Building an Amusement Park
Author: Panji
Developer: hocky, rama_pang
Editorialist: hocky
1575C. Cyclic Sum
Author: steven.novaryo
Developer: steven.novaryo
Editorialist: steven.novaryo
1575D. Divisible by Twenty-Five
Author: hocky
Developer: hocky
Editorialist: hocky
1575E. Eye-Pleasing City Park Tour
Author: steven.novaryo
Developer: rama_pang, hocky, steven.novaryo
Editorialist: rama_pang
1575F. Finding Expected Value
Author: rama_pang
Developer: rama_pang
Editorialist: rama_pang
1575G. GCD Festival
Author: yz_
Developer: hocky, yz_
Editorialist: rama_pang
1575H. Holiday Wall Ornaments
Author: hocky
Developer: Sakamoto, hocky
Editorialist: hocky
1575I. Illusions of the Desert
Author: JulianFernando
Developer: JulianFernando, hocky
1575J. Jeopardy of Dropped Balls
Author: richiesenlia
Developer: richiesenlia
Editorialist: hocky
<spoiler summary="Idea> Naively simulating the ball's path is enough, and runs in $$$O(nm + nk)$$$. Note that if we visit a non-$$$2$$$ cell, then the path length of the current ball is increased by $$$1$$$, and then the cell turns into $$$2$$$. So the total length of all paths can be increased by at most $$$O(nm)$$$ times. In addition, each ball needs at least $$$O(n)$$$ moves to travel, so we get $$$O(nm + nk)$$$.
We can improve this further. You can speed up each drops by storing consecutive $$$2$$$-cell segments in the downwards direction for each column. Using a Disjoint-Set Union data structure, for each cell $$$a_{x,y} = 2$$$, join it with its bottom cell if $$$a_{x + 1, y} = 2$$$.
Time complexity: $$$O(k + rc\cdot\alpha(rc))$$$
1575K. Knitting Batik
Author: hocky Developer: hocky
Observe that only some several non-intersecting part of $$$nm - rc$$$ that is independent in the grid. Simple casework shows that the answer is $$$k^{nm}$$$ if $$$a = b$$$, and $$$k^{nm - rc}$$$ otherwise.
Time complexity: $$$O(\log nm)$$$
1575L. Longest Array Deconstruction
Author: yz_
Developer: steven.novaryo
Editorialist: steven.novaryo
Define $$$a'$$$ as the array we get after removing some elements in $$$a$$$ and valid element as $$$a'_i$$$ that satisfy $$$a'_i = i$$$.
We can try to find combination of indices $$${c_1, c_2, \dots c_m}$$$ such that $$$a_{c_i} = a'_{p_i} = p_i$$$ for a certain set $$${p_1, p_2, \dots p_m}$$$. In other words, we want to find all indices $$${c_1, c_2, \dots c_m}$$$ such that $$$a_{c_i}$$$ will be a valid element in the $$$a'$$$.
Observe that each element in $$$c$$$ and every pair $$$i$$$ and $$$j$$$ ($$$i < j$$$) must satisfy: 1. $$$c_i < c_j$$$ 2. $$$a_{c_i} < a_{c_j}$$$ 3. $$$c_i - a_{c_i} \leq c_j - a_{c_j}$$$, the element you need to remove to adjust $$$a_{c_i}$$$ to it's location is smaller than $$$a_{c_j}$$$.
Therefore, we can convert each index into $$$(c_i, a_{c_i}, c_i - a_{c_i})$$$ and find the longest sequence of those tuples that satisfy the conditions. This is sufficient with divide and conquer in $$$O(n\log n\log n)$$$.
But the solution can be improved further. Notice that if $$$(2) \land (3) \implies (1)$$$. Hence we can solve problem by finding the longest sequence of pairs ($$$a_{c_i}, c_i - a_{c_i}$$$) with any standard LIS algorithm.
Time complexity: $$$O(n\log n)$$$
1575M. Managing Telephone Poles
Author: yz_
Developer: steven.novaryo
Editorialist: steven.novaryo
We can use convex hull trick to solve this problem.
Suppose that we only need to calculate $$$\sum_{x = 0}^{m} {S(x, y)}$$$ for a certain $$$y$$$. For a fixed $$$y$$$ axis and a pole located in point $$$(x_i, y_i)$$$, define $$$f(x) = (x - x_i)^2 + (y - y_i)^2 = - 2xx_i + x^2 - x_i^2 + (y - y_i)^2$$$, which is the euclidean distance of point $$$(x, y)$$$ and pole $$$(x_i, y_i)$$$.
Notice that, for a fixed pole $$$i$$$, $$$f(x)$$$ is a line equation, thus we can maintain it with convex hull trick.
Additionally, for a certain $$$y$$$, there are only $$$m$$$ poles that we need to consider. More specifically, pole $$$(x_i, y_i)$$$ is called considerable if there is no other pole $$$(x_j, y_j)$$$ such that $$$x_i = x_j$$$ and $$$|y_i - y| < |y_j - y|$$$.
Hence we can find the $$$\sum_{x = 0}^{m} {S(x, y)}$$$ for a certain $$$y$$$ in $$$O(m)$$$ or $$$O(m \log m)$$$. Calculating $$$\sum_{x = 0}^{m} {S(x, y)}$$$ for all $$$y$$$ will result in $$$O(nm)$$$ or $$$O(nm \log m)$$$ time complexity.