KAN15RTB - Editorial

PROBLEM LINK:

Practice
Contest

Editorialist: Karan Aggarwal

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Maths

PROBLEM:

Find out maximum number of regions in which you can divide a circle Given N points on a circle such that there is a line segment between every pair of points, find the maximum number of regions that can be created.

EXPLANATION:

Assume we already have the maximum number of regions for N-1 points on this circle. When we add the Nth point, the maximum extra number of regions it can make is equal to one more than the number of line segments it intersects when connected to each of the points on the circle.

Let’s number the N-1 points in clockwise order. Now when the Nth point is connected to the 1st point, it intersects 0 line segments and hence creates 1 region. When it is connected to the 2nd point, it makes 1*(N-3) + 1 regions and when to the 3rd point, it makes 2*(N-4) + 1 regions. Let R(N) denote the maximum number of regions in a circle with N points.

Hence R(N) = R(N-1) + ∑ ( (i-1)*(N-i-1) + 1) % 10^9 + 7.


Solving this recursion would give (N*(N-1)*(N-2)*(N-3))/24 + (N*(N-1))/2 + 1
We can precompute modulo inverse of 24 and 2 using Fermat’s theorem and hence each test case can be answer in O(1).