Editorial for Codeforces Round #910 (Div. 2)

Revision en43, by BULLMCHOW, 2023-11-18 18:34:01

1779A - Hall of Fame

Author: n0sk1ll

Hint
Solution
Bonus

1779B - MKnez's ConstructiveForces Task

Author: BULLMCHOW & n0sk1ll

Hint
Solution
Bonus

1779C - Least Prefix Sum

Author: n0sk1ll

Hint
Solution
Bonus

1779D - Boris and His Amazing Haircut

Author: n0sk1ll

Hint
Solution
Bonus

1779B - MKnez's ConstructiveForces Task

Author: BULLMCHOW & n0sk1ll

Hint
Solution
Bonus

We will iterate over the array from right to left. Then, as described in the hint section, we will split the current $$$a_i$$$ and create almost equal parts. For example, $$$5$$$ split into three parts forms the subarray $$$[1,2,2]$$$. Splitting $$$8$$$ into four parts forms the subarray $$$[2,2,2,2]$$$. Notice that the subarrays must be sorted. Because we want to perform as few splits as possible, the rightmost endpoint value should be as high as possible (as long as it is lower than or equal to the leftmost endpoint of the splitting of $$$a_{i+1}$$$ if it exists).

When we iterate over the array, it is enough to set the current $$$a_i$$$ to the leftmost endpoint of the splitting (the smallest current value). It will help to calculate the optimal splitting of $$$a_{i-1}$$$. For the current $$$a_i$$$, we want to find the least $$$k$$$ such that we can split $$$a_{i-1}$$$ into $$$k$$$ parts so the rightmost endpoint is less than or equal to $$$a_i$$$. More formally, we want $$$\lceil \frac{a_{i-1}}{k} \rceil \leq a_i$$$ to hold. Afterwards, we set $$$a_{i-1}$$$ to $$$\lfloor \frac{a_{i-1}}{k} \rfloor$$$ and continue with our algorithm. The simplest way to find the desired $$$k$$$ is to apply the following formula:

$$$k=\lceil \frac{a_{i-1}}{a_i} \rceil$$$

The answer is the sum over all $$$k-1$$$.

There are $$$q \leq 2\cdot 10^5$$$ queries: given an index $$$i$$$ and an integer $$$x>1$$$, set $$$a_i := \lceil \frac{a_i}{x} \rceil$$$. Modify the array and print the answer to the original problem. Please note that the queries stack.

1779F - Xorcerer's Stones

Author: n0sk1ll

To solve the problem for matrices of $$$3$$$-rd type, find the shortest path to $$$2$$$ closest exits with a modification of BFS. Block all cells not belonging to the path with obstacles.

For a matrix of type $$$1$$$, Misha can block all empty cells (except the one Vova stands on).

For a matrix of type $$$2$$$, Misha finds the shortest path to some exit with a single BFS and then blocks every other cell.

Matrices of type $$$3$$$ are more complicated. We want to find two shortest paths to the two closest exits and block the remaining empty cells.

But, notice how the paths will likely share their beginnings. We do not have to count those cells twice. Let's take a look at the junction where the two paths merge. If we first fix the junction, finding the shortest path to Vova can be done by running a single BFS and precalculating the shortest distances from each cell to Vova. Finding the shortest path from the junction to the two closest exits can also be done with BFS and precalculation. We modify the BFS, making it multi-source, with a source in each exit. Also, we will allow each cell to be visited twice (but by different exits). We will need to maintain the following data for each cell:

  • How many times was it visited;
  • The last exit/source that visited it;
  • The sum of paths from all exits/sources that visited the cell so far.

Running the BFS with proper implementation produces the answer. When everything said is precalculated, we fix the junction in $$$O(nm)$$$ ways (each empty cell can be a valid junction), and then calculate the shortest path from Vova to the two closest cells in $$$O(1)$$$ per junction.

Total complexity is $$$O(nm)$$$.

Solve the problem with LCA, or report that such solution does not exist.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en80 English n0sk1ll 2023-11-19 19:35:24 0 (published)
en79 English n0sk1ll 2023-11-19 19:25:25 2 Tiny change: '## [1898B *-* Milic' -> '## [1898A *-* Milic'
en78 English n0sk1ll 2023-11-19 19:25:02 71
en77 English n0sk1ll 2023-11-19 19:24:46 67
en76 English n0sk1ll 2023-11-19 19:24:15 9 Tiny change: '## [1898B ‐ Milica and' -> '## [1898B-Milica and'
en75 English n0sk1ll 2023-11-19 19:23:54 1 Tiny change: '# [1898B — Mili' -> '# [1898B ‐ Mili'
en74 English n0sk1ll 2023-11-19 19:22:13 76
en73 English n0sk1ll 2023-11-19 19:19:56 1 Tiny change: 'oblem:1898A]\n\nAuth' -> 'oblem:1898 A]\n\nAuth'
en72 English n0sk1ll 2023-11-19 19:19:39 2 Tiny change: 'roblem:1897A]\n\nAuth' -> 'roblem:1898A]\n\nAuth'
en71 English n0sk1ll 2023-11-19 19:15:37 2 Tiny change: 'roblem:1898A]\n\nAuth' -> 'roblem:1897A]\n\nAuth'
en70 English n0sk1ll 2023-11-19 19:15:22 4 Tiny change: '[problem:12A]\n\nAuth' -> '[problem:1898A]\n\nAuth'
en69 English n0sk1ll 2023-11-19 19:07:55 4 Tiny change: '[problem:1898A]\n\nAuth' -> '[problem:12A]\n\nAuth'
en68 English n0sk1ll 2023-11-19 19:06:58 4 Tiny change: '[problem:12A]\n\nAuth' -> '[problem:1898A]\n\nAuth'
en67 English n0sk1ll 2023-11-19 19:06:40 4 Tiny change: '[problem:1898A]\n\nAuth' -> '[problem:12A]\n\nAuth'
en66 English n0sk1ll 2023-11-19 19:06:25 0 Tiny change: '## [problem:1898A]\n\nAuthor' -> '## \n\nAuthor'
en65 English n0sk1ll 2023-11-19 16:41:26 0 Tiny change: '## [problem:1' -> '[problem:1'
en64 English n0sk1ll 2023-11-19 16:39:45 24
en63 English n0sk1ll 2023-11-19 11:58:57 56
en62 English n0sk1ll 2023-11-18 22:23:08 6 Tiny change: '<j_1$.\n\nOverall com' -> '<j_1$.\n\nThe overall com'
en61 English n0sk1ll 2023-11-18 22:22:32 2 Tiny change: 'bet size (\alpha=26 in this p' -> 'bet size ($\alpha=26$ in this p'
en60 English n0sk1ll 2023-11-18 22:22:00 111
en59 English n0sk1ll 2023-11-18 22:11:55 12 Tiny change: 'ater than the secon' -> 'ater than or equal to the secon'
en58 English n0sk1ll 2023-11-18 22:11:19 4
en57 English n0sk1ll 2023-11-18 22:10:39 36
en56 English n0sk1ll 2023-11-18 22:09:53 1387
en55 English BULLMCHOW 2023-11-18 20:12:16 57
en54 English BULLMCHOW 2023-11-18 20:10:22 244
en53 English BULLMCHOW 2023-11-18 20:05:00 17
en52 English BULLMCHOW 2023-11-18 19:57:53 3
en51 English BULLMCHOW 2023-11-18 19:56:55 4 Tiny change: ' $s_j$ to the position ' -> ' $s_j$ to position '
en50 English BULLMCHOW 2023-11-18 19:54:02 9
en49 English BULLMCHOW 2023-11-18 19:52:28 2
en48 English BULLMCHOW 2023-11-18 19:52:28 0
en47 English BULLMCHOW 2023-11-18 19:52:28 2217
en46 English BULLMCHOW 2023-11-18 18:36:42 129
en45 English BULLMCHOW 2023-11-18 18:35:05 1924
en44 English BULLMCHOW 2023-11-18 18:34:10 1934 Reverted to en39
en43 English BULLMCHOW 2023-11-18 18:34:01 1600 Reverted to en41
en42 English BULLMCHOW 2023-11-18 18:33:19 2064
en41 English BULLMCHOW 2023-11-18 18:32:23 181
en40 English BULLMCHOW 2023-11-18 18:31:35 1997
en39 English n0sk1ll 2023-11-18 12:10:56 2 Tiny change: 'bilities. implementin' -> 'bilities. Implementin'
en38 English n0sk1ll 2023-11-18 12:07:00 7 Tiny change: 'd $j$, we simply find the ' -> 'd $j$, we find the '
en37 English n0sk1ll 2023-11-18 12:02:57 230
en36 English n0sk1ll 2023-11-15 23:17:37 45
en35 English n0sk1ll 2023-11-15 23:13:25 89
en34 English n0sk1ll 2023-11-15 23:11:36 54
en33 English n0sk1ll 2023-11-15 23:09:36 16 Tiny change: ' times as it should (and try ' -> ' times as necessary (and try '
en32 English n0sk1ll 2023-11-15 23:08:30 1332
en31 English n0sk1ll 2023-11-15 15:15:36 56
en30 English n0sk1ll 2023-11-15 15:12:25 2056
en29 English n0sk1ll 2023-11-13 21:55:30 2 Tiny change: 'ed in the *hint* section.\' -> 'ed in the hint section.\'
en28 English n0sk1ll 2023-11-13 21:53:55 155
en27 English n0sk1ll 2023-11-13 21:48:01 1519
en26 English n0sk1ll 2023-11-12 21:14:31 235
en25 English n0sk1ll 2023-11-12 21:11:13 57
en24 English n0sk1ll 2023-11-12 21:09:33 147
en23 English n0sk1ll 2023-11-12 21:04:05 643
en22 English n0sk1ll 2023-11-12 20:41:57 2562
en21 English n0sk1ll 2023-10-07 22:46:21 107
en20 English n0sk1ll 2023-10-07 22:44:30 38
en19 English n0sk1ll 2023-10-07 22:43:16 50
en18 English n0sk1ll 2023-10-07 22:39:42 2817 Tiny change: ' \equiv x (\mod p)$' -> ' \equiv x \ (\mod p)$'
en17 English n0sk1ll 2023-10-02 10:44:23 230
en16 English BULLMCHOW 2023-10-02 09:32:30 37 Tiny change: ' of $a_i$ after th' -> ' of $a_i$ to $\lfloor \frac{a_i}{m+1} \rfloor$ after th'
en15 English BULLMCHOW 2023-10-01 18:39:16 23
en14 English BULLMCHOW 2023-10-01 18:36:19 8 Tiny change: ' $a_i$ be divided into in' -> ' $a_i$ be splited into in'
en13 English BULLMCHOW 2023-10-01 18:32:14 224
en12 English BULLMCHOW 2023-10-01 18:24:48 5 Tiny change: 'we will solve the array' -> 'we will sort the array'
en11 English BULLMCHOW 2023-10-01 18:24:10 824
en10 English BULLMCHOW 2023-10-01 17:59:57 4
en9 English BULLMCHOW 2023-10-01 17:58:00 11 Tiny change: '>\nAfter every operation the number of' -> '>\nAfter each operation number of'
en8 English BULLMCHOW 2023-10-01 17:57:04 105
en7 English BULLMCHOW 2023-10-01 17:56:27 279
en6 English BULLMCHOW 2023-10-01 17:47:08 25
en5 English BULLMCHOW 2023-10-01 17:43:48 7 Tiny change: ' subarray left from $a_' -> ' subarray right from $a_'
en4 English BULLMCHOW 2023-10-01 17:42:48 189
en3 English BULLMCHOW 2023-10-01 17:33:21 45
en2 English n0sk1ll 2023-10-01 14:34:31 239
en1 English n0sk1ll 2023-10-01 14:31:01 1091 Initial revision (saved to drafts)