tfg's blog

2025 ICPC South America — Brazil First Phase problem discussion
By tfg, history, 7 months ago, In English

Since usually there's no editorial for this contest (already on Gym), I wrote explanations to my team's (thank you leoanjos and gabmei) solutions during the official mirror/bracket that retired people can participate, they're available at https://github.com/tfg50/competitive-programming-tutorials/blob/main/ICPC/Latin%20america/2025%20Brazil%20First%20Phase/editorial.pdf. Solutions have been posted on the same repository. Feel free to share your opinions on the problems, ask questions, and perhaps comment on some of the alternative solutions that I didn't mention or explain.

  • Vote: I like it
  • +34
  • Vote: I do not like it

»
7 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by tfg (previous revision, new revision, compare).

→ Reply
»
7 months ago, hide # |
← Rev. 2  
Vote: I like it +10 Vote: I do not like it

Thanks for the editorial!

Could you clarify what you mean here:

To find if the congruences can be true at the same time, you can find a congruence with modulo divisor of Pi for the i-th congruence. The congruences with same modulo must not contradict.

I've seen the solution that claims there are at most sqrt different modulos (since their sum is N), so you can compare the ones with the same modulo and just check each pair of modulos. Not sure if you're saying the same thing.

→ Reply
  • »
    »
    7 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    Break

    $$$x \equiv c_i \mod P_i$$$

    into

    $$$x \equiv (c_i \% d) \mod d$$$

    for every d divisor of $$$P_i$$$. Then every $$$c_i \% d$$$ must be equal for congruences with the same d. You can iterate through divisors of $$$P_i$$$ by just iterating through every $$$x \in [1, P_i]$$$ since $$$\sum P_i \leq N$$$

    → Reply