COMPFEST 13 — Editorial

Revision en9, by hocky, 2021-10-03 08:15:30

1575A. Another Sorting Problem

Author: hocky
Developer: Richie

Idea

1575B. Building an Amusement Park

Author: Panji
Developer: hocky, rama_pang

Idea

1575C. Cyclic Sum

Author: steven.novaryo
Developer: steven.novaryo

Idea

1575D. Divisible by Twenty-Five

Author: hocky
Developer: hocky

Idea

1575E. Eye-Pleasing City Park Tour

Author: steven.novaryo
Developer: hocky

Idea

1575F. Finding Expected Value

Author: rama_pang
Developer: rama_pang

Idea

1575G. GCD Festival

Author: yz_
Developer: hocky, yz_

Idea

1575H. Holiday Wall Ornaments

Author: hocky
Developer: Sakamoto, hocky

Idea

define the dynamic programming of $$$dp[a][b][rem]$$$ as the minimum cost of having the string $$$p = s[1..a]$$$, $$$rem$$$ matches left, and the longest prefix match between $$$s$$$ and $$$t$$$ is at $$$b$$$. The answer will be at $$$dp[n][c][0]$$$ for any arbitrary $$$c$$$.

The transition can first be precomputed with brute force in $$$O(n^3)$$$ or with Aho-Corasick.

Time complexity: $$$O(n^3)$$$ Space complexity: $$$O(n^2)$$$

1575I. Illusions of the Desert

Author: JulianFernando
Developer: JulianFernando, hocky

Idea

Now the problem can be reduced to updating a vertex's value and querying the sum of values of vertices in a path.

This can be done in several ways. One can use euler tour tree flattening method, as described in Euler Tour Magic by brdy blog, or use heavy-light decomposition.

Time complexity : $$$O((q + n) \log^2 n)$$$ or $$$O((q + n) \log n)$$$

1575J. Jeopardy of Dropped Balls

[](https://codeforces.me/contest/1575/problem/J) Author: richiesenlia Developer: richiesenlia Expected difficulty: Easy

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

Idea

Time complexity: $$$O(\log nm)$$$

1575L. Longest Array Deconstruction

Author: yz_
Developer: steven.novaryo

Idea

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

Idea

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en27 English hocky 2021-10-03 10:41:52 1032
en26 English hocky 2021-10-03 10:02:23 0 (published)
en25 English hocky 2021-10-03 09:20:01 2
en24 English hocky 2021-10-03 09:19:35 61
en23 English hocky 2021-10-03 09:19:08 11
en22 English hocky 2021-10-03 09:17:14 439
en21 English steven.novaryo 2021-10-03 08:55:33 132
en20 English steven.novaryo 2021-10-03 08:46:27 20
en19 English hocky 2021-10-03 08:39:43 70
en18 English hocky 2021-10-03 08:36:45 2 Tiny change: '021-10-03]\nEditoria' -> '021-10-03] \nEditoria'
en17 English hocky 2021-10-03 08:34:45 97
en16 English hocky 2021-10-03 08:30:17 2 Tiny change: ' states:\n- Positi' -> ' states:\n\n- Positi'
en15 English hocky 2021-10-03 08:29:26 6
en14 English hocky 2021-10-03 08:24:10 37
en13 English hocky 2021-10-03 08:23:24 106
en12 English hocky 2021-10-03 08:21:39 1
en11 English hocky 2021-10-03 08:20:57 566
en10 English hocky 2021-10-03 08:17:16 160 Tiny change: 'O(n^2)$ \n\n## [15' -> 'O(n^2)$ \n</spoiler>\n\n## [15'
en9 English hocky 2021-10-03 08:15:30 461 Tiny change: '\n<spoiler>\n</spoil' -> '\n<spoiler summary="Idea">\n</spoil'
en8 English hocky 2021-10-03 08:12:50 25 Tiny change: '10-03]\n\nObserv' -> '10-03]\n\n<spoiler>\n</spoiler>\n\nObserv'
en7 English hocky 2021-10-03 08:12:21 770
en6 English hocky 2021-10-03 08:03:41 30
en5 English hocky 2021-10-03 08:02:33 143
en4 English hocky 2021-10-03 07:59:58 620
en3 English hocky 2021-10-03 07:53:59 86
en2 English hocky 2021-10-03 07:46:55 128
en1 English hocky 2021-10-03 07:44:51 16360 Initial revision (saved to drafts)