TreeReconstruct
TCO06 Round 4 · 2006-03-01 · by lars2520
TCO06 Round 4 · 2006-03-01 · by lars2520 · Graph Theory
Problem Statement
Problem Statement
A tree is a connected graph with no cycles.
Starting from a connected tree with positive integral edge lengths, we take a subset of the nodes of that tree. Next, we compute the lengths of the shortest paths between all pairs of nodes in the subset (in the original tree). This gives us a symmetric N*N distance matrix where N is the number of nodes in the subset.
Your task is to reverse this process. Given a N*N distance matrix, you are to reconstruct a tree, if possible. Since there may be many reconstructions, you should return the minimum number of nodes in any reconstruction that agrees with the distance matrix (this will be at least N). If no reconstruction is possible, return -1.
The distance between nodes i and j (indexed from 0) can be found by treating g1[i][j] and g2[i][j] as hexadecimal digits. Putting the two digits together gives the distance (g1 has the more significant digits).
Your task is to reverse this process. Given a N*N distance matrix, you are to reconstruct a tree, if possible. Since there may be many reconstructions, you should return the minimum number of nodes in any reconstruction that agrees with the distance matrix (this will be at least N). If no reconstruction is possible, return -1.
The distance between nodes i and j (indexed from 0) can be found by treating g1[i][j] and g2[i][j] as hexadecimal digits. Putting the two digits together gives the distance (g1 has the more significant digits).
Constraints
- g1 and g2 will each contain exactly N elements, where N is between 2 and 50, inclusive.
- Each element of g1 and g2 will contain exactly N hex digits ('0'-'9' and 'A'-'F').
- The distance between each pair of distinct nodes will be positive.
- The diagonal entries of g1 and g2 will be '0'.
- g1 and g2 will each be symmetric.
Examples
0)
{"0000",
"0000",
"0000",
"0000"}
{"0444",
"4044",
"4404",
"4440"}
Returns: 5
The original tree could have been a star: one central node, with 4 nodes connected to it, each by an edge of length 2. The subset of selected nodes are the 4 non-central nodes.
1)
{"0000",
"0000",
"0000",
"0000"}
{"0233",
"2033",
"3302",
"3320"}
Returns: 6
2)
{"00001",
"00001",
"00011",
"00100",
"11100"}
{"066C6",
"60CA4",
"6C02C",
"CA20A",
"64CA0"}
Returns: 6
3)
{"00000",
"00000",
"00001",
"00000",
"00100"}
{"06839",
"60E7B",
"8E0B1",
"37B0A",
"9B1A0"}
Returns: 7
4)
{"012120333422412163442343","101312222313321042351532","210403111204232131362621","134042555644634375624265","210403111115142231373622","023230444531503264553454","321514022315343242473731","321514202126154322584713","321514220226253342484733","432615312037164433595824","210413122305342242372632","234451566750725486775676","432615312137064423594804","123340455642604375664565","212423343425440264570654","101322233424432053462543","6437364243482765047A6925","321514222326354340484733","433635454537565474095854","4562757889779676A8907498","212433344525440264570654","356264777866856597846087","432625313237065423595804","321524133426454353484740"}
{"011FBF1EBA9B9D6C0DCB8FDD","1000A00DA98C8E5BFCBC70CC","1000A00DA98C8E5BFC3C70CC","F000AE0DA98A8C5BFCBC70CC","BAAA0AA30F26E8F552D61A26","F00EA00DA98C8E5BFCBA7ECC","1000A00DA98C8E5BFC3C70C6","EDDD3DD032591B2885094D59","BAAA0AA30F26E8F552D61A26","A999F992F015D7E441C50915","98882885210406D374B4F844","BCCA6CC965404A17B8763A88","9888E881ED0406D3B0B4F844","DEEC8EEB876A6039DA985CAA","6555F552FED1D30041012511","CBBB5BB854373900A7672B77","0FFF5FF8547BBD4A072B6FFB","DCCC2CC521480A1770F83C48","CB3BDB30DCB7B9062F072BFF","BCCC6AC965464817B8703C88","8777177410F3F52263230733","F000AE0DA98A8C5BFCBC70CC","DCCC2CC521484A17F4F83C08","DCCC6C6965484A17B8F83C80"}
Returns: 28
Submissions are judged against all 110 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TreeReconstruct with a public method int reconstruct(vector<string> g1, vector<string> g2) · 110 test cases · 2 s / 256 MB per case