11401 - Triangle Counting

[lighted]

Try to derive recurrent formula f(n), where f(n) is number of distinct triangles using rods 1, 2 .. n.
f(n) can be calculated using f(n - 1). Make precalculation for all n.

[richatibrewal]

Will someone plz explain the problem. I am having a difficulty in understanding this problem.

[lighted]

You are given n rods of length 1, 2…, n. You have to pick any 3 of them & build a triangle. How many distinct triangles can you make? Note that, two triangles will be considered different if they have at least 1 pair of arms with different length.

For n = 3. We have rods of length: 1, 2, 3. We can't make any triangle from these rods because they don't satisfy triangle inequality:

Code: Select all

a + b > c
a + c > b
b + c > a

For n = 4: 1, 2, 3, 4. We can make 1 triangle using rods: (2, 3, 4).

For n = 5: 1, 2, 3, 4, 5. We can make 3 triangles using rods: (2, 3, 4), (2, 4, 5), (3, 4, 5).

For n = 6: 1, 2, 3, 4, 5, 6. We can make 7 triangles using rods: (2, 3, 4), (2, 4, 5), (2, 5, 6), (3, 4, 5), (3, 4, 6), (3, 5, 6), (4, 5, 6).
And so on..

[richatibrewal]

Thank u so much.
Accepted

[Eucliwood]

For the fastest time, try to find the function f(n) for even n, and for odd n. They have different f(n).