This problem was our way of saying hi:)

To solve the problem you can keep increasing n until it is divisible by k, this is a linear solution.

A constant solution is to find how much we need to add to n to make it divisible by k, so the solution becomes $$$x + k - (x \pmod k)$$$, or $$$(n / k + 1) * k$$$ taking advantage of integer (floor) division.

• Didn't solve
• Good problem
• Average task
• Bad task

Connecting and disconnecting roads gives a hint to using DSU, also finding the minimum number of coins gives a hint to binary search.

The first thing we notice is that blocking all roads would be valid, now to construct the solution, we will use binary search on the answer, it will work because if we blocked all roads that cost $$$X$$$ or less and it was valid, blocking all roads that cost $$$X + 1$$$ or less would be valid too.

So for each midpoint in the binary search, we can check if the current cost is valid or not by connecting components in DSU when an edge cost is more than the current cost we are checking (the more we block the better, so we should not be choosy about what to block or not, if we can block a road then it is either would not change anything or it would disconnect two cities from each other), after that, we can check for connectivity for all forbidden pairs (cities in feuds), if all pairs were disconnected, then the current cost is valid and we search for less, if not, the current cost is invalid and we should search for a higher cost.

Solution Complexity: $$$O(log(10 ^ 9) * m * log(n))$$$