Questions Tagged With line-sweephttps://discuss.codechef.com/tags/line-sweep/?type=rssquestions tagged <span class="tag">line-sweep</span>enThu, 13 Dec 2018 15:30:23 +0530RNEST(Escape from the Mines)https://discuss.codechef.com/questions/5960/rnestescape-from-the-mines<p>How to approach the problem RNEST? (<a href="http://www.codechef.com/ACMAMR12/problems/RNEST">http://www.codechef.com/ACMAMR12/problems/RNEST</a> ). Naive O(n*n)
approach gets TLE. The AC solutions probably use segment trees or sweep line. Please explain how to approach the problem?</p>coder245Tue, 29 Jan 2013 19:46:03 +0530https://discuss.codechef.com/questions/5960/rnestescape-from-the-minessegment-treeline-sweeprnestsweep line / largest polygonhttps://discuss.codechef.com/questions/8543/sweep-line-largest-polygon<p>Hi, I have a set of segments and I have to calculate the area of the largest polygon which can be build using this segments (the polygon must be enclosed)… sounds like a sweep-line problem but I have no idea how to handle the sweep… any ideas? </p>hansholm1Sun, 21 Apr 2013 15:09:53 +0530https://discuss.codechef.com/questions/8543/sweep-line-largest-polygongeometryline-sweeppolygonareaTABISHOP - Editorialhttps://discuss.codechef.com/questions/7698/tabishop-editorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/TABISHOP">Practice</a><br>
<a href="http://www.codechef.com/COOK32/problems/TABISHOP">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>MEDIUM</p>
<h1>PREREQUISITES</h1>
<p>Ad Hoc, Sweep Line</p>
<h1>PROBLEM</h1>
<p>You are given a chess board with several bishops, and several <b>obstacles</b>. Considering that the movement of the Bishops is blocked by these obstacles, you wish to find the <b>number of cells that are under threat from one or more Bishops</b>.</p>
<p>Note that if a cell is under threat from multiple Bishops, we must count it only once.</p>
<h1>QUICK EXPLANATION</h1>
<p>We can imagine each Bishop to be at the center of an <b>X shaped region</b>. The region is terminated by either the <b>boundary of the chess-board</b> or some <b>obstacle</b>.</p>
<p>We can find the number of cells within this X shaped region.</p>
<p>Now, for all the Bishops together, we can find the <b>sum of of number of cells within their regions of attack</b>. The regions of attack of different bishops may <b>intersect</b> (we can easily handle overlaps, as we will see below). These <b>intersection points</b> have been double counted!</p>
<p>Finding the number of <b>intersection points</b> by use of a <b>sweep line algorithm</b>, we can count and then eliminate them.</p>
<p>The implementation of this approach, can use several simplifications as described below.</p>
<h1>EXPLANATION</h1>
<p><b>Consider bishops and obstacles in white cells and black cells separately</b></p>
<p>We know that bishops in black cells do not share regions of attack with bishops in white cells. Thus, we can consider them as two separate cases for simplicity.</p>
<p>The real benefit of introducing this differentiation is in the following simplification.</p>
<p><b>Tilt the board by 45 degrees</b></p>
<p>Now, each region of attack is a simple <b>plus</b> shaped region, built from a <b>horizontal segment</b>, and a <b>vertical segment</b>. We consider white and black on different boards, hence do not have to worry about how to <b>not consider the intersection of segments from bishops which are rooted on cells of two separate colors</b>.</p>
<p>Consider a board of size <b>5 by 5</b>. The alternate boards that should be considered are shown below</p>
<p>Original Board.</p>
<pre> 1 | 2 | 3 | 4 | 5
----------------------
6 | 7 | 8 | 9 | 10
----------------------
11 | 12 | 13 | 14 | 15
----------------------
16 | 17 | 18 | 19 | 20
----------------------
21 | 22 | 23 | 24 | 25
</pre>
<p>Assuming that the top left cell is colored black, let us look at the arrangement of all the black cells tilted by 45 degrees. We preserve the labels of the cells as showed above to make the mapping obvious.</p>
<pre> | | 1 | |
----------------------
| 11 | 7 | 3 |
----------------------
21 | 17 | 13 | 9 | 5
----------------------
| 23 | 19 | 15 |
----------------------
| | 25 | |
</pre>
<p>Let us look at the arrangement of all the white cells tilted by 45 degrees.</p>
<pre> | 6 | 2 |
-----------------
16 | 12 | 8 | 4
-----------------
22 | 18 | 14 | 10
-----------------
| 24 | 20 |
</pre>
<p>Note how the <b>black</b> board is built from cells numbered odd, and the <b>white</b> board from cells numbered even.</p>
<p><b>Consider horizontal segments and vertical segments</b></p>
<p>Now, in each one of the <b>sub-boards</b> separately (<b>black</b> and <b>white</b>), we can consider the line segments that are attacked by bishops. We know that the segments will be vertical and horizontal.</p>
<p><b>We can count the number of cells in each one of the segments</b>. Next, we must find the <b>number of intersection points</b> caused by these segments. <b>Reducing this</b> from the <b>sum of number of cells in all the segments</b> leads us to the answer.</p>
<p><b>Finding the number of intersections</b></p>
<p>We have <b>N</b> horizontal and <b>N</b> vertical line segments (potentially fewer, because overlapping line segments from different bishops can be <b>merged</b> and considered as single line segment).</p>
<p>We wish to find the number of points at which these line segments <b>intersect</b>. We already know that two line segments that overlap (touch each other sideways) can always be merged and considered as a single segment. Thus, each intersection can only happen between one horizontal segment, and one vertical segment.</p>
<p>Let <b>T</b>, be an augmented binary tree that is aware of the <b>dynamic order index</b> of its members. This can be done in several ways, for example</p>
<ul>
<li>Use a Binary Index Tree (or Fenwick's Tree)<ul>
<li>add 1 at the value that is inserted</li>
<li>subtract 1 at the value that is deleted</li>
<li>Now, sum until each value represents the order index of the value</li>
</ul>
</li>
<li>Use a Binary Tree with number of descendants stored at each node<ul>
<li>update this number with each insert / delete</li>
<li>add the number of descendants for each left sub-child that is skipped in the traversal from root to the node. This represents the order index of the value.</li>
</ul>
</li>
</ul>
<p>Both the techniques above support each operation (add, delete and check-index) in <b>O(log N)</b> time, where we may add at most <b>N</b> items.</p>
<p>In the case of Fenwick's Tree, because the number of values that are added is much smaller than the range of values, we must <b>relabel</b> the values to a smaller range [1 ... number of values].</p>
<p>Let <b>E</b> represent the set of events for a <b>Sweep Line algorithm</b>. We will consider the following events</p>
<ul>
<li>Vertical segment start</li>
<li>Vertical segment end</li>
<li>Horizontal segment encountered</li>
</ul>
<p>We can iterate through the list of events <b>sorted by the x-coordinate</b>. We handle the events as follows</p>
<ul>
<li>Vertical segment start<ul>
<li><b>Insert y coordinate of the segment in T</b></li>
</ul>
</li>
<li>Vertical segment end<ul>
<li><b>Delete y coordinate of the segment in T</b></li>
</ul>
</li>
<li>Horizontal segment encountered<ul>
<li>Add to result, the number of values in T between the start and end of the horizontal segment.</li>
<li>The number of values can be calculated as</li>
<li><b>T.OrderIndex(end) - T.OrderIndex(start) + 1</b></li>
</ul>
</li>
</ul>
<p>Thus, we will know the number of intersection points.</p>
<p>The overall complexity of the algorithm would be <b>O(N log N)</b>, where <b>N is the number of bishops</b>.</p>
<h1>SETTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/COOK32/Setter/TABISHOP.cpp">here</a>.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/COOK32/Tester/TABISHOP.cpp">here</a>.</p>gamabuntaMon, 25 Mar 2013 00:19:32 +0530https://discuss.codechef.com/questions/7698/tabishop-editorialcook32order-statisticeditorialad-hocmedium-hardline-sweepTRIQUERY - Editorialhttps://discuss.codechef.com/questions/6380/triquery-editorial<h1>Problem Link:</h1>
<p><a href="http://www.codechef.com/problems/TRIQUERY">Practice</a><br>
<a href="http://www.codechef.com/FEB13/problems/TRIQUERY">Contest</a></p>
<h1>Difficulty:</h1>
<p>Medium</p>
<h1>Pre-requisites:</h1>
<p>line-sweep, rank-query DS</p>
<h1>Problem:</h1>
<p>Given <strong>N</strong> points <strong>(Xi, Yi)</strong>, and <strong>Q</strong> queries <strong>(x, y, d)</strong>, find for each query how many of the <strong>N</strong> points lie within or on the boundary of the triangle formed by the triangle A(x+d, y), B(x,y), C(x,y+d).</p>
<h1>Explanation:</h1>
<p>This problem is solved by offline processing of the queries and using a line-sweep. Unlike most line-sweep problems, where you would sweep a (vertical) line across the X-axis (or a horizontal line across the Y-axis), and keep an active set etc, in this problem, you sweep a line of the form "x+y=c" across the plane. (Note that the slope of the hypotenuse of our query-triangle is parallel to such a sweep-line and hence the motivation for such a choice).</p>
<p><img alt="Query Triangle" src="http://codechef.com/download/TRIQUERY%20Illustration.png">
In the figure shown, we want to find the number of points in or within the boundary of <strong>L2</strong>, <strong>B</strong> and <strong>G</strong>. If we are processing lattice points in the plane in order of sweep-line, and have so far seen points below <strong>L2</strong>, we just need to remove from this set of seen points, the ones that are below <strong>G</strong> or to the left of <strong>B</strong>.</p>
<p>This suggests that we have an active set of "seen points", wherein at time T, their X+Y <= T (i.e. T defines our sweep-line). From this set of seen points, we want to remove those whose X <= x, or whose Y <= y. If we store the seen points in 2 Binary Indexed Trees (BIT): one for their X coordinate, one for their Y coordinate, and query for <em>how many points <= x</em>, or <em><= y</em>, then using principle of inclusion-exclusion, we get that the required answer = Total seen points - num(points left of <strong>B</strong>) - num(points below <strong>G</strong>) + num(points left of <strong>B</strong> <em>and</em> below <strong>G</strong>).</p>
<p>How do we find num(points left of <strong>B</strong> and below <strong>G</strong>)? <br>
The answer lies in the line <strong>L1</strong>. When our sweep-line was at <strong>L1</strong>, we have: Total number of points seen so far = points either left of <strong>B</strong> or below <strong>G</strong>. Again by Inclusion-Exclusion, we have Total points seen so far = num(points left of <strong>B</strong>) + num(points below <strong>G</strong>) - num(points left of <strong>B</strong> <em>and</em> below <strong>G</strong>). From this, we can calculate num(points left of <strong>B</strong> <em>and</em> below <strong>G</strong>).</p>
<p>Thus, our algorithm is as follows: <br>
For each of the <strong>N</strong> lattice points <strong>(X, Y)</strong>, associate an event "Add <strong>(X,Y)</strong> to active set at time point <strong>X+Y</strong>". <br>
For every query <strong>(x, y, d)</strong>, associate 2 events. Event 1 is: "Find num(points having X<=<strong>x</strong> and Y<=<strong>y</strong>) at time point <strong>x+y</strong>". <br>
Event 2 is: "Answer required query at time point <strong>x+y+d</strong>". <br>
Lets call the first kind of event as "Add point" event, the second kind of event as "L1-type" event, and the third kind as "L2-type" event.</p>
<p>Finally, care has to be taken to ensure that we include the boundary of our triangle formed by B, G, L2. This is done by breaking ties of time-point in the manner of L1-type event comes before any Add-point event which comes before any L2-type event.</p>
<h1>Setter's Solution:</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/February/Setter/TRIQUERY.cpp">here</a></p>
<h1>Tester's Solution:</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/February/Tester/TRIQUERY.c">here</a></p>pragrameTue, 12 Feb 2013 18:20:46 +0530https://discuss.codechef.com/questions/6380/triquery-editorialfeb13line-sweepmediumtriqueryeditorialNPIN - Editorialhttps://discuss.codechef.com/questions/18369/npin-editorial<h1>PROBLEM LINK</h1>
<p><a href="http://www.codechef.com/problems/NPIN">Practice</a><br>
<a href="http://www.codechef.com/JULY13/problems/NPIN">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>HARD</p>
<h1>PREREQUISITES</h1>
<p>Computational Geometry<br>
<a href="http://en.wikipedia.org/wiki/Pick's_theorem">Pick's Theorem</a><br>
<a href="http://akundu.tripod.com/CyrusBeck.pdf">Cyrus Beck's Line Clipping Algorithm</a><br>
<a href="http://www.cs.tufts.edu/comp/163/notes05/seg_intersection_handout.pdf">Sweep Line Algorithm</a>
<a href="http://www.cs.tufts.edu/comp/163/notes05/seg_intersection_handout.pdf">Line Segment Intersection</a></p>
<h1>PROBLEM</h1>
<p>You are given a convex polygon whose vertices are <b>lattice points</b> on the <b>x-y plane</b>. You are also given several <b>line segments</b> in the <b>x-y plane</b> whose endpoints are <b>lattice points</b>. On each <b>lattice point</b> on a line (and the endpoint of a line) and also <b>on or inside the polygon</b>, you place a <b>Needle</b>. Lines include the ones that form the polygon.</p>
<p>On all other <b>lattice points</b> inside the polygon, you place a <b>Pin</b>. Find the number of <b>Needles</b> placed, and the number of <b>Pins</b> placed.</p>
<h1>EXPLANATION</h1>
<p><a href="http://en.wikipedia.org/wiki/Pick's_theorem">Pick's Theorem</a> states that</p>
<pre>Area of polygon =
number of internal <b>lattice points</b>
+ number of boundary <b>lattice points</b> / 2
- 1
</pre>
<p>We can find the number of <b>lattice points</b> on a line segment from <b>(x<sub>1</sub>,y<sub>1</sub>) to (x<sub>2</sub>,y<sub>2</sub>)</b> as</p>
<pre>GCD( abs(x<sub>1</sub> - x<sub>2</sub>), abs(y<sub>1</sub> - y<sub>2</sub>) )
</pre>
<p>We do not place needles on the portion of the line segment that lies outside the polygon. Thus, we must <a href="http://akundu.tripod.com/CyrusBeck.pdf">clip</a> the line segments to <b>lattice points</b> that lie inside the polygon.</p>
<p>The linked resource uses the <b>parametric notation of a line segment</b>. All the calculations can be done purely on integers to allow for finding the clipped lines very accurately. This may be achieved by maintaining the value of the parameter as a <b>fraction</b> - integer numerator and denominator.</p>
<ul>
<li>Lines that are parallel to an edge of the polygon and on, or outside the polygon, can be simply ignored</li>
</ul>
<p>The expected time complexity for this step was <b>O(N*P)</b>, where <b>P</b> is the number of edges in the polygon.</p>
<p>Doing so, we are able to calculate the number of needles on the boundary of the polygon, and on the line segments inside the polygon. But, several line segments may have <b>intersection points</b> among them which are also <b>lattice points</b>. We must reduce our count of needles by the number of such intersections.</p>
<p>Intersections within a set of lines can be found using a <b>plane sweep algorithm</b>. The idea is elementary in books that deal with <b>Computational Geometry</b>. I personally found <a href="http://www.cs.tufts.edu/comp/163/notes05/seg_intersection_handout.pdf">this</a> resource very useful in implementing the plane sweep algorithm to report the intersection points.</p>
<p>Implementing this algorithm correctly and accurately (handling all the <b>degeneracies</b> possible) is the most difficult part of solving this problem. It is very well researched though, so there is no scarcity in resources describing a solution.</p>
<p>The expected time complexity for this step was <b>O((N + I) log N)</b>, where <b>I</b> is the number of intersection points.</p>
<p>Lastly, the number of pins can be found by reducing the count of needles from the number of internal <b>lattice points</b>, found using the Pick's Theorem above.</p>
<h1>SETTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/July/Setter/NPIN.cpp">here</a>.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Will be uploaded shortly.</p>gamabuntaMon, 22 Jul 2013 04:46:14 +0530https://discuss.codechef.com/questions/18369/npin-editorialgeometryhardline-clippingjuly13editorialline-sweepURBANDEV - Editorialhttps://discuss.codechef.com/questions/87389/urbandev-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/URBANDEV">Practice</a><br>
<a href="http://www.codechef.com/NOV16/problems/URBANDEV">Contest</a></p>
<h1>DIFFICULTY:</h1>
<p>Medium</p>
<h1>PREREQUISITES:</h1>
<p>sweep line, segment tree</p>
<h1>PROBLEM:</h1>
<p>Given <strong>N</strong> segments on Cartesian plane, each one is either vertical or horizontal, count the number of intersection points between any pair of the segments.</p>
<h1>EXPLANATION:</h1>
<h2>General explanation</h2>
<p>Let's imagine vertical line moving from very far left (say X=-inf) to very far right (say X=inf) -let's call this line as "sweeping line"-, at every moment this line is intersecting with some subset of horizontal segments so we can keep track with this subset as long as the sweeping line is moving, now whenever that line meets vertical segment, say it's endpoints are (X1,Y1) and (X2,Y2) such that X1=X2 and Y1 < Y2, then the answer to its query is the number of horizontal segments which are now intersecting with the sweeping line and their Y-coordinates is between Y1 and Y2.</p>
<p>so if we can find a way to quickly count number of horizontal segments in the subset which have Y-coordinates between any given range then we can answer the query of all vertical segments. however, we also need to support add/erasing segments from the subset.</p>
<p>note that we can do the same idea but with a horizontal sweeping line to answer the queries of horizontal segments.</p>
<h2>representing the sweeping line and its movement technically</h2>
<p>We want to find a way to store the subset of horizontal segments which are currently interesting with the sweeping line and support quickly adding new segment to this set and support removing existing segment from this set.</p>
<p>This can be done by consider the sweeping line as an array <strong>A</strong> of length 10<sup>5</sup> + 1 if there's currently segment intersecting with sweeping line at Y-coordinate equal to <strong>Y</strong> then we have <strong>A[Y] = 1</strong> otherwise, we have <strong>A[Y] = 0</strong>, when we want to answer a query to vertical segment then we just need to find the sum of elements in this array inside a given range, so can use segment tree or Fenwick tree data structure.</p>
<p>to simulate the movement of the sweeping line we are only interested in some events that will occur during the movement of the sweeping line which are</p>
<ul>
<li>
<p>The sweeping line meets with a vertical segment, because we need to answer its query</p>
</li>
<li>
<p>sweeping line intersect with new horizontal segment</p>
</li>
<li>
<p>sweeping line stop intersecting with a horizontal segment </p>
</li>
</ul>
<p>so we create an array of events that will store all events of any of the above 3 types and sort them according the X-coordinates where it will happen, then we simply do the events in that order.</p>
<h2>Corner Cases</h2>
<ul>
<li>The problem said "at least two other directions to continue their trip" so we should intersecting points that has extensions in 3 or 4 directions but not 2, that means an intersection point can be endpoint of at most of segment but not two, so for simplicity we can include the case that has 2 extensions then exclude them alone, so for now an intersecting can be an endpoint of 2 segments</li>
<li>when we sort the events in case two or more events have same X-coordinates then we put first events of adding new horizontal segments first, then the events of querying vertical segments and lastly the events of erasing horizontal segments, this is because an intersection point can be an endpoint of a segment.</li>
<li>also because an intersection point can be an endpoint of a segment, then the range sum query should be inclusive.</li>
</ul>
<h1>SETTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/NOV16/Setter/URBANDEV.cpp">here</a>.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/NOV16/Tester/URBANDEV.cpp">here</a>.</p>kingofnumbersSat, 12 Nov 2016 10:41:14 +0530https://discuss.codechef.com/questions/87389/urbandev-editorialmediumurbandevsegment-treeeditorialline-sweepnov16Sweep Line Algorithmhttps://discuss.codechef.com/questions/5989/sweep-line-algorithm<p>I want to learn about sweep line algorithm.Can someone suggest me a good resource or tutorial to learn about it?
Thanks, in advance.</p>saikrishna173Wed, 30 Jan 2013 22:26:21 +0530https://discuss.codechef.com/questions/5989/sweep-line-algorithmline-sweepFLYMODE - Editorialhttps://discuss.codechef.com/questions/89649/flymode-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/FLYMODE">Practice</a> <br>
<a href="https://www.codechef.com/LTIME43/problems/FLYMODE">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a></p>
<h1>DIFFICULTY:</h1>
<p>SIMPLE</p>
<h1>PREREQUISITES:</h1>
<p>Sorting, sweep line</p>
<h1>PROBLEM:</h1>
<p>For a list of $N$ positive consecutive heights: $h_1, h_2, \ldots, h_N$ denoting some heights at which a plane was during its flight and knowing that between heights $h_i$ and $h_{i+1}$ it was flying the shortest path between these height, which means it was at every height between these two ones once, find the maximum integer $K$, such that the plane was $K$ times at some height during the flight.</p>
<h1>QUICK EXPLANATION:</h1>
<p>For every pair of consecutive heights $h_i, h_{i+1}$ add each of these heights as either opening or closing time event to a list of all events, let’s call it $E$, happening in time. Sort $E$ and process it using sweep line keeping track of the number of current opened events that has not been closed. The result is the maximum number of opened events during this process.</p>
<h1>EXPLANATION:</h1>
<h1>Subtask 1</h1>
<p>In this subtask $N$ is at most $1000$ and we know that each $h_i \leq 1000$. This allows the following approach:</p>
<p>Let $K$ be the result to the problem and $H$ be the set of some candidate heights such that the plane was at some $h \in H$ exactly $K$ times. If $H$ is not too big, then we can for each $h \in H$ check how many times the plane was at height $h$ by iterating over all two consecutive input heights $h_i, h_{i+1}$ and counting the number of such pairs that contain $h$. The answer to the problem is the maximal such count. This approach has the time complexity of $O(|H| \cdot N)$, but how to chose $H$? Well, we can take advantage of the fact that $h_i \leq 1000$. Important thing to notice is that the height on which the plane was the most number of times can be a real number, not integer. However, the crucial observation is that we can put to $H$ all positive integers not greater than $1000$ and also floating points exactly between them, so $1.5, 2.5, \ldots$. Is turns out that these candidate heights are sufficient because all input heights are integers.</p>
<h1>Subtask 2</h1>
<p>In the second subtask $N$ can be at most $10^5$ and each $h_i \leq 10^9$, so method described above will take too much time. The crucial observation to approach the problem is to notice that if $K$ is the answer to the problem, there exists height $h$ for which there exists $i$ such that $\min(h_i, h_{i+1}) \le h \le \max(h_i, h_{i+1})$ and the plane was at height $h$ exactly $K$ times. Thus the problem can be reduced to finding a point which is covered by most of these height pairs and returning the maximum size of such cover. Let’s think of pairs of consecutive heights as segments from the smaller to the larger height. Notice that changing height from $h_i$ to $h_{i+1}$ corresponds to one such segment. Moreover, the reduced problem can be easily solved using a <a href="https://en.wikipedia.org/wiki/Sweep_line_algorithm">sweep line</a> algorithm by sorting all endpoints of the segments, then processing them from left to right counting the number of opened segments and returning the maximal such count during this process. The complexity of this solution is $O(N \cdot \log(N))$ dominated by the sorting phase.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><br>
Setter's solution can be found <a href="https://www.codechef.com/download/Solutions/LTIME43/Setter/FLYMODE.cpp">here</a>. <br>
Tester's solution can be found <a href="https://www.codechef.com/download/Solutions/LTIME43/Tester/FLYMODE.cpp">here</a>. </p>pkacprzakSat, 31 Dec 2016 18:41:47 +0530https://discuss.codechef.com/questions/89649/flymode-editorialsortingflymodeltime43simpleeditorialline-sweepCHEFCIRC - Editorialhttps://discuss.codechef.com/questions/90268/chefcirc-editorial<p><a href="https://www.codechef.com/problems/CHEFCIRC">Practice</a> <br>
<a href="https://www.codechef.com/JAN17/problems/CHEFCIRC">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/iscsi">Istvan Nagy</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></p>
<h1>Difficulty:</h1>
<p>Medium</p>
<h1>Pre-Requisites:</h1>
<p>sweepline, binary search, polar angle, intersection of 2 circles</p>
<h1>Problem Statement</h1>
<p>You are given $N$ points. Find minimal radius $R$ of the circle, which contains at least $K$ points inside or on the circumference.</p>
<h1>Explanation</h1>
<h1>Subtask 1</h1>
<p>$N$ is less or equal than 200. Well-optimized $O(N^4)$ can pass and $O(N^3 log (max(|X|,|Y|)/EPS))$ too.
Describe $O(N^4)$ solution below.</p>
<p> Will call circle interesting if it contains at least one point from the $N$ points, and if we move this circle in any direction this circle will contain another set of points. Which circles are interesting? That circles which are constructed from 3 points(if they don't lie on the same line), or from 2 points(if segment which connects they are the diameter of the circle). We need to go over all interesting circles and check the number of points which lies inside of them. </p><p>Let's use next observation, if there are at least $K$ points lies inside a circle of the radius $R$, then at least $K$ points lies inside any circle with a radius bigger than $R$. Also if $K$ points don't lie inside the circle of $R$, then $K$ doesn't lie inside any circle with a radius smaller than $R$. The function of a radius is monotonic, we can use binary search for solving this problem. Rephrase problem, we have radius $R$, find a maximal number of points which lies inside of a circle with radius $R$ and compare it with $K$. </p>
<p> Use this observation for solving problem in $O(N^3 log (max(|X|, |Y|)/EPS))$ </p>
<p>Will iterate over a pair of points $i$ and $j$, if the distance between them more than EPS, will try to carry out through them the circles(this points will lie on the circumference), there are exactly 2 circles which can be drawn between 2 distinct points. There are at most $2*N^2$ circles, and after building circles, iterate over all points and check if they lie inside of the circles in $O(1)$, hence $O(N^3)$ complexity for checking with radius $R$. </p>
<h1>Subtask 2</h1>
<p>For this subtask use scanline approach and binary search by radius. The first step is binary search by radius, secondly iterate over point $i$ with coordinates ($X$,$Y$) which will lie on the circumference of the circle, then the center of the circle lies somewhere with coordinates ($X+R*cos(theta)$, $Y+R*sin(theta)$). For every point $j != i$ find all possible angles theta which satisfied condition that point j lies inside of circle of radius $R$ and centered in point ($X+R*cos(theta)$, $Y+R*sin(theta)$).
</p>
<p>
Let we have point $i$ and $j$ ($i != j$), how to find all theta's described above? At first, if $\\sqrt((X_{i}-X_{j})^2+(Y_{i}-Y_{j})^2)$ (Euclidian distance between point $i$ and $j$) more than $2*R$, there are no theta's satisfied condition. In another case, let's say that we have two circles of radius $R$ centered in points $i$ and $j$. Find points where they intersect, in every point of their intersection, can be placed a circle of the radius $R$, and it will contain both points $i$ and $j$. All theta's which satisfied condition lie within some sector of the circle centered in point $i$ and with the radius $R$.
</p>
<p> Let's find intersection between two circles centered in points $i$ and $j$ with radiuses $R$. Call these points as $A$ and $B$(in case if circles intersect in one point, assume that $B$ = $A$). Let $P_{a}$ will be <a href="http://mathworld.wolfram.com/PolarAngle.html">polar angle</a> for vector $(A.x-X_{i}, A.y-Y_{i})$, and $P_{b}$ for vector $(B.x-X_{i}, B.y-Y_{i})$, possible two cases:
</p><li> $P_{a} <= P_{b}$, then theta can lie in the range $I$ = [$P_{a}; P_{b}$]</li>
<li> $P_{a} > P_{b}$, then theta can lie in the range $I$ = [$P_{a}; 2*PI$) U [$0; P_{b}$]</li>
<p></p>
<p> If theta lies inside the range $I$ then point $j$, will be inside the circle. Now we can reduce this problem to another well-known problem, there are segments, we need to find the point which covered with the maximal number of segments. It can be solved with standard sweep line technique. </p>
<p>The overall time complexity of this approach is $O(N^2 * log N * log (max(|X|,|Y|)/EPS))$.</p>
<h1>Solution:</h1>
<p>Setter's solution can be found <a href="http://www.codechef.com/download/Solutions/JAN17/Setter/CHEFCIRC.cpp">here</a> <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/JAN17/Tester/CHEFCIRC.cpp">here</a></p>
<p><strong>Please feel free to post comments if anything is not clear to you.</strong></p>mgchWed, 18 Jan 2017 04:37:49 +0530https://discuss.codechef.com/questions/90268/chefcirc-editorialbinary-searchmediumchefcircgeometryjan17editorialline-sweepLIGHT - Editorialhttps://discuss.codechef.com/questions/2267/light-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/LIGHT">Practice</a><br>
<a href="http://www.codechef.com/SEP12/problems/LIGHT">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>MEDIUM</p>
<h1>PREREQUISITES</h1>
<p>Binary Search, Greedy Algorithm, Geometry</p>
<h1>PROBLEM</h1>
<p>You are given several light sources along a road (road is x-axis). Each light source casts isosceles triangles with their base over the road. We wish to find the highest height at which we can fly a plane from x = L to x = R such that line segment from (L, h) to (R, h) is completely within the light - that is, within one or more of the isosceles triangles cast by the light sources.</p>
<h1>QUICK EXPLANATION</h1>
<p>A useful technique while solving any problem is to identify that the solution w.r.t. one of the variables is monotonic. In this problem there is some height H, above which we cannot find a segment (L, h) to (R, h) satisfying the constraint. But, below this H, for all h, (L, h) to (R, h) will always be in light.</p>
<p>Thus, we can perform a binary search on h to find the largest height which is <strong>valid</strong>.</p>
<h1>EXPLANATION</h1>
<p>If the segment from (L, h) to (R, h) is completely within the light triangles, we call h <strong>valid</strong>.</p>
<p>To check if h is valid we can do the following
</p><pre>function verify(h)
Let A be a list of items, where item is a pair of numbers
for each source of light, s
if height[s] < h then ignore this source
else
base = ((Y[s] - h) * tan Z[s])
lx = X[s] - base
rx = X[s] + base
A.push(lx, 1)
A.push(rx, -1)
A.push(L, 0)
A.push(R, 0)
</pre><p></p>
<p>So, for each light source, we find the intersection of the light source with a line at height h.</p>
<p>We store these intersection points in a list along with "1" for the points at which a light source is added, and "-1" for the points at which a light source is ended.</p>
<p>Note that we also add L and R to A, but without any delta (that is their pair value is 0).</p>
<p>We know that now the number of light sources illuminating each segment in A are constant. By adding L and R to A, we have ensured that we consider the line segments that start / end at L (or R) separately.</p>
<p>The following snippet shows the complete <strong>verify</strong> procedure.</p>
<pre>function verify(h)
Let A be a list of items, where item is a pair of numbers
for each source of light, s
if height[s] < h then ignore this source
else
base = ((Y[s] - h) * tan Z[s])
lx = X[s] - base
rx = X[s] + base
A.push(lx, 1)
A.push(rx, -1)
A.push(L, 0)
A.push(R, 0)
sort A
Let cnt = 0 be number of active sources of light for the next segment
Let la = -infinity be the endpoint of the last seen segment
for i = 0 to A.size
Let x = A[i].first
Let del = A[i].second
if x > L and
x <= R and
x > la and
cnt == 0
then return "Invalid"
la = x
cnt += del
return "Valid"
</pre>
<p>We sort A to consider each line segment one by one. This is equivalent to a line sweep algorithm from left to right touching all the intersection points (that we stored in A). For each segment we see if <code>x</code> lies within the line segment. Now, if the line segment from <code>la</code> to <code>x</code> was of positive length, then we know that there is some (or all) of the line segment between <code>la</code> to <code>x</code> which belongs to the region <code>L</code> to <code>R</code>.</p>
<p>If <code>cnt</code> for that segment was 0, then that segment was not lit and we return "Invalid".</p>
<p>Otherwise we update the <code>cnt</code> and <code>la</code> for the next iteration.</p>
<p>If we find that no such dark segment exists, we return "Valid".</p>
<p>Hence we can call <strong>verify</strong> from within a binary search to find the largest possible h.</p>
<p>You need to be careful about precision errors and angle format conversions (degree / radians) for the respective language's math library.</p>
<h1>SETTERS SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2012/September/Setter/LIGHT.cpp">here</a></p>
<h1>TESTERS SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2012/September/Tester/LIGHT.c">here</a></p>gamabuntaTue, 11 Sep 2012 15:27:57 +0530https://discuss.codechef.com/questions/2267/light-editorialsep12geometryline-sweepeditorialbinary-searchINSQ16G - Editorialhttps://discuss.codechef.com/questions/87310/insq16g-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/INSQ2016/problems/INSQ16G">Contest</a><br>
<a href="https://www.codechef.com/problems/INSQ16G">Practice</a></p>
<p><strong>Author:</strong> <a href="www.codechef.com/users/mmaks">Manish Kumar Sinha</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/pakhandi">Asim Krishna Prasad</a> <br>
<strong>Editorialist:</strong> <a href="www.codechef.com/users/mmaks">Manish Kumar Sinha</a></p>
<h1>DIFFICULTY:</h1>
<p>EASY-MEDIUM</p>
<h1>PREREQUISITES:</h1>
<p>Geometry, Line-sweeping</p>
<h1>PROBLEM:</h1>
<p>Given the corners of a number of polygons, calculate the area and perimeter of the polygon. Also the sides of polygons are parallel to X-axis and Y-axis and none of the polygons intersect. </p>
<h1>EXPLANATION:</h1>
<p>First thing to observe that sides are parallel to the coordinate axes and polygons are non intersecting, so at a particular value of X or Y, there must be even number of points. So take a vertical line to sweep and maintain active set of points with y ordinate only. At a particular value X, first count the number of points, if it is odd then given region cannot be closed, hence print "Impossible". Otherwise calculate the area till this X, by iterating through the points in active set.<br></p>
<p><b>Calculating Area till X:</b>
<br>Maintain prevX (previous value of X ordinate in case you are sweeping vertical line). At sweep line x = A, iterate through the active set of points(sorted by y-ordinate) and take every pair of points and calculate area by<br> </p><center>Area += (A - prevX) * (active[i+1] - active[i]);<br>i += 2; </center><p></p>
<p>For calculating the perimeter, we have to sweep first using vertical and hen horizontal line. For a vertical sweep line, at a particular X, if we find a point having y ordinate already in the active set, then this a side of a polygon, hence add its length to the perimeter. For vertical sweep line, all the sides which are parallel to x-axis will be added to the perimeter. So for sides parallel to Y-axis, sweep horizontal line and do same.</p>
<h1>SOLUTION:</h1>
<p><a href="http://codechef.com/download/Solutions/INSM16TS/INSQ16G.cpp">Setter's Solution</a></p>vikky_codderThu, 10 Nov 2016 16:01:39 +0530https://discuss.codechef.com/questions/87310/insq16g-editorialgeometryline-sweepinsomniamnniteditorialCK87DANC Editorialhttps://discuss.codechef.com/questions/115159/ck87danc-editorial<h1>Problem Link:</h1>
<p><a href="https://www.codechef.com/COOK87/problems/CK87DANC">Practice</a></p>
<p>Contest</p>
<p><strong>Author</strong>: <a href="https://www.codechef.com/users/mhammad1">Mohammad Shahhoud</a> & <a href="https://www.codechef.com/users/saeed_sryhini">Said Sryhini</a> </p>
<p><strong>Tester</strong>: <a href="https://www.codechef.com/users/kingofnumbers">Hasan Jadouh</a></p>
<p><strong>Editorialist</strong>: <a href="https://www.codechef.com/users/saeed_sryhini">Said Sryheni</a></p>
<h1>Difficulty:</h1>
<p>Medium.</p>
<h1>Prerequisites :</h1>
<p>Prefix XOR, Trie Tree, Minimum Range Lazy Segment Tree, Sweep Line.</p>
<h1>Problem:</h1>
<p>Given an array of $N$ elements and an integer $M$, you are to answer $Q$ queries. In each query you are given two integers $L$ and $R$. You are to find the minimum range $[i, j]$, that falls completely inside the range $[L, R]$, and the logical $XOR$ of its elements is no less than the given integer $M$.</p>
<h1>Explanation:</h1>
<h2>Main algorithm:</h2>
<ol>
<li>
<p>For each index $i$ find the smallest range that ends at $i$, and the $XOR$ of its elements is no less than $M$ using a trie tree.</p>
</li>
<li>
<p>Build a minimum range lazy segment tree whose leaves are the given queries sorted in non-decreasing order by their ending $R$.</p>
</li>
<li>
<p>Answer the queries offline. Sweep over the indexes and the left side of each query.</p>
</li>
<li>
<p>When encountaring the start of a query activate its corresponding location inside the segment tree.</p>
</li>
<li>
<p>When encountaring an index, get the smallest range that starts at $i$ (let's denote the end as $j$), and lazy update all the queries that end in the range $[j, \infty[$ with the length of the range $[i, j]$.</p>
</li>
<li>
<p>Iterate over all the queries and get their answer through a query to the segment tree.</p>
</li>
</ol>
<h2>Extended Explanation:</h2>
<p>First let's find a more efficent way to calculate the $XOR$ of all the elements inside a given range. We can do so by calculating the prefix $XOR$ for each index in the given array. Let's denote such an array as $Pref$, where $Pref_i = Pref_{i - 1} \oplus D_i$. Now the logical $XOR$ for all the elements in the range $[L, R]$ can be calculated as $Pref_R - Pref_{L - 1}$.</p>
<p>Consider the binary representation of the values of $Pref$ over a 30-bit representation. Create a trie tree, where each node has two children ${0, 1}$ denoting the bits of the elements from the given array. The root of the trie tree will contain the most significant bit, while the leaves will contain the least significant bits.</p>
<p>Iterate over array's elements from left to right. For each index $i$, we need to find the largest index $j$ such that $Pref_i - Pref_{j - 1} \le M$. In order to do so, for each index first insert the value of $Pref_{i - 1}$. Now we need to find the largest index inside our trie tree, such that the above mentioned operation holds true. In other words we need to query the formed trie tree passing the value of $Pref_i$. While iterating over the trie, let's define the corresponding bit of $M$ as $B_m$ and the corresponding bit of $Pref_i$ as $B_i$. Also, for each node let's store the value of the maximum index whose binary representation passes through this node, let's denote it as $MX$. In each node we may encounter one of the following two conditions:</p>
<ol>
<li>
<p>$B_m = 1$. In this case we have no other choice but to go to the child whose value is $1 - B_i$. This is because to get the value of $1$ out of an $XOR$ operation, we need to have two different bits.</p>
</li>
<li>
<p>$B_m = 0$. In this case we have two option:</p>
<ul>
<li>Either go to the child whose value is $B_i$, because the $XOR$ of the same bit is $0$. Note that in this case the calculated value still equals to $M$.</li>
<li>Or go to the child whose value is $1 - B_i$. This will give us a resulting bit that equals to $1$. In this case the formed value is already greater than $M$, and there's no need to further investigate the subtree of the current node since we already know the value of the largest index that passes through this node, and it's stored in the variable $MX$, so we simply return it.</li>
</ul>
</li>
</ol>
<p>Obviously when reaching a leaf node, we need to return the value of $MX$.</p>
<p>So far we manages to understand how to efficentely handle step number $1$. Now the problem reduces to: Given ranges $[i, j]$ and queries $[L, R]$, find for each query the smallest range $[i, j]$ that falls completely inside the range $[L, R]$.</p>
<p>Moving to step $2$ We build a minimum range lazy segment tree whose leaves are the given queries sorted in non-decreasing order by the value of their $R$. The initial value of each query must be $-\infty$.The purpose of such segment tree will be explained below.</p>
<p>Sweep over both the left side of each query $[L, R]$ and the left side of the calculated ranges $[i, j]$.</p>
<ul>
<li>
<p>When encountering a query $[L, R]$ activate its corresponding leaf by setting its value to $\infty$.</p>
</li>
<li>
<p>When encountering a range $[i, j]$ we know for sure that all the queries whose left side is smaller than $i$ has already been activated. Among these queries, only the ones that end at $R >= j$ actually covers the current range. Since the queries $[L, R]$ inside our segment tree are sorted in non-decreasing order of their end $R$, we can lazy update all these queries in our segment tree. In other words update all the queries whose ending $R$ is in the range $[j, \infty[$. Please pay special attention that $2$ queries may have the same ending, so to find the first query whose $R$ is no less than $j$ we perform a simple binary search opearation over the queries array which is sorted in non-decreasing order by their end.</p>
</li>
</ul>
<p>After sweep operation is finished, we can now simply iterate over all the queries by the order given in the input, and query our segment tree for their value.</p>
<p>Time Complexity: $O((N + Q) . (log(Q) + log(N)) + N . log(10^9))$</p>
<p>Check setter and tester solutions for the implementation.</p>
<p><a href="https://ideone.com/iTVEwK">Solution 1</a></p>
<p><a href="https://ideone.com/65wGW2">Solution 2</a></p>saeed_sryhiniMon, 23 Oct 2017 03:23:10 +0530https://discuss.codechef.com/questions/115159/ck87danc-editorialrmqtrielazypropagationsegment-treecook87line-sweepCK87MEAD - Editorialhttps://discuss.codechef.com/questions/115103/ck87mead-editorial<h1>Problem Link:</h1>
<p><a href="https://www.codechef.com/problems/CK87MEAD">Practice</a><br>
<a href="https://www.codechef.com/COOK87/problems/CK87MEAD">Contest</a></p>
<p><strong>Author</strong>: <a href="https://www.codechef.com/users/mhammad1">Mohammad Shahhoud</a> & <a href="https://www.codechef.com/users/saeed_sryhini">Said Sryhini</a> <br>
<strong>Tester</strong>: <a href="https://www.codechef.com/users/kingofnumbers">Hasan Jadouh</a><br>
<strong>Editorialist</strong>: <a href="https://www.codechef.com/users/mhammad1">Mohammad Shahhoud</a></p>
<h1>Difficulty:</h1>
<p>Medium-Hard</p>
<h1>Prerequisites :</h1>
<p>Centroid Decomposition, Sweep Line, Binary Indexed Tree, Simple Math.</p>
<h1>Problem:</h1>
<p>Given a tree, each node $i$ has value $A_i$, find the number of node pairs($u$,$v$) such that the <strong>median</strong> of values in the path from $u$ to $v$ (inclusive) is at most $X$ and the <strong>mean</strong> is at least $Y$.</p>
<h1>Explanation:</h1>
<p>The current described solution based on the setter solution, so you can check the setter solution for the implementation.</p>
<p>We will discuss many solutions that are going to lead us to the correct fast solution.</p>
<h2>Slow solution:</h2>
<p>Suppose we will loop on each pair of nodes ($u$) and ($v$), so now we have the end nodes fixed, we can do DFS from the starting node and get all the nodes in the path from ($u$) to ($v$) and put them into array, sort the array and get the mean and median, so the time complexity of this solution will be: $O(N^3.Log(N))$ which actually doesn't fit in the time limit.</p>
<h2>Better solution:</h2>
<p>We can actually do an optimization for the previous code by writing some math equations: </p>
<p>Let $A_i$ be the value of node $i$, so if we create two arrays called $medianValue$ and $meanValue$ of length $N$ where: </p>
<p>$medianValue[i] = (A[i] <= X) ? +1 : -1$
$meanValue[i] = A[i] - Y$</p>
<p>The $medianValue$ of node $i$ is <strong>+1</strong> if the node value is less or equal to $X$ and <strong>-1</strong> otherwise, and the $meanValue$ is $A[i] - Y$, but what's the point of creating those two arrays? </p>
<p>To check the median condition of the array, we can simply sum the values of the node values on the path from ($u$) to ($v$) and let's call this value $sumMedian$, so if the $sumMedian$ value is greater or equal to zero, that means the number of values less than or equal to $X$ are greater than or equal to the number of values greater than $X$, so the median is a number less than or equal to $X$. To check the mean condition we can write these equations: </p>
<p>$\sum_{i = 1}^{N}A[i] / N \ge Y$ ==> $\sum_{i = 1}^{N}A[i]\ge Y * N$ ==> $\sum_{i = 1}^{N}A[i] - Y * N \ge 0$ ==> $\sum_{i = 1}^{N}(A[i]-Y) >= 0$ ==> $\sum_{i = 1}^{N}meanValue[i] >= 0$</p>
<p>So the problem conditions are correct if: $sumMedian \ge 0$ <strong>and</strong> $sumMean \ge 0$ </p>
<p>Now after all that, we can do DFS from each node $i$ passing the sum of $meanValue$ and $medianValue$, checking of the $sumMedian$ and $sumMean$, we can get a solution of complexity: $O(N^2)$. </p>
<h2>Intended Solution:</h2>
<p>We will call a pair ($u$,$v$) is <strong>good</strong> if the conditions of median and mean hold.
For better solution, we can do <strong>centroid decomposition</strong> for the tree.</p>
<h2>What is Centroid Decomposition?</h2>
<p>It's a technique used for dividing the tree into trees, each new tree has size at most $N/2$, and the node that divides the tree called centroid, calculating the number of good-pairs passing through this centroid, then call the same procedure on the new trees. you can read more about centroid decomposition from: <a href="https://threads-iiith.quora.com/Centroid-Decomposition-of-a-Tree">Quora Thread</a> .</p>
<p></p><center><img alt="tree" src="https://codechef_shared.s3.amazonaws.com/download/upload/COOK87/CK87MEAD.png"></center><p></p>
<p>Now let's for simplicity consider a binary tree case, in the previous picture, the centroid divides the tree to two trees, but how can we get the number of good-pairs passing through the centroid? </p>
<p>By doing DFS from the centroid, we can get for each node the value $sumMean$ and $sumMedian$, where $sumMean[i]$ is the sum of $meanValue[i]$ from the centroid to node $i$ (<strong>without centroid value</strong>), and $sumMedian[i]$ is the sum of $medianValue[i]$ from the centroid to node $i$ (<strong>without centroid value</strong>), now we have to find:
$sumMedian[u] + sumMedian[v] + medianValue[centroid] \ge 0$ ==> $sumMedian[u] \ge -sumMedian[v] - medianValue[centroid]$</p>
<p><strong>and</strong></p>
<p>$sumMean[u] + sumMean[v] + meanValue[centroid] \ge 0$ ==> $sumMean[u] \ge -sumMean[v] - meanValue[centroid]$</p>
<p>where ($u$) is a node from tree1 and ($v$) is a node from tree2</p>
<p>Let's consider ($sumMean[u]$, $sumMedian[u]$) as a point in <strong>2D Cartisian Plane</strong>, so for each node ($v$) from tree2 we have to find the number of points from tree1 in the rectangle that its bottom-left corner is ($-sumMean[v]-meanValue[centroid]$, $-sumMedian[v]-medianValue[centroid]$) and its upper-right corner is ($Infinity$, $Infinity$) and to solve this efficiently, we can do it using sweep line and Binary Indexed Tree.</p>
<h2>Sweep Line:</h2>
<p>First we have to convert the 2D problem to 1D problem for easier and more efficient solution, and we can do that by sorting all points by their $X$ values.
Second, we note that each point has two events:
1. Add event: we add the point to the <strong>BIT</strong>.. The add event at point($sumMean[v]$)
2. Query event: we query to get the number of good points with the current point.. The query event at point($-sumMean[v] - meanValue[centroid]$).</p>
<p>So each point $v$ has two events, and each event has ($type, mean, median, index$) where $type$ is the type of the event, $mean$ is $sumMean[v]$ for add events and ($-sumMean[v] - meanValue[centroid]$) for query events, $median$ is $sumMedian[v]$ for add events and ($-sumMedian[v] - medianValue[centroid]$) for query events, index is the index of the owner point of the event.</p>
<p>After that, we add all $2N$ events into array, sort them by their mean value and we add all the median values into the <strong>BIT</strong>.</p>
<p>Loop from left to right on events, if the current event type is update, we remove the median value from the <em>BIT</em>, and if the current event type is query, we query on the <em>BIT</em> to find the good points with this point, the query interval is [$Event.median$, $Infinity$]. </p>
<p><strong>Important</strong>: Note that for query events, all $meanValue[u]$ that are less than the event mean value have removed, and all $meanValue[u]$ that are greater than or equal to the event mean value are still exist in the <em>BIT</em>, so the mean constraint is always true for each query event.</p>
<p>There is a case when some point $u$ add point $v$ to the answer and $v$ add point $u$ to the answer (so here we count the same pair twise), so we can handle this case by removing the point from BIT when we query it.</p>
<p>There is a problem in this solution; we said before that we want to find the number of paths <em>passing through</em> the centroid, but here we counted also the paths that don't, so we call the same above procedure for each resulting tree to remove those paths from the answer.</p>
<h1>The time complexity of this solution:</h1>
<p>The levels of centroid tree is at most $Log(N)$ levels (each time we get the <strong>half size</strong> of the tree).</p>
<p>On each level we loop through all the nodes, calculate the $2N$ events and sort them with complexity $O(N.Log(N))$</p>
<p>Last step, we loop on all events, add $N$ points and remove $N$ points , query $N$ points, each (add, remove, query) operation is $Log(N)$, so the complexity is: $N.Log(N)$ </p>
<p><strong>The total complexity</strong>: $O(N.Log(N).Log(N))$</p>
<p><a href="http://www.codechef.com/download/Solutions/COOK87/Setter/CK87MEAD.cpp">Solution 1</a><br>
<a href="http://www.codechef.com/download/Solutions/COOK87/Tester/CK87MEAD.cpp">Solution 2</a> </p>mhammad1Sat, 21 Oct 2017 23:36:37 +0530https://discuss.codechef.com/questions/115103/ck87mead-editorialeditorialfenwick-treecook87medium-hardcentroid-decompline-sweepck87meadmhammad1CHEFRES - EDITORIALhttps://discuss.codechef.com/questions/136251/chefres-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/CHEFRES">Practice</a> <br>
<a href="https://www.codechef.com/LTIME64A/problems/CHEFRES">Contest: Division 1</a> <br>
<a href="https://www.codechef.com/LTIME64B/problems/CHEFRES">Contest: Division 2</a> </p>
<p><strong>Setter:</strong> <a href="https://www.codechef.com/users/kingofnumbers">Hasan</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/teja349">Teja Vardhan Reddy</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/taran_1407">Taranpreet Singh</a> </p>
<h1>DIFFICULTY:</h1>
<p>Simple</p>
<h1>PREREQUISITES:</h1>
<p>Maps, Binary search or ordering queries would do fine.</p>
<h1>PROBLEM:</h1>
<p>Given $N$ disjoint intervals $[L_i, R_i)$ and $M$ query times $P_i$, we need to print the minimum waiting time from query point to any time belonging to any interval, at or after query time.</p>
<h1>SUPER QUICK EXPLANATION</h1>
<ul>
<li>Sort intervals as well as query time, maintain two pointers and for every interval, iterate from earliest query time $X$ and answer is $L_i - T_i$ if query time is before interval, otherwise $0$ for every query time such that $R_{i-1} \leq X < R_i$.</li>
<li>Alternate online solution is for every query $X$, to use binary search to find earliest interval such that $X < R_i$. If query time lies in interval, Wait time is zero, else $L_i-X$.</li>
<li>Query times at or after $R_n$ will wait forever (if possible without food :D)</li>
</ul>
<h1>EXPLANATION</h1>
<p>Since intervals are disjoint, every query point can belong to at most one interval, which we need to find, in order to find out the waiting time. Suppose we know that for query time $X$, the required interval is $[L, R)$. How to calculate waiting time?</p>
<p>See the secret box.</p>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p>If $X$ belong to $[L, R)$, Food is delivered immediately and thus, waiting time is zero.</p>
<p>Otherwise, we will have to wait for Interval to begin, that is, wait from time $X$ up to time $L$, resulting in waiting time $L-X$.</p>
</div></div>
<p>This is enough to solve sub task 1, since we can check for every query time, waiting time for all intervals ending after query time and print the minimum of all waiting times, but this results in $O(N*M)$ complexity, which is too slow for sub task 2.</p>
<p>We need to find this interval fast. We know that the interval we are seeking is in fact the earliest interval which ends after query time. </p>
<p>It is ideal to sort the intervals, whenever we need to find such earliest, first, last intervals. Sorting is almost used in every problem which involves intervals.</p>
<p>Anyways, after sorting, if interval j is required interval, we know that either $j==1$ of $R_{j-1} \leq X < R_j$. This can be used as condition for binary search, since all interval before jth interval has $R_i \leq X$ and all intervals after jth interval has $R_i < X$.</p>
<p>Otherwise, we can sort the query points and use two pointers, one for query points and one for interval index. For every interval, assign minimum times to all query points which are before $R_i$, not assigned answer yet.</p>
<p>In case answer is not assigned to query, customer has to survive without food forever.</p>
<h1>Time Complexity</h1>
<p>For binary search solution, Time complexity is $O((M+N)*logN)$. <br>
For Offline solution, Time complexity is $O(N*logN +M*logM)$.</p>
<p>Proving complexity is not hard for this problem, though may be referred in secret box.</p>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p>In binary search solution, sorting cost $O(N*logN)$ and each query take $O(logN)$ time, thus total time $O((M+N)*logN)$ </p>
<p>For offline solution, sorting dominates time complexity. After sorting, rest part takes only $O(M+N)$ time.</p>
</div></div>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/LTIME64/setter/CHEFRES.cpp">Setter's solution</a><br>
<a href="http://www.codechef.com/download/Solutions/LTIME64/tester/CHEFRES.cpp">Tester's solution</a> <br>
<a href="http://www.codechef.com/download/Solutions/LTIME64/editorialist/CHEFRES.java">Editorialist's solution</a> </p>
<p><strong>Edit:</strong> Until above links are not working, You may refer solution <a href="https://ideone.com/Ls5gd5">here</a>.</p>
<p>Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)</p>taran_1407Sun, 30 Sep 2018 01:05:59 +0530https://discuss.codechef.com/questions/136251/chefres-editorialbinary-searchtaran_1407ltime64easychefresline-sweepIMPO - EDITORIALhttps://discuss.codechef.com/questions/142027/impo-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/IMPO">Practice</a> <br>
<a href="https://www.codechef.com/SNCKEL19/problems/IMPO">Contest</a> </p>
<p><strong>Setter:</strong> <a href="https://www.codechef.com/users/jafarbadour">Jafar Badour</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/taran_1407">Taranpreet Singh</a> </p>
<h1>DIFFICULTY:</h1>
<p>Hard</p>
<h1>PREREQUISITES:</h1>
<p><a href="https://en.wikipedia.org/wiki/Computational_geometry">Computational Geometry</a> and Integrals. Familiarity with Line-Sweep Algorithms would be helpful.</p>
<h1>PROBLEM:</h1>
<p>Given two projections of a body, one on XY plane having $N$ vertices and other on XZ plane having $M$ vertices, Find the maximal possible area of the body or determine if no such body exists.</p>
<h1>QUICK EXPLANATION</h1>
<ul>
<li>Any valid body shall exist if and only if minimum and maximum values of x coordinates of both projections coincide.</li>
<li>We can consider the body as a number of extremely thin sheets merged together to form the body. By multiplying the area of such sheets by a corresponding thickness of sheets, we can compute the volume of such body.</li>
<li>We can divide the body into parts by each x-coordinates of both polygons and use definite integration to compute the volume of the body between every two consecutive x-coordinates.</li>
</ul>
<h1>EXPLANATION</h1>
<p>First of all, let us check <strong>whether any valid solid body exists or not, for the given two projections</strong>.</p>
<p>See, If we project the shadow of a body on the XY plane, it is nothing, but the hull of points formed by setting z coordinate as zero. Similarly, the shadow on the XZ plane is the hull of points formed by setting y-coordinate zero. (Note that hull here may be concave too, but surely not self-intersecting).</p>
<p>This way, the only thing we have is that we have x-coordinates preserved in both projections. The only check we have for a valid body is that both minimum x-coordinate and maximum x-coordinate should coincide for both polygons. </p>
<p>The reason is simple, If one polygon has a point with x coordinate smaller than the minimum of x-coordinates of the second polygon, It means, that the body has some solid part below minimum of x-coordinate of the second polygon, which cannot be true, as the second polygon is the projection of body on XZ plane. A similar argument holds for maximum x-coordinate too.</p>
<p>Thus, the two polygons become self-contradictory, if minimum and maximum values of x-coordinates of both polygons do not coincide.</p>
<p><strong>Calculating maximal volume</strong></p>
<p>Let us divide the body into thin sheets formed by taking $x = c$ for all $minX \leq c \leq maxX$. We can see, that the volume of the body is just summation of the area of each sheet multiplied by its width.</p>
<p>Suppose, area of sheet at $x$ is given by $f(x)$. We can see that we need to find the maximal volume, and areas of sheets at different $x$ are independent of each other. So, we want to maximize the area of each sheet too. The only way we can maximize the area of the sheet is when our body covers the whole area allowed by projections. Let $g(c)$ be the length of projection at $x = c$ on XY plane and $h(c)$ be length of projection at $x = c$ on XZ plane. It can be seen that $f(x) = g(x)*h(x)$ where $g(c)$ is the sum of length of line segments of line $x = c$ strictly lying inside first polygon while $h(c)$ is the sum of lengths of line segments of line $x = c$ lying strictly inside second polygon.</p>
<p>Now, The problem here is, that we cannot run this process for each possible value of $x$. To help us, calculus comes to our rescue. We want to compute the sum of $f(x)$ for all values in range $[x1,x2]$, $x1 \leq x2$. It is a well-known problem and can be easily solved using definite integration, as follows.</p>
<p>Suppose we can write both $g(x)$ and $h(x)$ as linear functions of x. Say $g(x) = a+b*x$ and $h(x) = c+d*x$. We get</p>
<p>$\begin{equation}
f(x) = (a+b*x)*(c+d*x) = (b*d)*x^2+(a*d+b*c)*x+a*c
\end{equation}$</p>
<p>Integrating both sides, we have</p>
<p>$\int_{x1}^{x2} f(x) = \left | \frac{b*d*x^3}{3}+\frac{(a*d+b*c)*x^2}{2}+a*c*x \right |_{x1}^{x2} = F(x2)-F(x1)$</p>
<p>where $F(x) = \frac{b*d*x^3}{3}+\frac{(a*d+b*c)*x^2}{2}+a*c*x$</p>
<p>Now, we divide the body into separate parts by planes, given by $x = x_i$ for all distinct $x_i$ present in either of the polygon. See the image below. Orange lines show partitioning polygon into parts for each distinct x coordinate.</p>
<p><img alt="alt text" src="https://discuss.codechef.com/upfiles/impo1_8yom3Jc.jpg"></p>
<p>To represent the shaded area, we can add area below the line AB, subtract area below line AF, add area below line EF and subtract area below line DC, all in the range $[x1,x2]$. This can be achieved by just adding or subtracting equations of these lines, getting a linear function over x. </p>
<p>In the Image, for point $x1$, $g(x1)$ is the sum of lengths of the two left purple segments while at $x = x2$, $g(x)$ is the length of the purple segment at the right side. It can be seen, that if we try to draw line $x = x3$, $x1 \leq x3 \leq x2$, we shall obtain sum of lengths of segments lying inside polygon as $g(x3-x1)$.</p>
<p>This can be generalized into three dimension by considering each distinct x out of all points and finding linear functions $g(x)$ and $h(x)$ which hold between each consecutive pair of x coordinate by adding a line into function when left end of the segment is to the left of $x1$ and removing it when its right end is also to the left of $x1$ for both polygons and calculating value of $f(x)$ in range $[x1, x2]$ using integration as explained above.</p>
<p>Adding or removing a line segment can be represented as operations over the slope and constant term when both line segment to be added, and the function $g(x)$ are expressed in point-slope form.</p>
<p>Still in doubt? Refer to setter's solution for details.</p>
<p><strong>Learning Resources</strong></p>
<ul>
<li><a href="https://www.hackerearth.com/practice/notes/computational-geometry-i-1/">Computational Gemoetry basics</a></li>
<li><a href="https://www.hackerearth.com/practice/math/geometry/line-sweep-technique/tutorial/">Line Sweep Algorithms</a></li>
<li><a href="https://www.intmath.com/applications-integration/2-area-under-curve.php">Area under the curve problem (in 2-dimension)</a></li>
<li><a href="http://www.cut-the-knot.org/Curriculum/Calculus/StraightLine.shtml">Equations of a line</a></li>
</ul>
<h1>Time Complexity</h1>
<p>Time complexity is $O(N*logN+M*logM)$ per test case due to sorting.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/SNCKEL19/setter/IMPO.cpp">Setter's solution</a><br>
<a href="http://www.codechef.com/download/Solutions/SNCKEL19/tester/IMPO.cpp">Tester's solution</a> </p>
<p>Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)</p>taran_1407Thu, 13 Dec 2018 15:30:23 +0530https://discuss.codechef.com/questions/142027/impo-editorialtaran_1407hardcomputational-geometryintegralssnckel19line-sweepimpo