Editorial for LCC '22 Contest 2 S3 - Round Nuts


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.

Author: ji_mmyliu

Let's sort all the points by their distance from the origin. The problem is then reduced to the longest subarray with a bluntness less than or equal to B.

Since the bluntness of a subarray is the difference between the distances of the left and rightmost points in the subarray, this problem can be solved using a two-pointers approach.

Time complexity: \mathcal{O}(N \log N).

Alternatively, a binary search approach can be taken by considering all positions for the left endpoint. For each left endpoint, perform binary search to find the rightmost point that won't make the bluntness exceed B.

Time complexity: \mathcal{O}(N \log N).


Comments

There are no comments at the moment.