Questions Tagged With triqueryhttps://discuss.codechef.com/tags/triquery/?type=rssquestions tagged <span class="tag">triquery</span>enTue, 12 Feb 2013 18:20:46 +0530TRIQUERY:giving REhttps://discuss.codechef.com/questions/6241/triquerygiving-re<p>I'm getting a runtime error SIGSEGV in the problem whereas its working fine on the sample input.What could be the possible reasons I've already checked if the array indices are correct or not.Where am I going wrong?</p>jaskaran_1Thu, 07 Feb 2013 21:33:20 +0530https://discuss.codechef.com/questions/6241/triquerygiving-reruntimetriqueryWhy in TRIQUERY there were no successful subbmission in C?https://discuss.codechef.com/questions/6336/why-in-triquery-there-were-no-successful-subbmission-in-c<p>Can any one tell me why there were no successful submissions in C in TRIQUERY,ROOM CORNER and other problems in february long contest...Is it something related to any disadvantage of C..??? please tell </p>amitupadhyayMon, 11 Feb 2013 15:17:38 +0530https://discuss.codechef.com/questions/6336/why-in-triquery-there-were-no-successful-subbmission-in-cacsubmissionroom_cornertriqueryvacationTRIQUERY - 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-sweepmediumtriqueryeditorial