Croatian Open Competition in Informatics (COCI) 2021/2022 — Round #5

Hi everyone!

The fifth round of COCI will be held tomorrow, March 5th at 14:00 UTC. You can access the judging system here. If you are not familiar with COCI contest format, we encourage you to read the announcement.

The round was prepared by ominikfistric, Bartol, pavkal5, and me.

Feel free to discuss the problems in the comment section after the contest ends.

Support for rust will be added either for the next round or for the next season.

Hope to see you tomorrow!

• 23 hours ago, # ^ |

  I agree that A was super toxic but imple for B is quite simple and short?

• 23 hours ago, # ^ |

  ← Rev. 3 →  

  +34

  GCD(x, y) = 1 iff exists some prime number that divides both of the x and y.

  Let's say A[1], A[3], A[4], A[10] are divisible by p, then segments [1, 3], [3, 4] and [4, 10] are "bad", i.e. answer is "DA" if the given segment contains some "bad" segment.

  It is clear that the number of bad segments doesn't exceed O(q*k), where k is the maximal number of prime divisors of some number (k <= 7).

  Let's update each l with the minimum r such that [l, r] is bad. The answer is "DA" if getmin(l, r) <= r.

  Complexity O(n + qklog(n)), where k<=7

  • 22 hours ago, # ^ |

    Great. I'm so stupid that I used 2D data structures for the last part of the solution. Thank you so much for sharing your solution.

• 22 hours ago, # ^ |

  Here is my solution:

  The problem is essentially just directing the edges in a way to have the minimum possible number of total SCCs.

  Let's say that we directed all the edges from left to right initially. Some edges won't have an impact on the compressed SCC graph. An example of this is if you have the edges "4 1" and "2 3". If you include the edge "4 1", you can notice that adding the edge "2 3" doesn't do anything since node 2 on the left side is already connected to node 3 on the right side. Let's call edges like "2 3" in this example with the term "useless" and all other edges "useful". There are many ways to find the useful edges but I used a segment tree RMQ to do it. After finding all the useful edges, I direct the useful edges from left to right and I direct the useless edges from right to left. After, you can just build the graph and run any SCC algorithm to count the number of SCCs.

  • 21 hour(s) ago, # ^ |

    The approach focusing on directing the edges from left to right is cool! thanks!

    I was stuck on directing both directions simultaneously and failed to get any points :(