Lightoj 1331 solution in English

 

Lightoj 1331 Ajent J 

Problem Link

Click here to see the discussion in Bangla

In the movie Dhoom 2, Hrithik Roshan’s diamond theft scene is quite famous. Similarly, LightOJ problem 1331 is about a diamond theft.

                                          

Here we have an agent ‘J’ who wants to steal the diamond kept in a museum. But the theft isn’t that easy, because there are three circular laser scanners, continuously rotating.

These three circles are placed in such a way that each circle is externally tangent to the other two, and the diamond is placed in the middle enclosed region.

Our task is to find the area of that enclosed region (the shaded diamond-shaped area). The radii of the three circles are given: $R1, R2, R3$.

                                     

Step 1: Forming the Triangle

If we connect the centers of the three circles, we form a triangle.

• The distance between the centers of circle $R1$ and $R2$:

  $$a = R1 + R2$$

• The distance between the centers of circle $R2$ and $R3$:

  $$b = R2 + R3$$

• The distance between the centers of circle $R1$ and $R3$:

  $$c = R1 + R3$$

Step 2: Area of the Triangle

Once we have the three sides $a, b, c$, we can calculate the area of the triangle using Heron’s formula.

First compute the semi-perimeter:

$$s = \frac{a+b+c}{2}$$

Then, the triangle’s area is:

$$\text{Area}_{\triangle} = \sqrt{s(s-a)(s-b)(s-c)}$$

Step 3: Sector Areas (Circular Arcs)

                                              

From basic geometry, we know that the area of a circular sector is:

$$\text{Sector Area} = \tfrac{1}{2} r^2 \theta$$

where $r$ is the circle’s radius and $\theta$ is the angle in radians subtended at the circle’s center.

So, to compute the circular sectors inside the triangle, we need the angles of the triangle at the vertices.

Using the cosine rule:

$$\cos(C) = \frac{a^2 + b^2 - c^2}{2ab}$$ $$\cos(A) = \frac{b^2 + c^2 - a^2}{2bc}$$ $$\cos(B) = \frac{c^2 + a^2 - b^2}{2ca}$$

Now, the sector areas are:

$$\text{Area}_1 = \tfrac{1}{2} R1^2 \cdot \arccos\left(\frac{c^2 + a^2 - b^2}{2ca}\right)$$ $$\text{Area}_2 = \tfrac{1}{2} R2^2 \cdot \arccos\left(\frac{b^2 + a^2 - c^2}{2ab}\right)$$ $$\text{Area}_3 = \tfrac{1}{2} R3^2 \cdot \arccos\left(\frac{c^2 + b^2 - a^2}{2bc}\right)$$

Step 4: The Diamond Area

Finally, the required shaded region (diamond area) is:

$$\text{Diamond Area}={\text{Area}}_{\mathrm{△}}-({\text{Area}}_1+{\text{Area}}_2+{\text{Area}}_3)$$
For source code: Source code

Read More

Lightoj 1072 solution in English

Problem Link: Lightoj 1072

Click here to see the discussion in Bangla

In this problem, we are given:

• The radius of a large outer circle
  $R$

• The number of smaller circles
  $n$
   that fit inside the larger circle, touching it

We need to find the radius of each smaller circle 

$\mathrm{r<a\; href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgVEANBv3h5X85wCQV-Js7u5IWvQgGoNgsfAUn0ckZ7AvxgExlvH3tj6R7PF1ivS\_wiDQouALnDdBcWgS5FB2gN09YJbPPh9m5DkYCmwfVDL0\_thvoEVFrRr-VOywAg1ATfGDMtL1tG\_F4/s1600/1072new.PNG"\; style="margin-left:\; 1em;\; margin-right:\; 1em;"><img\; border="0"\; data-original-height="509"\; data-original-width="962"\; height="169"\; src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgVEANBv3h5X85wCQV-Js7u5IWvQgGoNgsfAUn0ckZ7AvxgExlvH3tj6R7PF1ivS\_wiDQouALnDdBcWgS5FB2gN09YJbPPh9m5DkYCmwfVDL0\_thvoEVFrRr-VOywAg1ATfGDMtL1tG\_F4/s320/1072new.PNG"\; width="320"></a>}$

Step 1: Angle subdivision

We know a full circle is 

$360^\circ$

.

If there are 

$n$

small circles inside, they divide the large circle into 

$n$

equal sectors.

So, the angle at the center of the large circle subtended by one small circle is:

$$\frac{360^\circ}{n} = \frac{180^\circ}{n} = \frac{\pi}{n}$$

Step 2: Using trigonometry

Consider the triangle formed by:

• The center of the large circle

• The center of one small circle

• The point of tangency on the large circle

In this triangle:

• The opposite side = 
  $r$
  (radius of the small circle)

• The hypotenuse = 
  $R - r$

So:

$$\sin\theta = \frac{r}{R - r}, \quad \theta = \frac{\pi}{n}$$

                                   

Step 3: Solve for 

$r$

$$\sin\left(\frac{\pi}{n}\right) = \frac{r}{R - r}$$ $$r = \sin\left(\frac{\pi}{n}\right)(R - r)$$ $$r = R\sin\left(\frac{\pi}{n}\right) - r\sin\left(\frac{\pi}{n}\right)$$ $$r + r\sin\left(\frac{\pi}{n}\right) = R\sin\left(\frac{\pi}{n}\right)$$ $$r(1 + \sin(\tfrac{\pi}{n})) = R\sin\left(\tfrac{\pi}{n}\right)$$ $$\boxed{r = \frac{R \sin(\pi/n)}{1 + \sin(\pi/n)}}$$

Thus, the radius of each inner small circle is:

$$r = \frac{R \sin(\pi/n)}{1 + \sin(\pi/n)}$$

Would you like me to also provide a short Python function that computes 

$r$

for given 

$R$

and 

$n$

?

Source Code:

Another problem like this, 

Problem Link :  codeforces 1100 C

Source Code : SourceCodeLink

Read More

Lightoj 1178 solution in English

Lightoj 1178 : Problem Link

Click here to see the discussion in Bangla

In this problem, we are given the lengths of the four sides of a trapezium. We need to calculate its area.

We know the formula for the area of a trapezium is:

$$\text{Area} = \tfrac{1}{2} \times (\text{sum of parallel sides}) \times (\text{distance between them})$$

That is:

$$\text{Area} = \tfrac{1}{2} \times (a + c) \times h$$

Here:

• $a$ and $c$ are the lengths of the parallel sides.

• $h$ is the height (perpendicular distance between $a$ and $c$).

We are given $a$ and $c$, but not $h$. So, we need to calculate $h$.

Step 1: Drop perpendiculars

• From point $C$, drop a perpendicular $CP$ onto $AB$.

• From point $D$, drop a perpendicular $DQ$ onto $AB$.

Thus:

$$CP = DQ = h$$

Also:

$$PQ = c, \quad AP + BQ = a - c$$

Let:

$$AP = x, \quad BQ = a - c - x$$

Step 2: Apply Pythagoras

Now, consider right triangles APC and BDQ.

In triangle APC:

$$AC^2 = AP^2 + h^2$$ $$d^2 = x^2 + h^2 \quad \Rightarrow \quad h^2 = d^2 - x^2 \quad ...(1)$$

In triangle BDQ:

$$BD^2 = BQ^2 + h^2$$ $$b^2 = (a - c - x)^2 + h^2 \quad \Rightarrow \quad h^2 = b^2 - (a - c - x)^2 \quad ...(2)$$

Step 3: Eliminate $h$

From equations (1) and (2):

$$d^2 - x^2 = b^2 - (a - c - x)^2$$

Expanding:

$$d^2 - x^2 = b^2 - (a^2 + c^2 + x^2 - 2ac - 2ax + 2cx)$$ $$d^2 - x^2 = b^2 - a^2 - c^2 - x^2 + 2ac + 2ax - 2cx$$ $$d^2 = b^2 - a^2 - c^2 + 2ac + 2ax - 2cx$$ $$2ax - 2cx = d^2 - b^2 + a^2 + c^2 - 2ac$$ $$x = \frac{d^2 - b^2 + a^2 + c^2 - 2ac}{2a - 2c}$$

So we have found x.

Step 4: Solve for $h$

Now substitute $x$ into equation (1):

$$h^2 = d^2 - x^2$$ $$h = \sqrt{d^2 - \left(\frac{d^2 - b^2 + a^2 + c^2 - 2ac}{2a - 2c}\right)^2}$$

Step 5: Area of the trapezium

Finally, substitute $h$ back into the trapezium formula:

$$\text{Area} = \tfrac{1}{2} \times (a + c) \times h$$

Now we have the formula to calculate the trapezium’s area using the four sides. 

Source Code : SourceCodeLink

Read More

Lightoj 1004 Solution in English

Lightoj 1004 Solution in English

Problem Link: Lightoj 1004

Click Here to see the discussion in Bangla

First, let me say this is a simple DP (Dynamic Programming) problem.

If you know the Rock Climbing problem, this one will feel very similar. If not, it’s better to learn that first (there are Bengali blogs about it). Anyway, let’s discuss the problem.

We are given a diamond-shaped 2D array.

Each cell of the array contains some bananas 🍌.

A monkey starts from the top of the diamond and can only move downward to adjacent cells.

Whenever the monkey visits a cell, it eats all the bananas in that cell.

So, our task is to find the maximum number of bananas the monkey can eat by choosing the best possible path. 

                                                             

Step 1: Understanding the movement

• The monkey can only move to adjacent cells below the current cell.

• For example, if the monkey is at [1,1] (with 7 bananas), it can go to [2,1] or [2,2].

• Now, which one should it choose? The answer depends on which path eventually gives more bananas.

• So, we must check all possible paths to know the maximum.

This can naturally be solved using recursion:

• At each cell, check all possible next moves.

• Take the path that yields the maximum bananas.

Step 2: Why recursion is not enough

Although recursion works, it will cause a TLE (Time Limit Exceeded).
Why?
Because the monkey can revisit the same cell multiple times from different paths, and each time, recursion will recompute the result for that subproblem.

If you print row/column indices during recursion, you’ll see that many cells are visited multiple times.

Step 3: Adding DP (Memoization)

To avoid recomputing, we use DP (Dynamic Programming):

• We store the result (maximum bananas from this cell onward) in a DP array.

• If we reach the same cell again, we don’t recurse further. Instead, we directly return the stored result.

• This way, each cell is computed only once, making the solution efficient.

Step 4: Special case for diamond shape

Since the array is diamond-shaped, there are two phases:

1. Expanding rows (from top to middle).

2. Contracting rows (from middle to bottom).

That’s why the recursive function uses two conditions for handling movement in different halves of the diamond.

Read More

Lightoj 1289 - LCM from 1 to n solution in English

 

Lightoj 1289 - LCM from 1 to n solution in English

Problem Link: Lightoj 1289 

Click here to see the discussion in Bangla 

The problem is: we are given a number n. We need to calculate the LCM of all numbers from 1 to n.

At first glance, if we look at the constraints:

• n can be as large as 10^8

• The number of test cases can be as large as 10^4

So if we try to directly compute the LCM by looping through numbers one by one, we will definitely get a TLE (Time Limit Exceeded).

Step 1: Recall how to calculate LCM and GCD

For two numbers a and b, we know:

• Every number can be expressed as a product of prime powers:

  a = p1^x1 * p2^x2 * ...
  b = p1^y1 * p2^y2 * ...
  

• Then:

  gcd(a, b) = p1^min(x1,y1) * p2^min(x2,y2) * ...
  lcm(a, b) = p1^max(x1,y1) * p2^max(x2,y2) * ...
  

Example:

• 20 = 2^2 * 5

• 14 = 2 * 7

gcd(20,14) = 2^min(2,1) * 5^min(1,0) * 7^min(0,1) = 2  
lcm(20,14) = 2^max(2,1) * 5^max(1,0) * 7^max(0,1) = 140

The same principle works for multiple numbers.

So:

lcm(a,b,c,d) = p1^max(x1,y1,z1,m1) * p2^max(x2,y2,z2,m2) * ...

Step 2: How this applies to our problem

We need lcm(1,2,...,n).
This means: for each prime ≤ n, we need the maximum power of that prime that is ≤ n.

Let’s try an example with n = 10:

Numbers:

1,2,3,4,5,6,7,8,9,10

Factorizations:

2 = 2^1
3 = 3^1
4 = 2^2
5 = 5^1
6 = 2*3
7 = 7^1
8 = 2^3
9 = 3^2
10 = 2*5

So:

LCM(1..10) = 2^3 * 3^2 * 5^1 * 7^1 = 2520

Notice:

• All primes ≤ 10 appear at least once in the LCM.

• But for primes like 2 and 3, higher powers also appear (2^3, 3^2).

Step 3: How to get maximum powers efficiently

• For a prime p, the maximum exponent k such that p^k ≤ n is exactly:

  k = floor(log_p(n))
  

• For example, for n = 10:

  • For prime 2: largest power ≤ 10 is 2^3 = 8

  • For prime 3: largest power ≤ 10 is 3^2 = 9

  • For prime 5: largest power ≤ 10 is 5^1 = 5

  • For prime 7: largest power ≤ 10 is 7^1 = 7

That’s exactly what we need.

Step 4: Precomputation strategy

• Generate all primes up to 10^8 using Sieve of Eratosthenes.

• Precompute cumulative product of primes to handle queries faster:

  store[i] = store[i-1] * prime[i]
  

This way, for any n, we know:

• Multiply all primes ≤ n once.

• Then, for primes ≤ sqrt(n), also multiply the extra higher powers.

Step 5: Modulo issue

The problem asks us to take the result modulo 2^32.
If we use unsigned int in C++ (32-bit), the modulo will happen automatically.

So the efficient approach:

1. Generate primes up to 10^8.

2. For each test case:

   • Multiply all primes ≤ n.

   • For each prime ≤ sqrt(n), multiply in the maximum exponent of that prime ≤ n.

3. Result is modulo 2^32.

'

Read More