MarcosK's blog

By MarcosK, 16 months ago,

Hi everyone!

The 2022-2023 ICPC Latin America Regional Programming Contest was held last weekend. Given that (as far as I know) there is no official editorial for the problems, I decided to create one.

Please notice that, given that these are not the official solutions, there can be typos/mistakes in the explanations. Feedback is always appreciated :)

I would like to thank lsantire for reviewing the editorial and providing valuable feedback.

Don't hesitate to reach out to me if you have any questions/suggestions. Thank you!

104252A - Asking for Money

Hint
Solution
Code

104252B - Board Game

Hint
Solution
Code

104252C - City Folding

Hint
Solution
Code

104252D - Daily Trips

Hint
Solution
Code

104252E - Empty Squares

Hint
Solution
Code

104252F - Favorite Tree

Hint
Solution
Code

104252G - Gravitational Wave Detector

Hint
Solution
Code

104252H - Horse Race

Hint
Solution
Code

104252I - Italian Calzone & Pasta Corner

Hint
Solution
A case that takes O(n^4 * log n) operations
Code

104252J - Joining a Marathon

Hint
Solution
Code

104252K - Kind Baker

Hint
Solution
Code

104252L - Lazy Printing

Hint
Solution
Code

104252M - Maze in Bolt

Hint
Solution
Code
• +120

 » 16 months ago, # |   +8 Thank u for the hint-solution style!
 » 16 months ago, # | ← Rev. 2 →   +18 Good editorial! Some comments on a few of the easier problems:104252C - City Folding SpoilerIf you do only R folds, you can notice the element in height $H$ (0-indexed) is the representation of $\frac{H}{2}$ in binary, reversed. You don't need to notice this to solve the original problem, but you can get a neat simple description of what the entire final permutation looks like (it's essentially a bit-reversal permutation).104252I - Italian Calzone & Pasta Corner SpoilerYou don't need the $O(\log n)$ term in the complexity, because you can just iterate from $1$ to $RC$ and check if the next number is a candidate for expansion or not.104252K - Kind Baker SpoilerMake a 50-pronged fork with all colors you are going to use (like this Ш, but with 50 vertical lines). Now all other squares are connected to this fork, so you can paint them however you like, and there are more than 4000 of them. So number the squares from $1$ to $K-2$ and paint square $i$ with $i$ in binary.104252L - Lazy Printing SpoilerFrom my dislike of hashing and wish to avoid copying suffix array: You can also find the longest prefix that is periodic with period $P \leq D$ via a direct application of KMP.
•  » » 16 months ago, # ^ |   0 About problem I: in practice, I think the solution I proposed is faster because, in the worst case I could come up with, the amount of operations is around $\frac{n^4}{16}$. Even for values of n like 200 or 250, my code finishes in less than a second.Anyways, I found your solution way simpler to code, and the constant factor is almost non existing. Good call!
•  » » » 16 months ago, # ^ |   +8 I'm usually not very interested in constant optimizations, but if that's the subject another thing you can do in problem I is to use bitsets (if you add edges from smaller numbers to bigger numbers you can treat it is a "count reachable nodes in a DAG" problem, a problem I apparently helped turn into a meme).
•  » » 15 months ago, # ^ |   0 Can you elaborate more about how L can be done using kmp?
•  » » » 15 months ago, # ^ |   0 It is pretty direct as I said: if the KMP failure function is $T_i$, then the period of the prefix with length $i$ is $i - T_i$.Assuming you know how KMP works, it should be simple to explain why; if you don't, well, I probably shouldn't write an entire KMP tutorial in a comment. :)
 » 16 months ago, # | ← Rev. 2 →   +1 104252I — Italian Calzone & Pasta Corner CommentThere is a faster solution which runs in $O(n^4)$. From each cell, instead of running a priority queue, we can run a simple DFS. Suppose that we are in a certain cell, we will always move to another cell which has a greater value than the current cell we are. When we finish visiting all possible cells, it can be shown that the greedy path mentioned by MarcosK exists.
 » 16 months ago, # | ← Rev. 6 →   +14 104252B - Board Game has even another solution :) SpoilerYou can notice that given a token, you can find the player that takes it by just adding the lines one by one until one line covers the token. However, it's also possible to take a slower approach using binary search. In each step, just test if any of the first $p$ lines covers the token by adding the first $p$ lines to the structure. This procedure would take $O(P \cdot log^2 P)$. You may be wondering why we would want to take this approach as repeating this procedure for each token would result in TLE. However, the good part is that you can run all the binary searches in parallel! That would lead to an $O(logP \cdot (P + T \cdot logP))$ solution.Implementation: 198648853
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 Another even crazier solution: SpoilerInstead of doing a new lichao tree in every iteration of the parallel binary search, you can alternatively make a persistent lichao tree, then for every point you can binary search to find up to what line the condition holds.Implementation
 » 16 months ago, # |   0 some hint to solve the problem E in O(1)?
•  » » 16 months ago, # ^ |   0 In how many ways can a number x be formed by the sum of two non-negative different integers?
 » 15 months ago, # |   0 can't thank you enough for this editorial, I love you S2
 » 9 months ago, # |   0 Hello, will you also upload this year's ICPC problems?
•  » » 9 months ago, # ^ |   +12 The problems are already uploaded on gym: https://codeforces.com/gym/104736/standings
•  » » » 9 months ago, # ^ |   0 Thank you, when can I see the solutions sent?