Editorial for DMPG '16 S5 - Pizza Bag


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.

First, let's solve the problem as if the pizza was a line instead of a cycle. (This is subtask 3.) If the goal is to find the longest segment equal in length to or shorter than K, then the length of a segment can be quickly computed by building a prefix sum array on the line. If the sum of the range [a,b] can be found by subtracting position a-1 of the prefix sum array from position b, then for every position e in the line, the largest sum segment ending at e can be computed as the minimum of all positions in the range [e-k,e) in the prefix sum array, subtracted from position e. After building the prefix sum array, a set can be used to solve this (the sliding range minimum query problem) in \mathcal O(N \log K), or alternatively, it can be solved in \mathcal O(N) using a double ended queue.

To solve the problem for a cycle, just arbitrarily choose any starting point, take two periods, and treat it as a line.


Comments

There are no comments at the moment.