Editorial for TLE '17 Contest 3 P2 - Sectors
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
We note that in order for Fax to take the shortest path, there is no option but for Fax to try to head directly to the next sector he must visit.
For of the points, we find the location of the next sector Fax needs to visit by brute-force checking sectors to the left and right of the current sector. When we find the next sector, we stop and count how many sectors we passed in between.
Time Complexity:
For of the points, we can simply store the location of each sector in the line. Instead of brute-force checking the location of the next sector, we simply look it up.
Make sure that 64-bit integers are used.
Time Complexity:
Comments