PROTEPOI - Unofficial Editorial

Observation : There should be a snake in each row and in each column in the range [(n-k)/2+1,(n+k)/2]. So we will treat horizontally aligned snakes and vertically aligned snakes separately.(Note that vertically aligned snake also covers one cell horizontally and vice versa).
Let p1 = (n-k)/2+1 and p2 = (n+k)/2, H be the array that stores (start,end) for the horizontally aligned snakes, i.e. the starting column(start) and the ending column of a snake(end) and ans be a variable that stores the minimum number of snakes required.

Greedy Approach :

  • Sort the array H according to the starting column(start).
  • Let a variable en be the end point of the snake we have chosen(initially we have not chosen any snake) and mn be the farthest end point of the snake that starts before or at en + 1. en is initialized to p1 - 1 as we do not need any snake in the range [0,p1-1].
  • While traversing through array H, there will be 3 cases :
    1. When H[i].start <= en+1, we just need to update mn = max(mn,H[i].end).
    2. When H[i].start >en+1 and mn=en,that means there will be atleast one column((en+1)th column) left uncovered. So it is impossible to protect the poison and answer is -1.
    3. When H[i].start >en+1 and mn>en, then we know that we can reach atmost till the (mn)th column by choosing a snake. So we will simply update mn = en and increment the number of snakes required,i.e. ans.
    4. We will traverse through H till en reaches to p2(because we dont need any snake in the range [p2+1,n].
    5. After traversal, if en < p2, that means it is impossible and hence answer is -1.

    Similarly, we can apply the same approach for vertically aligned snakes.

    Correctness :

    Consider 2 varibales i,j such that, H[i].start<=en+1, H[j].start<=en+1 and H[i].end < H[j].end. Then the number of elements k(k > i and k < j) that can be traversed by choosing ith snake is a subset of the number of elements traversed by choosing jth element. Hence it is optimal to choose the jth snake(and hence updating en=mn). Thus the greedy approach is correct.

    For implementation details, check my solution.

    Complexity :

    O(NlogN)

    2 Likes

    Really amazing :smiley: keep it up