welcome: please sign in

Upload page content

You can upload content for the page named below. If you change the page name, you can also upload content for another page. If the page name is empty, we derive the page name from the file name.

File to load page content from
Page name
Comment

location: ProblemsDescription / WeightAssignmentTree

Weight-Assignment Tree

Problem Description

Problem is concerned with a full-binary tree such that

  1. its leaves are pairs (weight,cardinality), where weight and cardinality are integers
  2. the right child of an inner node is a leaf,
  3. each inner node is a pair (color,weight), where color is either green, red, or blue.

Condition (2) implies that the trees of interest are paths "going to the left" with each node on the path having the right child being a leaf of the tree.

In the problem, the weights and cardinality values of n leaves and the colors of all inner nodes are given. The weights of inner nodes are computed recursively (or to put it differently, are subject to constraints) based on their colors, weights and the cardinalities of their children.

Specifically, the weight of an inner node X satisfies the formulas (constraint):

Total weight of a tree is the sum of the weights of its inner nodes.

The problem is: given a tree T, with all weight and cardinalities assigned to leaves, and colors specified for the internal nodes, verify if there is a tree T' with the same set of leaves as T satisfying conditions (1)-(3) whose total weight is less than a total weight of T. The leaves in the tree T' may be arranged differently than in the tree T, and the colors of the internal nodes may be different.

Input format

An input consists of the following parts:

a. n leaves are given with corresponding weight and cardinality (there are 1..n leaves): leafWeightCardinality(leaf1,w1,c1). ... leafWeightCardinality(leafn,wn,cn). where w1..wn, c1..cn are integers.

b. for each inner node (there are 1..n-1 inner nodes), its assigned color is specified: innerNodeColor(1,color1) ... innerNodeColor(n-1,color_n-1) where color1..color_n-1 is one of the three colors {green, red, blue}

c. tree structure of T is given by predicates innerLeftRight(1,leafL_id_1, leafR_id_1). .. innerLeftRight(n-1,leafL_id_n-1, leafR_id_n-1). where leafL_id_1, leafR_id_1... are ids of leaves 1..n.

Output format

A solution is represented by means of a constant "exists" if there is a tree T' and a specification of T' in the following format innerNodeColorPrime(1,color1) ... innerNodeColorPrime(n-1,color_n-1) innerLeftRightPrime(1,leafL_id_1, leafR_id_1). .. innerLeftRightPrime(n-1,leafL_id_n-1, leafR_id_n-1).

Otherwise, no answer set is returned.

Example

Given:

leafWeightCardinality(leaf1,4,5). leafWeightCardinality(leaf2,3,7). innerNodeColor(1,green). innerLeftRight(1,leaf1,leaf2).

Output contains: exists innerNodeColorPrime(1,red). innerLeftRightPrime(1,leaf2,leaf1).

Explanation: Total weight of the tree in the example is 10

Total weight of the tree in the output is 7.

Author(s)