Editorial for LCC '24 Contest 1 S3 - Graham's Neighbourhood
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:
Suppose we represent a hosue visiting another as a road between them. That means for each house, it is most optimal to draw a rode to either it's direct left or right neighbour.
Notice that between 2 houses that give out candy, there can be at most 1 pair of consective houses that do not have a road in between them. If there are more, that means that there is a group of houses that are not connected to any house that gives out candy.
Thus, we realize that the optimal solution is to connect every house on the line together. However, between 2 houses that give out candy, we remove the road with the longest length.
Comments