11401 - Triangle Counting

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: 11401 - Triangle Counting

Post by lighted » Tue Jul 29, 2014 12:53 am

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

Post by richatibrewal » Thu Nov 06, 2014 11:16 am

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

Post by lighted » Thu Nov 06, 2014 1:42 pm

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

Post by richatibrewal » Fri Nov 07, 2014 5:45 pm

Thank u so much.
Accepted

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

Re: 11401 - Triangle Counting

Post by Eucliwood » Mon May 30, 2016 1:10 pm

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

Post Reply

Return to “Volume 114 (11400-11499)”