PROTEPOI - Editorial

PROBLEM LINK:

Practice
Contest

Author: admin3
Testers: Hasan Jaddouh
Editorialist: Pawel Kacprzak

DIFFICULTY:

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:

alt text

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.

1 Like

@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?

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

1 Like

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.

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

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

@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

@abhi98, got the mistake, thanks !!

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.

@namenotfound15 Try this case. It should output 3.

https://pastebin.com/LqQFgAzi

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

It is impossible that you tried all test cases.

The solution links given with the editorial get directed to some error page. @admin Please look into this. Thanks ! :slight_smile:

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 ! :slight_smile:

Here is my code:
https://www.codechef.com/viewsolution/13893020

Can anybody please look why my code is giving Runtime (SIGABRT Error)

Link :https://www.codechef.com/viewsolution/13879398

Thanks in advance:-)

@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

1 Like

@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. :slight_smile:

@aniruddh48 Thanks buddy. I got it what you are pointing to. :slight_smile:

@paphonb Got my mistake. Thank you so much!

Can anyone post the correct solution here.