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

×

QRECT - Editorial

2
2

Problem link : contest practice

Difficulty : Hard

Pre-requisites : 2D data structures, segment trees

Solution :

Let's start with the following claim: two rectangles intersect if and only if their projections on the coordinate axes intersect. This is an observation that isn't hard to come up with, and that can be easily reasoned.

Let's consider the following problem, where we have to manage answering two types of queries:

  • Add a segment, denoted by its' endpoints x and y;
  • Count the number of segments that intersect with the segment, denoted by the endpoints x and y.

This problem can be solved with the following approach:

  • We keep track on the total number of the segments and all the leftmost and the rightmost endpoints of the segments. For these purposes, one can use segment tree;
  • When we need to calculate the number of the segments that intersect with the given one (let's denote its' the leftmost and the rightmost endpoints by L and R respectively), we can simply subtract the number of the segments that don't intersect with the given one from the total number of the segments. The number of the segments that don't intersect with the given one is: the number of the segments with the leftmost coordinate greater than R plus the number of the segment with the rightmost coordinate smaller than L. Calculating the sought number of segments can be done now with a segment tree, that was already mentioned above.

How to calculate the number of the rectangles that don't intersect with the given one (denoted by its' projections Xl, Xr and Yl, Yr)? From the first glance, we might say that is: the total number of the rectangles, minus the number of rectangles with the X-axis projection, not intersecting [Xl, Xr], minus the number of rectangles with the Y-axis projection, not intersecting [Yl, Yr]. But this is wrong, because some of the rectangles might be subtracted twice. To be exact, those that don't intersect with the both of the projections.

There are four symmetric cases for such rectangles. Let's consider one of these cases, for example those when the both top/right most coordinates of the rectangle (and the projection respectively) are smaller than the bottom/left most coordinates of the rectangle (and the projection as well). Actually, we can simply calculate the number of such rectangles by counting the number of the rectangles with the top-right corner inside the rectangle (1, 1, Xl-1, Yl-1). So now the problem becomes a standard one and you only have to:

  • Add a point on the plane;
  • Calculate the number of the points inside the axes-parallel rectangle.

There are generally a lot of ways to do it. Take a look at the setter's/tester's solutions for the details in case you're unfamiliar how to do so. Though, there are really a lot of ways, so everyone can find the most convenient one for himself. The tester prefers 2D Fenwick tree+SQRT decomposition. This approach is capable of achieving the maximal runtime of ~0.7 on the given test cases.

The described case is one of four, the rest has exactly the same logic. The main difficulty of the problem is to code everything clear and correct, but only the practice helps to become stronger in the "techical" problems :)

Setter's solution : link

Tester's solution: link

This question is marked "community wiki".

asked 15 Sep '14, 15:41

xcwgf666's gravatar image

6★xcwgf666 ♦♦
719436377
accept rate: 0%

edited 15 Sep '14, 15:53

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156581


I am not sure if setter/tester wants N*log^2(N) to pass, but all i can say is time limit is not good for either of the case.

link

answered 15 Sep '14, 15:53

akash4983's gravatar image

6★akash4983
506115
accept rate: 0%

You could do a bit of optimisation. For example, I used a 2D range tree with fractional cascading and 1D bits, and it passed well under time limit. But yeah, the time limit was really really strict. At times, I feel that they set the time limit solely based on the running times of their programs. This is not a very good way to go about it since there can be solutions of same complexity but different implementation which may not pass

(15 Sep '14, 15:59) pushkarmishra4★

Well i did lots of optimizations, using 2D segment trees. Now i tried using few AC solutions they are hardly 0.1-0.5s faster than mine on some randomly generated files.

(15 Sep '14, 16:06) akash49836★

If you used a dynamic 2d segment tree, then you shouldn't blame the time limit.This is because , though, queries would be fast, updates(ie, additions and deletions will take log^2 (10^9), which is substantially slower than log^2 N.

(15 Sep '14, 16:29) pushkarmishra4★
1

In my code neither the memory is allocated dynamically, nor it is log^2 (10^9), it is log^2 (10^5) after compression :)

(15 Sep '14, 17:49) akash49836★
1

Then you are right in complaining about strict time limits.....

(15 Sep '14, 17:51) pushkarmishra4★

I have a O(n log^2(n)) solution which got TLE during the contest. I compared my solution with the slower ones which got AC, and on randomly generated test files, my code is as fast as theirs (abs(difference) < 0.5s).

Can someone provide with the generator in which my solution performs considerably worse than expected?
According to me the time limit is really really strict, and I would like to know how the setter/tester reached at this particular limit.

link

answered 15 Sep '14, 20:38

logic_max's gravatar image

5★logic_max
260447
accept rate: 0%

try to produce extreme cases. for example, make a case where there are many rectangles with same coordinates. what data structure have you used in your algo?

(15 Sep '14, 21:08) pushkarmishra4★

@pushkarmishra, I tried many different test cases. My program is faster*(~0.5s) for random cases. It is slower*(~0.3s) for cases with a lot of queries. Not a lot of difference. I have used 2d segment tree type structure.

*In comparison to last 2 ac solutions.

(15 Sep '14, 22:47) logic_max5★

Well.... The time limit was certainly tooo strict....

(15 Sep '14, 23:29) pushkarmishra4★

10^9 is the max co ordinate which is too high for the tree memory bounds, right ? So how do we tackle that while using a fenwick tree ? Some special hashing ? .... Or have I misunderstood the implementation and gone completely off track here ?

link

answered 25 Sep '14, 17:26

thezodiac1994's gravatar image

6★thezodiac1994
1.0k61122
accept rate: 16%

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,852
×1,359
×289
×146
×61

question asked: 15 Sep '14, 15:41

question was seen: 4,703 times

last updated: 25 Sep '14, 17:26