rawat_sidharth's blog

By rawat_sidharth, 3 weeks ago, In English,

Recently encountered this problem in a competition. Tried solving it using graphs, creating neighbors and then finding the number of nodes in different disconnected sub-graphs. But the creation of neighbors itself is O(n^2) and hence was getting TLE. I have been trying to figure out a way to solve this without creating neighbors or find a more efficient way to create neighbors, but haven't been able to do so. I also thought of using union-find, but again computing distances between each pair is O(n^2). Any help would be really appreciated.

Problem:

There are n circles, for each of which center ( x , y ) and radius r are provided. These circles can intersect each other. Circles are said to be intersecting if they touch each other or cross each other's circumference. A cluster of circles is defined as a group of circles which are in contact with each other. So, if C1 intersects C2 and C2 intersects C3, then C1, C2, C3 are in a cluster even if C1 and C3 don't directly intersect each other. We have to find the cluster with the largest number of circles. Print the number of circles in the largest cluster and the smallest circle index in that cluster. If 2 clusters have the same number of circles, print the one with the smallest circle index.

Constraints:

0<= n <= 1e5, 0 <= r <= 50, 0 <= x, y <= 1e4

Time limit:

3s for 50 test cases.

Additional info:

For 20% test cases, 0 <= n <= 100

For 30% test cases, 100 <= n <= 1000

For 30% test cases, 1000 <= n <= 1e4

For 20% test cases, 1e4 <= n <= 1e5

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rawat_sidharth (previous revision, new revision, compare).

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

First observation: 0 $$$\leq$$$ p $$$\leq$$$ 50, means that there are at most 51 different radiuses.

Second observation: if we're looking at a circle of radius r, let's try to add all the circles with some fixed radius R, such that r $$$\leq$$$ R, and those circles intersect. There are at most 3 groups which circles of radius R can form. So let's just find at least one circle in each group and get an edge between. After that it's just DFS, with $$$O(n)$$$ vertices and $$$O(np)$$$ edges.

Now let's link 4 circles that are in 4 different parts of the coordinate plane using some data structure like segment tree.

N̶o̶w̶ ̶i̶f̶ ̶i̶'̶v̶e̶ ̶m̶i̶s̶u̶n̶d̶e̶r̶s̶t̶o̶o̶d̶ ̶t̶h̶e̶ ̶p̶r̶o̶b̶l̶e̶m̶ ̶a̶n̶d̶ ̶t̶w̶o̶ ̶c̶i̶r̶c̶l̶e̶s̶ ̶i̶n̶t̶e̶r̶s̶e̶c̶t̶ ̶i̶f̶ ̶**d̶i̶s̶t̶** ̶≤̶ ̶**r̶** ̶+̶ ̶**R̶**,̶ ̶t̶h̶e̶ ̶p̶r̶o̶b̶l̶e̶m̶ ̶i̶s̶ ̶i̶n̶d̶e̶e̶d̶ ̶s̶o̶l̶v̶e̶d̶ ̶i̶n̶ $$$O(np \cdot log)$$$.

Otherwise:

Rr $$$\leq$$$ dist $$$\leq$$$ r + R

Third observation: if there is a circle of radius R and the circle of radius r inside of it, then the circle of radius R intersects all the circles of radius R, such that they intersect or contain the circle of radius r.

Now we should link the circles only in case if there is at least one circle of radius R that intersects with ours. So to link correctly we need to know, whether there is such a circle. This is where it gets really hard and I don't know any nice solution (the best I can do is probably $$$O(np^2log)$$$ or $$$O(np^2)$$$ which is way too slow), so it's unsolved.

UPD: I was a little wrong, so I still can't figure out the solution.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Are x, y, and r reals or integers?