1
$\begingroup$

This is a somewhat long question thus sincere apologies beforehand. In a tree a node is a simple point. Now instead of a node let us consider a set of 'choice nodes' that have the following properties:

  1. Each 'node' has a top side, bottom side, and a unique set of K distinct color pairs (vertical top-bottom pairs). Each color always pairs with exactly one other color (eg: red with pink, orange with yellow and so on).
  2. Each 'node' can connect to another via an edge only b/w two same colors: edge b/w bottom of upper node and top of lower node (in a tree).
  3. In any 'node' both colors of a pair cannot take part in connections. These connections are illegal.

enter image description here

Given a set of $C$ color pairs, each color pair occurring exactly $2k$ times in total: $k$ times as $C_{red}:C_{pink}$ and $k$ times as $C_{pink}:C_{red}$. Each node has $p$ color pairs (4 in example). Thus total number of Nodes given to us are $N = 2kC/p$

Query 1: Given any set of such nodes, can we always create a tree $T$ such that: $Depth(T) \leq log_{p-1}N$? In other words, can we always create a tree with smallest depth possible? I believe the answer is yes, but I am struggling to formally prove it. If NO can someone explain why (with an explicit example if possible).

Query 2: Assuming answer is YES, what algo can be used to create this minimum depth tree $T$?

$\endgroup$
1
  • $\begingroup$ can someone please please help with this Q? $\endgroup$
    – J.Doe
    Jul 21, 2023 at 16:17

0

You must log in to answer this question.

Browse other questions tagged .