Understanding the Problem
Bad Triangle is an 800-point problem at codeforces, I hope you have read the problem carefully and have tried thinking about solving it. This problem basically states that you need to tell if a triangle is non-degenerate or not.
Simply put, non-degenerate triangle is a triangle that the sum of any two sides in it is bigger than the other side. To see if it’s a bad triangle we have to check whether the sum of the two sides of them is less or equal than the other.
How to Think for a Solution
This problem has three inputs:
- input for test cases
- input for how many numbers we have in the coming array
- input for the array that has possible sides of a triangle (sorted increasingly)
Let’s focus on the third input, you can think of this problem as iterating through every element to see every possible validation for the sum of two numbers is less or equal than the other and that’s very time consuming because you have to check for three different indices.
There is a trick for solving this problem which won’t make you need to iterate through the array. The fact that the input is sorted in non-decreasing order makes the largest number at the right-most of the array which means if you just check whether the sum of the first two numbers in the array is less than that largest number at the end of the array, this will be enough for you to tell if this triangle is bad or not.
If it’s less than the last element, it’s then a bad triangle and we print these indices; using the fact that the problem states that we need to print any of the indices that make it such bad triangle. If it’s not less than the last element, there is no need to loop over because you will never find a bigger number than the last element; so in this case, print -1.
That’s how I thought about this problem and below is my implementations in Python and Javascript:
Python
Javascript
Shoutout
I’d like to share this video because the idea of solving this solution is from this guy. Check out his solution in C++ if you’re interested.