UVA 11554 - Hapless Hedonism

Problem link

Problem Clearance: 

You are given N, an integer which means you have N  rods of 1,2,....,N  length. .You are to find Maximum number of Distinct Triangle  you can form with these Rods. You can say a triangle will be different from another triangle if it has a difference in Lengths of a Pair of Sides . 

To solve this problem you need know a very well know formula which is " To be a valid Triangle the Sum of Length of any Two sides must be Grater than the length 3rd one . "  For example if we have Rod of length of 1,2,3 then formed triangle will be [1,2,3] but it's not valid because 1+2=3 . if we have 2,3,4 then formed triangle will be [2,3,4] and it's valid because 2+3>4 .

One thing you have consider that the Rods will be taken as Increasingly Sorted order as in 1,2,3 not 3,1,2  / 3 2 1 . 


Approach:

To get a better idea about how to solve this problem you have to do what I am doing here. Take a pen & paper. And do what I am doing here . Hope you will be able what you are doing.

It is sure for N = 3 the ans will be 0 . Reason is described in Clearance section. Now do some Pen-Paper works for 4 - 8. If you are right in your approach you will get the following results .

Make sure you are getting the same results compared to me. For every Nth step can you see something similar to (N-1)th step ?

Yes... That's it .. The value of every (N-1)th Steps will be Add with Nth step. So, in each step we have to Store this value to find out the Next step's Value. Let's denote the RED segments as Previous & the Blue segments as Current . 

Now Pay a deep attention to the number of the Current segments for every Nth term. Can you find any Pattern ?

Yes.. That's it .. For every Nth  step we will add an extra value .
Look more closely, you will able to see a Lovely Pattern for every Even N & every Odd N .  Let an Increment  variable inc = 0 . For every Even N we will increase the value inc  by 1 . And for every Odd N  we will add the current inc values.

Why we are adding an Extra value in each step. Is it any Analogy / and Arbitrary Value? Nope.

Watch the generated Triangles Closely & Match with the pattern. You will see the ,

=> 1st term of Pattern is the number of the Triangle Generated with starting Side 2 for Nth step.
=> 2nd term of Pattern is the number of the Triangle Generated with starting Side 3 for Nth step.
=> 3rd term of Pattern is the number of the Triangle Generated with starting Side 4 for Nth step.
.
.
=> Nth term of Pattern is the number of the Triangle Generated with starting Side (N+1) for Nth step.

references



A solution in c++