PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
CYCLE-FINDING, BINARY SEARCH, SPARSE TABLE
PROBLEM:
There is a country with n cities arranged in a circle. The length of the path connecting city i and (i + 1) mod n is l_{i}. You start at city 1. Each day, you can run at most x kilometres. However, after each day, you must end up in one of the cities. Determine the minimum number of days before you run at least y kilometres.
EXPLANATION:
This problem can be solved in different ways. Some of the ways which are unoptimized can lead to a solution for the smaller subtasks. I’ll describe a full solution here.
Firstly, we can detect if the answer is -1 by just going one round and see if we get stuck forever at one town (the length of road for next town is higher than x). Thus, from now on, we assume the task is always possible.
Suppose we’re at city i, which city is the next that we’ll visit? We can calculate how many rounds we go from city i. Then, we can binary search to find the last town we’ll arrive at. We can do this for each city in O(n\log n) total. Now, the key is that if we start from town 1, and keep moving, eventually after at most n + 1 days, we’ll end up at one of the towns we’ve visited before. Thus, we now have a cycle, i.e. after every few days we’ll return back to the same position.
Thus, we can divide y by the total length travelled for each cycle and calculate the number of cycles we have to make. Then, we can calculate the number of days needed to finish the last few kilometres of the whole run. This gives us an O(n \log n) solution for this problem. You can see the details for this solution from the tester’s solution.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.