MarcosK's blog

By MarcosK, 16 months ago, In English

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
  • Vote: I like it
  • +120
  • Vote: I do not like it

»
16 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Thank u for the hint-solution style!

»
16 months ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

Good editorial! Some comments on a few of the easier problems:

104252C - City Folding

Spoiler

104252I - Italian Calzone & Pasta Corner

Spoiler

104252K - Kind Baker

Spoiler

104252L - Lazy Printing

Spoiler
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you elaborate more about how L can be done using kmp?

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it +1 Vote: I do not like it

104252I — Italian Calzone & Pasta Corner

Comment
»
16 months ago, # |
Rev. 6   Vote: I like it +14 Vote: I do not like it

104252B - Board Game has even another solution :)

Spoiler
  • »
    »
    16 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Another even crazier solution:

    Spoiler
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

some hint to solve the problem E in O(1)?

  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In how many ways can a number x be formed by the sum of two non-negative different integers?

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can't thank you enough for this editorial, I love you S2

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, will you also upload this year's ICPC problems?