×

PROTEPOI - Editorial

Editorialist: Pawel Kacprzak

Easy-Medium

PREREQUISITES:

Greedy, sortings, segments geometry

PROBLEM:

Given a grid of with $N$ rows and $N$ columns, with special square grid of size $K \times K$ in its center, and position of $M$ snakes (vertical of horizontal segments of consecutive cells), where no snakes are inside the special square, the task is to leave minimum number of snakes on the grid (remove the maximum unnecessary snakes), so that the special square will be protected by the remaining snakes. The special square is protected by the snakes if and only if there doesn't exist an arrow that can be shot along a row or a column, which can enter the special square and leave the whole grid on the other side. Notice that arrows can pass only cells not occupied by snakes.

EXPLANATION:

We say that a snake protects a side of the special square if and only if there exists an arrow that can be shot as described in the statement and the snake prevents it either from entering the special square or leaving it on the other side. The first thing to notice is that there is no snake which can protect both a vertical and horizontal side of the special grid at the same time. This is true because snakes are straight segments. Thus the problem can be divided into two separate problems: finding the minimum number of snakes required to protect horizontal sides of the special square and finding the minimum number of snakes required to protect vertical sides of the special square. We'll focus here on the first of these problems because the solution to the other one follows the same idea.

Now, we want to find the minimum number of snakes required to protect horizontal sides of the special square. Let's reformulate the problem a little bit. Snakes denote horizontal segments, and the set of all these segments is $S$. We have also a special horizontal segment $A$ which we want to cover completely by the minimum, in terms of the number of elements, subset of $S$. Notice that $A$ is the segment denoting the top (or the bottom, it doesn't matter, because we only care about horizontal coordinates) side of the special square, and that set $S$ can be computed as the set of the snakes with a non-empty intersection with $A$ on the horizontal axis. For example, as illustrated in the below picture, the set $S$ contains red, blue and orange snakes:

We reduced the original problem to a problem of finding the smallest subset of the given set of horizontal segments $S$, which covers completely the whole segment $A$. This is one of the classical problems, which can be solved greedily. The idea is to sort the segments in $S$ by their left endpoints and process them from left to right in that order trying to cover the left-most not yet covered point of $A$. More specifically, let's assume that $x$ is the left-most not yet covered point of $A$. We examine all segments from $S$ with left endpoint not greater than $x$ and we take to the result the one with the largest right endpoint. Let this largest endpoint be $k$, so we update $x$ to $k+1$ and continue the process until either all points of $A$ are covered, so we have the result, or we examined all segments, which means that there is no way to cover $A$.

The total complexity of this solution is $O(N \cdot \log(N))$ and it's dominated by sorting time. Notice that we need to solve this problem two times: one for horizontal sides of the special square, and second, for the vertical sides of the special square. If at least one of these problems has no solution, we, of course, return $-1$ as the final answer.

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter's solution can be found here.
Tester's solution can be found here.
Editorialist’s solution can be found here.

This question is marked "community wiki".

74485097
accept rate: 12%

19.8k350498541

 1 Hey, I did something like this only, but maybe some cases are not passing , can you give me some cases? My solution - https://www.codechef.com/viewsolution/13867833 answered 29 May '17, 12:44 3★abhi98 11●2 accept rate: 0%
 1 @rahulladda check this test case.output should be 3 but your code is giving -1. 1 7 3 7 1 1 6 1 1 2 3 2 5 2 5 2 1 5 2 5 6 2 6 4 5 6 5 7 7 1 7 4 answered 30 May '17, 13:52 11 accept rate: 0%
 0 @pkacprzak Hey, how can we keep track of the points that have been covered, or not yet covered? In my solution I tried using an array of all 'k' points. I do the same for both horizontal and vertical points that need to be covered. but 'k' can be of the order (10^9)-2. I am getting a TLE. Can you suggest a better way? answered 29 May '17, 12:43 2★rak_9792 11●2 accept rate: 0% There is no need for an array. Initially, set the first uncovered point to the left endpoint of the segment you want to cover. Then, as described in the editorial, if k is the furthest right endpoint of a segment covering x, then set next x (the next point to be covered) to k+1. (29 May '17, 12:51)
 0 Can anybody post some good test cases as I have done the same thing during the contest with nlogn TC and still got the WA.I can't figured out what's wrong with my code Here is my code : https://www.codechef.com/viewsolution/13871262 Thanks in advance answered 29 May '17, 13:29 1 accept rate: 0%
 0 Hey I used similar logic,but got wrong answer would you help me? In program i sort the segment by starting point and chooses the one segment whose starting point is valid and end point is longest here is the link to my code: http://ideone.com/gtN4CV answered 29 May '17, 14:52 1 accept rate: 0%
 0 @durden8055 . Have a look at this test case, actual answer should be "2" but your code displays "-1". 1 7 3 7 1 1 6 1 7 1 7 1 1 2 7 2 1 3 1 5 2 3 2 5 1 6 1 7 6 6 6 6 answered 29 May '17, 14:58 3★abhi98 11●2 accept rate: 0%
 0 @abhi98, got the mistake, thanks !! answered 29 May '17, 15:42 1 accept rate: 0%
 0 I also did the same thing as mentioned in the editorial. Still I was getting WA. I can't figure out what's wrong with my code. Can anybody provide a strong test case or debug my code please? My solution: https://www.codechef.com/viewsolution/13861971 Thanks in advance. answered 29 May '17, 17:00 1 accept rate: 0%
 0 @namenotfound15 Try this case. It should output 3. https://pastebin.com/LqQFgAzi answered 29 May '17, 17:43 0★paphonb 1 accept rate: 0%
 0 Can anyone tell what's wrong here? Tried almost all test cases. Can someone suggest a testcase for which this fails?? https://www.codechef.com/viewsolution/13888974 answered 29 May '17, 18:19 2★rak_9792 11●2 accept rate: 0% It is impossible that you tried all test cases. (29 May '17, 19:12)
 0 The solution links given with the editorial get directed to some error page. @admin Please look into this. Thanks ! :) answered 30 May '17, 01:00 21●2 accept rate: 0%
 0 Can someone please help me in showing where I am going wrong. Its giving WA. I have tried it with the test cases, given in the comments, by @paphonb and @abhi98. It is giving correct answers. Please help. Thanks ! :) Here is my code: https://www.codechef.com/viewsolution/13893020 answered 30 May '17, 03:19 21●2 accept rate: 0%
 0 Can anybody please look why my code is giving Runtime (SIGABRT Error) Thanks in advance:-) answered 30 May '17, 10:55 4★anushi 246●1●7 accept rate: 15%
 0 @aniruddh48 Thanks for replying. Can you please look at the provided test case by you. There are 7 snakes given the first line of input. But it is followed by only six snakes. Please look at it. :) answered 30 May '17, 20:40 21●2 accept rate: 0%
 0 @aniruddh48 Thanks buddy. I got it what you are pointing to. :) answered 30 May '17, 21:26 21●2 accept rate: 0%
 0 @paphonb Got my mistake. Thank you so much! answered 31 May '17, 03:07 1 accept rate: 0%
 0 Can anyone post the correct solution here. answered 31 May '17, 10:15 1 accept rate: 0%
 0 Can anyone tell me what's wrong in my code?? All test cases in this post had pass... Really cannot figure out what I am missing https://www.codechef.com/viewsolution/13956597 answered 01 Jun '17, 19:37 3★kirakira 1 accept rate: 0%
 0 Anyone please tell what's wrong in my code. https://www.codechef.com/viewsolution/14060633 answered 04 Jun '17, 20:16 1 accept rate: 0%
 0 Ok...so, once we have the x = the leftmost point not covered, then we see all those points coveering x and having k maximum,...and then update x=k+1 but then again we will have to see traverse all the points again...this will take O(N^2).Am i right..correct me plz, if i am! answered 04 Jun '17, 21:34 150●5 accept rate: 6%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,719
×1,682
×1,006
×797
×638
×483
×7
×5

question asked: 29 May '17, 11:37

question was seen: 2,548 times

last updated: 04 Jun '17, 21:34