AllTriangles
TCO21 Algo Semi 2 · 2021-11-12 · by misof
Problem Statement
Triangular numbers are numbers that can be obtained when counting items arranged into a triangle - in other words, they are sums of prefixes of the sequence of all positive integers.
The smallest few triangular numbers are 1, 3, 6, 10, 15, 21, ...
A permutation of order N is a sequence of length N that contains each of the numbers from 1 to N exactly once.
A permutation called a cyclic triangular permutation if it has the following property: if you place the elements of the permutation around a circle, each pair of adjacent elements would sum to a triangular number.
For example, {1, 2, 8, 7, 3, 12, 9, 6, 4, 11, 10, 5} is a cyclic triangular permutation. This is because 1+2, 2+8, 8+7, 7+3, ..., 10+5, and also 5+1 are all triangular numbers.
Given N, determine whether a cyclic triangular permutation of order N exists. If yes, return any one such permutation. If no, return an empty
Constraints
- N will be between 2 and 200, inclusive.
2
Returns: {1, 2 }
Both {1, 2} and {2, 1} are valid cyclic triangular permutations.
3
Returns: { }
Regardless of how you place the numbers 1, 2, 3 onto a circle, 2 and 3 will be adjacent, and their sum 2+3 is not a triangular number.
12
Returns: {1, 2, 8, 7, 3, 12, 9, 6, 4, 11, 10, 5 }
The example from the problem statement.
4
Returns: { }
5
Returns: { }
Submissions are judged against all 199 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AllTriangles with a public method vector<int> construct(int N) · 199 test cases · 2 s / 256 MB per case