You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

This question is marked "community wiki".

asked 29 May '17, 11:37

pkacprzak's gravatar image

5★pkacprzak ♦♦
74485097
accept rate: 12%

edited 30 May '17, 12:18

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 29 May '17, 12:44

abhi98's gravatar image

3★abhi98
112
accept rate: 0%

edited 29 May '17, 13:00

@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

link

answered 30 May '17, 13:52

aniruddh48's gravatar image

4★aniruddh48
11
accept rate: 0%

edited 31 May '17, 10:52

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

link

answered 29 May '17, 12:43

rak_9792's gravatar image

2★rak_9792
112
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) pkacprzak ♦♦5★

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

link

answered 29 May '17, 13:29

vikesh8860's gravatar image

4★vikesh8860
1
accept rate: 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

link

answered 29 May '17, 14:52

durden8055's gravatar image

4★durden8055
1
accept rate: 0%

edited 29 May '17, 14:53

@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

link

answered 29 May '17, 14:58

abhi98's gravatar image

3★abhi98
112
accept rate: 0%

@abhi98, got the mistake, thanks !!

link

answered 29 May '17, 15:42

durden8055's gravatar image

4★durden8055
1
accept rate: 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.

link

answered 29 May '17, 17:00

namenotfound15's gravatar image

0★namenotfound15
1
accept rate: 0%

@namenotfound15 Try this case. It should output 3.

https://pastebin.com/LqQFgAzi

link

answered 29 May '17, 17:43

paphonb's gravatar image

0★paphonb
1
accept rate: 0%

edited 29 May '17, 17:45

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

link

answered 29 May '17, 18:19

rak_9792's gravatar image

2★rak_9792
112
accept rate: 0%

It is impossible that you tried all test cases.

(29 May '17, 19:12) prakhariitd6★

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

link

answered 30 May '17, 01:00

rahulladda's gravatar image

2★rahulladda
212
accept rate: 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

link

answered 30 May '17, 03:19

rahulladda's gravatar image

2★rahulladda
212
accept rate: 0%

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

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

Thanks in advance:-)

link

answered 30 May '17, 10:55

anushi's gravatar image

4★anushi
24617
accept rate: 15%

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

link

answered 30 May '17, 20:40

rahulladda's gravatar image

2★rahulladda
212
accept rate: 0%

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

link

answered 30 May '17, 21:26

rahulladda's gravatar image

2★rahulladda
212
accept rate: 0%

@paphonb Got my mistake. Thank you so much!

link

answered 31 May '17, 03:07

namenotfound15's gravatar image

0★namenotfound15
1
accept rate: 0%

Can anyone post the correct solution here.

link

answered 31 May '17, 10:15

goyalpradhuman's gravatar image

4★goyalpradhuman
1
accept rate: 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

link

answered 01 Jun '17, 19:37

kirakira's gravatar image

3★kirakira
1
accept rate: 0%

Anyone please tell what's wrong in my code. https://www.codechef.com/viewsolution/14060633

link

answered 04 Jun '17, 20:16

abhishek_019's gravatar image

5★abhishek_019
1
accept rate: 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!

link

answered 04 Jun '17, 21:34

iamabjain's gravatar image

4★iamabjain
1505
accept rate: 6%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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