AtCoder Beginner Contest 175

First lets see Making Triangle question. You have N stick which have length Li. Now in how many ways you can choose different sticks such that they are of different length & form valid triangle. So basically this is the question.

 

Similar type of question occurred in Codeforces. So can find its complete explanation here.

 

We all know property of triangle a + b > c. As the constraints are low you can write O(n^3) solution. Simply we will maintain three pointer & check both the conditions & update the count accordingly.

 

Solution

 

 Related Articles : Important LeetCode questions

 

Next is Walking Takahashi so there is a number line & takahashi is on coordinate. He can make exactly k moves of distance D. After k moves his destination coordinate should be minimum possible. Since the constraints are very high we will apply math here.

Basically we have to hop towards the zero. If you are on negative side then hop towards right else hop towards left until you come closest to zero. After reaching closest to zero if you are left with more k then just hop back & forth.

 

Other Posts : Development

 

For doing back & forth we have to keep in mind that for even moves you can easily nullify the hops but in case of odd. After reaching closest to zero our main goal will be to nullify hops left so that we can stay closest.

There are two cases after reaching closest to zero :

1. If you are left with even number of hops you can easily nullify that (they will get cancel out) & you remain closest to zero.
2. If you are left with odd number of hops then we have to do one more step to check which one is closest to zero.

 

Explanation :

1.  We will find absolute value of x.
2.   x/d is how many step it will take to reach on zero. If its greater than or equal to k it will mean that we will exhaust our hops on right of number line else it will mean that we are left with more chance & we will have to hop back & forth.
3. At last apply concept of even & odd as discussed above. 

 

Solution

 

Related Posts : Data Structures