I was trying to solve this problem, and I understood the O(NLogN) solution, but here on the usaco guide is also said that an O(N) solution exist, does someone that has solved the problem know the answer?
It’s briefly described in the official analysis.
1 Like
Sorry but I really can’t find the official analysis, could you send a link to it?
see the USACO Guide link you sent above
Thank you, found it, but I still don’t get it, how do i find which range does a station cover in the optimal solution in O(1)?
The idea is to maintain a stack of stations where each station in the stack is the closest station to some nonempty portion of the highway. Iterate over the stations s from left to right. As the analysis mentions, repeatedly pop the top station from the stack if its portion becomes empty (more formally, if a is second from the top of the stack and b is at the top of the stack, we have that x_a<x_b<x_s, and b can be popped from the stack if every point in the highway is closer to a or s than b). Then add s to the stack.
Implementation: Submission #284584 :: oj.uz
Added this problem to requested missing solutions · Issue #4165 · cpinitiative/usaco-guide · GitHub in case anyone wants to provide a more complete explanation.
1 Like