Connection Status:
Competition Arena > LuckyTree

LuckyTree

SRM 665 · 2015-06-30 · by tehqin

SRM 665 · 2015-06-30 · by tehqin · Graph Theory
Class Name: LuckyTree
Return Type: int[]
Method Name: construct
Arg Types: (int)
Problem Statement

Problem Statement

Cat loves making trees. Cat's friend Dog will have a birthday soon, so Cat has decided to make a special tree for Dog.


Cat likes the numbers 4 and 7. Therefore, the weight of each edge in the tree will be either 4 or 7.


Dog likes balance. A simple non-empty path in the tree is balanced if it contains the same number of weight-4 and weight-7 edges. (Note that an empty path is not balanced.) Direction does not matter: a path from X to Y is the same as a path from Y to X.


Dog's favorite number is favorite. Cat would like to encode this number into the tree as the number of balanced paths it contains.


You are given the int favorite. Find a tree that contains at most 51 vertices and has all the above properties. Return a int[] containing a description of the tree in the format specified below. If there are many such trees, you may return any of them. If there are no such trees, return an empty int[] instead.


Suppose that you want to return a tree with V vertices. (Note that V must be between 1 and 51, inclusive.) First, label those vertices 0 through V-1. Then, return a int[] X with exactly 3V-2 elements. X[0] should be the number of vertices. The rest of X should be the list of edges. More precisely: For each edge in your tree there must be an i between 0 and V-2, inclusive, such that X[3*i+1] and X[3*i+2] are the vertices connected by that edge and X[3*i+3] is the weight of the edge: either 4 or 7.

Constraints

  • favorite will be between 1 and 1275, inclusive.
Examples
0)
1
Returns: {3, 0, 1, 4, 1, 2, 7 }

We are looking for any tree with exactly 1 balanced path. The return value describes a tree with three vertices. There are two edges: 0-1 (weight 4) and 1-2 (weight 7). The single balanced path is the path between vertices 0 and 2.

1)
64
Returns: {17, 0, 1, 4, 0, 2, 4, 0, 3, 4, 0, 4, 4, 0, 5, 4, 0, 6, 4, 0, 7, 4, 0, 8, 4, 0, 9, 7, 0, 10, 7, 0, 11, 7, 0, 12, 7, 0, 13, 7, 0, 14, 7, 0, 15, 7, 0, 16, 7 }
2)
47
Returns: {15, 1, 12, 4, 1, 11, 4, 0, 1, 7, 0, 2, 7, 2, 10, 4, 2, 9, 4, 0, 4, 4, 0, 3, 4, 3, 7, 7, 3, 8, 7, 4, 5, 7, 4, 6, 7, 12, 13, 7, 13, 14, 4 }
3)
1275
Returns: { }

It is not possible to create a tree with 1275 balanced paths using only 51 nodes.

4)
578
Returns: {51, 0, 1, 4, 1, 2, 7, 2, 3, 4, 3, 4, 7, 4, 5, 4, 5, 6, 7, 6, 7, 4, 7, 8, 7, 8, 9, 4, 9, 10, 7, 10, 11, 4, 11, 12, 7, 12, 13, 4, 13, 14, 7, 14, 15, 4, 15, 16, 7, 16, 17, 4, 17, 18, 7, 18, 19, 4, 19, 20, 7, 20, 21, 4, 21, 22, 7, 22, 23, 4, 23, 24, 7, 24, 25, 4, 25, 26, 7, 26, 27, 4, 27, 28, 7, 28, 29, 4, 29, 30, 7, 30, 31, 4, 31, 32, 7, 32, 33, 4, 33, 34, 7, 34, 35, 4, 35, 36, 7, 36, 37, 4, 37, 38, 7, 39, 15, 7, 40, 37, 7, 41, 37, 7, 42, 37, 7, 43, 37, 7, 44, 37, 7, 45, 37, 7, 46, 37, 7, 47, 37, 7, 48, 37, 7, 49, 37, 7, 50, 37, 7 }

Submissions are judged against all 138 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LuckyTree with a public method vector<int> construct(int favorite) · 138 test cases · 2 s / 256 MB per case

Submitting as anonymous