June 13, 2018 Cracking Abstruse Obtuse Triangles

Students enjoy simple trigonometric problems that involve figuring out the degrees of the angles in a triangle. For this last SRM, finding the number of possible obtuse triangles proved to be a fun and challenging problem.
For this problem, two values are provided, a and n. For the integers between a and a+3*(n-1), there is a stick of length x. When 3n sticks are provided, n disjoint obtuse triangles are constructed. The output is the number of obtuse triangles or the empty set. The output is returned as {r¹,…,rⁱ,…,rⁿ} where rⁱ = rⁱ10⁸+rⁱ10⁴+zⁱ. Each stick is only used once, any stick can be chosen, and the order of the sticks in the answer does not matter. The code will be provided in pseudocode.
A good first place to start is to figure out the integers that the will be measured. Writing a function that returns the upper-bound of the number of sticks is essential. The function for the upper bound should be defined as such:

	def calculate_max_bound(a, n):
		Return a+3*(n-1)

Okay, simple enough. Let us now write the functions for the other formulas. One is for calculating the length of the triangle:

	def  calculate_triangle(a,b,c):
		return c*c > a*a + b*b:  //returns true if c squared is greater than sum
	def obtuse_sides(a,b,c):
		if calculate_triangle(a,b,c):
			return [a,b,c]
		elif calculate_triangle(b,c,a):
			return [b,c,a]
		elif calculate_triangle(a,b,c):
			return [a,b,c]
		else:
			Return []

Finally, the definition of most importance is the one that will be used for providing the output of the program. The definition, based on the parameters, will be provided as such:

	def output(x, y, z):
		return x*pow(10,8) + y*pow(10,4) + z

Now that the standard definitions have been written, we can look into solving the problem. The idea behind the program is that the first tuple of possible lengths for a triangle is returned.
The first thing to do is establish the for-loop:

	for (int i = a; a < calculate_max_bound(a, n) + 1; a++):
		array a [] = obtuse_sides(a, a+1, a+2)
		return output(a[0], a[1], a[2])

At the moment, the output is being returned for whatever inputs of a and n are provided. However, n also defines how many output tuples are necessary to complete the problem. This can be solved by also adding an extraneous for-loop that takes this into account:

	for (int i = 0; i < n; i++):
		for (int i = a; a < calculate_max_bound(a, n) + 1; a++):
		array a [] = obtuse_sides(a, a+1, a+2)
		return output(a[0], a[1], a[2])

What we have done in the pseudocode is simple. We have calculated the possible sides of the obtuse triangle, the output, and the number of possible outputs. The reader can now go and implement the problem as code. The solution provided by Stonefeang also shows optimization for time. If one wants to participate in SRM, please read this guide. Happy coding.