## 11401 - Triangle Counting

Moderator: Board moderators

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 11401 - Triangle Counting

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.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

### Re: 11401 - Triangle Counting

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

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 11401 - Triangle Counting

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..
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

### Re: 11401 - Triangle Counting

Thank u so much.
Accepted

Eucliwood
New poster
Posts: 3
Joined: Mon May 30, 2016 1:07 pm

### Re: 11401 - Triangle Counting

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