What is the lowest number of irrigators (circles) needed to cover the surface of a foliage (rectangle)? (competitive programming)

Question

I participated in a test and, in one of the problems, I did not get the total score of the question, one of the test cases gave Wrong Answer, but I could not identify exactly my error.

The statement of the problem:

N sprayers are installed on lawn strips of L meters in length and W meters in width. Each spray is installed on the central line of the grammar range. For each sprayer its position is provided as being the distance from the leftmost side of the centre line and also its operating radius.

What is the lowest number of sprayers connected to water the entire lawn strip?

Entree

The input consists of up to 35 cases. The first line for each case contains the integers N, L and W being 1 N 10000, 1 L 107, and 1 W 100. The next N lines contain 2 integers giving the x (0 x L) position and the r (1 r 1000) operating radius of the sprayer.

Exit

For each test case the output should be the fewest number of sprayers needed to water the entire lawn strip. If it is impossible to water the whole lane the outlet shall be -1.

Input example

8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4
3 10 1
3 5
9 3
6 1
3 10 1
5 3
1 1
9 1

Output example

6
2
-1

the idea basically of the code

• It is noted that the useful area of the circle to cover the length of the foliage of length l is the rectangle inscribed to the circumference with the vertices on the sides of the foliage. Each of these rectangles entered in the circle shall be an interval varying from X1=x-sqrt(r 2 - (w/2) 2) up to x2=x+sqrt(r 2 - (w/2) 2)

• Insert each interval into the vector and sort in ascending order of X1

• iterate the vector:

• i) if the first value found is greater than 0, returns -1

• ii) whenever the next range X1 in the vector is within the covered area (covered), the covered area is updated or not, depending on the range, we therefore include or not this interval in the count

• iii)If the foliage extension L is covered, we print the interval count if we do not print -1

My code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#define fori(x, y) for(int i = x; i < y; ++i)
using namespace std;
int numcirc(vector < pair <double, double> > &v, int l){
    double cover = v[0].second;
    int cont = 1;
    if(v[0].first>0) return -1;
    else {
        fori(1, v.size()){
            if(v[i].first > cover) return -1;
            else{
                int t=i;
                double _cover = cover;
                while(v[t].first<=cover && t<v.size()){ //queremos incluir os intervalos de maior alcance
                    _cover=max(_cover, v[t].second);
                    t++;
                }
                if(_cover>cover){
                    cont++;
                    cover=_cover;
                }
                i=t-1; 
            }
            if(cover>=l) return cont;
        }
    }
    return -1;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int n, l, w, x, r;
    double x1, x2;
    while(cin >> n >> l >> w){
        vector < pair< double, double > > v;
        fori(0,n){
            cin >> x >> r;
            if((double)r > (w/(double)2)){
                x1 = (double)(x - sqrt(abs(r*r - 0.25*w*w)));
                x2 = (double)(x + sqrt(abs(r*r - 0.25*w*w)));
                v.push_back(make_pair(x1, x2));
            }
            else{
                v.push_back(make_pair(10000001, 0.1)); //se r<=w/2, então não serve para cobrir a folhagem
            }
        }
        sort(v.begin(), v.end());
        cout << numcirc(v, l) << "\n";
    }
    return 0;
}

I could not have access to the test cases. What could be causing the Wrong Answer?

Answer 1

As you yourself noticed, this problem can be reduced from coverage of area for coverage of segments. To level the playing field, I will explain this transformation. And the area, amazingly, is not relevant to the question by a simple detail: the statement assured that all the sprayers will be right in the center.

So the land that is provided to us is something like this:

Generally speaking, you will only find these following 3 types of circles on that centerline:

1. the first is a circle that has a smaller irrigation diameter than W
2. the middle circle is one that has a diameter greater than W
3. the last circle is that which has an irrigation diameter identical to W

In this type of case, the points furthest from the center line of the rectangle are those that are most difficult to irrigate. If that point is watered, I have a guarantee that the entire vertical segment associated with that fixed point is also watered.

So, therefore, our problem ends up being transformed into covering these extreme points. That is, covering an entire segment.

So how do I turn the problem from areas of circles within the rectangle to segments?

First, let’s understand how each type of circle will be projected on the bottom segment of the rectangle (could use symmetrically the upper, just chose a convenient projection to make the drawing)?

The first type of circle does not reach the edge, so it is not useful in watering on the bottom edge and is always unnecessary.

The second type will project an entire range, as illustrated below:

The radius of the circle was illustrated in red, the projected segment of the circle was indicated in cyan. The calculation to know where this segment starts and ends is already in the question: [ x-sqrt(r^2 - (w/2)^2) , x+sqrt(r^2 - (w/2)^2) ], where x is the position of the spray, r its radius and w the width of the field.

How did you arrive at these figures? If you make a segment from the center of the circle to the bottom of the rectangle in a perpendicular manner, you will notice that it will fall exactly in the middle of the segment. Thus, as it is perpendicular, to join this segment, one of the radii and take the segment of the perpendicular segment will obtain a rectangular triangle. The hypotenuse is known, the radius of the circle, r; one of the catects is also known, which is the length of the perpendicular segment from the center of the circle to the rectangle, which is half the width of the field, so w/2; leaving then the other cathode to calculate the length that is sqrt(r^2 - (w/2)^2). So if I take the point from the center of the circle and walk to the left, I get the point to the left of the segment as being x-sqrt(r^2 - (w/2)^2), and if you walk to the right x+sqrt(r^2 - (w/2)^2).

The third circle type will add only one point on the lower segment. As we are dealing with a finite number of circles, the union of many dots will never make a segment, so this type of spray also will not contribute to irrigation, as well as the first type of spray.

That said, let’s start building the algorithm?

First, we’ll need to read all the dots. Then we will discard the circles that will not contribute to the interval; that is, we will be left with circles whose rays are strictly larger than half the width. So we turn the filtered circles into intervals.

Okay, now we just have intervals and we want to know the smallest set of those intervals that cover a whole segment. Do you know what we can use to model intersections of intervals? An interval graph!

Yes, now I’m turning the problem into a graph problem. How to assemble this graph?

An interval graph is a way of representing, in graph, segments and intersections. Each segment is a vertex and the existence of intersections between two intervals is represented as an edge. So, with the graph mounted, we need to get out of some gap that contains the 0 (origin) and, just navigating the edges, arrive at some interval that contains the L (destination). If not possible, either because there is no gap containing the 0 for departure, either because there is no point of arrival that contains the L or because the graph is disconexus, then return -1.

Here on the network have some interesting questions that address the problem of interval graphs. The ones I remember at the time:

• Machine Scheduling - Graph Theory
• How to identify an invalid graph for operator allocation problem per machine?
• Algorithm O(n log n) to identify contiguous intervals given a range list

In fact, I suggest reading in this order I have put, which coincides with the chronological order of publication

The first step is to find the starting vertex. Regardless of anything, the starting point needs to encompass the starting point 0. Therefore, I must consider as the candidate vertex at the start every interval whose leftmost value is <=0. Similarly to the arriving vertex, right-most value >=L.

Now, how to define these points in more assertive ways? For the starting point, the one that covers up to the right maximum will have full coverage over any other starting candidate point, so only the one whose right most value is the highest is left. Similarly, the point of arrival is the one whose leftmost value is the smallest.

There is the special case that the starting point encompasses the output; in this case, there is also the possibility that my source/destination detector will find distinct points of origin and destination, but it is trivial to check whether only the source sprayer would be enough to cover everything. For this case, just return 1 and go to the next entry.

Defined origin and destination, we need the edges to navigate the graph. A priori, an interval graph is an undirected graph. However, we can do some optimizations and turn our interval graph into a directed acyclic graph.

I’ll add an edge of the range [c1, f1] for halftime [c2, f2] if and only if there is an intersection between these intervals and the second interval ends after the first interval and the second interval does not fully encompass the first. That is, if c2 <= f1 (there needs to be intersection) and f2 > f1 (the second interval necessarily ends after the first interval) and c2 > c1 (the first interval has a piece prior to the second interval). Obviously, sorting the intervals by their value to the left in an increasing way allows us to make several optimizations in the construction of the edges

Assembling this graph, directed even, just run any algorithm with the shortest distance between vertices (consider all edges with weight 1) from the point of origin to the point of destination. If it is not possible to reach the destination, the exit must be -1. Otherwise the output is the distance found plus one.

---

From what I understand from your approach, you tried to do something more greedy. However, the greedy strategy to work needs to decide very calmly whether or not to enter the next interval. From what I could see, the strategy of choosing the next element you used was really adequate (I look forward to all intervals that have some intersection with what has been covered so far). But the choice of starting point is always fixed, you do not try to optimize it to take as a starting point the one that contains the 0 and goes as far as possible. Then, yes, you would have a sweet tooth solution and no backtracking.

I also noticed that you add unnecessarily to the list points that I’ve made out, making them a burden on ordering that would be unnecessary (but that ultimately would not be significant).