Statistics

Problem Statement for "SkewTree"

Problem Statement

In a binary tree, every node has an optional left, and optional right child node. A BST (binary search tree) is a binary tree that satsifies the following properties:
1) Every node has a unique value
2) The value at a given node must be greater than the value at every node in its left subtree
3) The value at a given node must be less than the value at every node in its right subtree

The depth of a node in a BST is defined as such:
1) The top node (root) has depth 0
2) Every node has depth 1 higher than its parent

Usually, when given a list of distinct values, it is best to build a balanced binary search tree - a tree where the size of the left subtree is approximately the same as the size of the right subtree at each node. A balanced tree isn't always the best solution though. Given a int[] values of distinct values and a int[] probs containing the percentage chance of each element being accessed, your method will return the best (lowest) access score achievable by a BST containing the given values. The access score of any BST is computed by adding together the access scores for all of its nodes. The access score for a particular node is calculated by the formula p*(d+1) where p is the probability of that node being accessed, and d is the depth of that node in the tree.

Definition

Class:
SkewTree
Method:
bestScore
Parameters:
int[], int[]
Returns:
int
Method signature:
int bestScore(int[] values, int[] probs)
(be sure your method is public)

Constraints

  • values and probs will both contain between 1 and 50 elements, inclusive.
  • Each element of values and probs will be between 1 and 1000, inclusive.
  • Each element of values will be unique.
  • values and probs will contain the same number of elements.

Examples

  1. {1,2}

    {1,2}

    Returns: 4

    The best tree looks like: 2 \ 1

  2. {1,2,4,3,5,6}

    {1,2,3,4,5,6}

    Returns: 44

    Here the best tree is: 5 / \ / \ 3 6 / \ 2 4 / 1 The score is 5*1 + 4*2 + 6*2 + 2*3 + 3*3 + 1*4 = 44

  3. {6,5,3,7,51,36}

    {65,13,49,62,34,16}

    Returns: 492

  4. {44,211,92,88,688,569,143,291,145,28,188,550,331,327,603,46,497,479,250,903,905,735,539,726,382,745,196,57,98,926,728,205,4,366,899}

    {666,256,8,318,743,842,515,415,31,352,929,665,170,512,184,901,613,669,615,971,197,866,803,773,4,564,521,921,306,316,69,921,421,916,985}

    Returns: 74366

  5. {879,244,142,959,141,145,343,881,871,456,398,707,262,566,85,831,518,182,604,179,435,728,763,307,617,545,703,322,930,926,147,424,463,953,209,247,837}

    {169,132,174,184,345,185,521,464,14,97,803,125,950,84,298,255,511,485,785,504,584,493,629,59,917,287,361,832,758,89,526,892,75,360,836,846,103}

    Returns: 61345

  6. {615,534,586,742,107,931,901,856,461,584,191,402,121,274,724,133,896}

    {836,993,91,215,238,457,492,928,87,413,230,556,697,230,281,72,745}

    Returns: 22501

  7. {1}

    {131}

    Returns: 131

  8. {23,407,177,834,724,74,994,2,957,187,83,292,666,642,728}

    {68,558,801,694,634,228,687,337,758,497,917,291,380,773,664}

    Returns: 25603

  9. {581,285,179,839,834,17,462,15,21,346}

    {987,116,287,203,858,985,234,158,211,466}

    Returns: 10873

  10. {161,434,677,710,194,831,344,39,392,363,844,708,814,80,772,2,76,527,960,799,448}

    {707,888,844,907,156,314,532,810,299,787,364,567,548,432,736,680,514,10,333,21,329}

    Returns: 35497

  11. {720,668,144,408}

    {722,746,166,649}

    Returns: 3986

  12. {627,82,208,877,828,392,366,211,886,566,852,719,592}

    {570,765,959,985,119,453,478,78,151,88,23,885,836}

    Returns: 16677

  13. {577}

    {605}

    Returns: 605

  14. {141,649,143,493,651,336,245,825,835,763,583,330,593,918,850,519,250,48,638,37,18,145,64}

    {895,606,107,348,612,897,933,741,800,562,177,729,210,808,302,827,956,182,723,616,434,526,104}

    Returns: 45932

  15. {452,697,903,874,213,652,249,650,102,853,990,597,651,700,147,837,704,911,72,161,511,321,318,716,466,578,619,243,211,595,375,164,115,444,755,158,489,553,848,197,461,708,300,149}

    {124,372,533,223,436,254,929,468,358,906,357,495,879,365,27,390,922,479,930,509,580,649,67,491,794,130,264,331,359,949,596,833,105,714,370,92,203,314,166,898,816,557,658,149}

    Returns: 87928

  16. {996,291,506,945,660,338,772,399,507,876,829,222,857,958,791,4,7,496,985,957,684,553,757,729,305,91,486,827,926}

    {730,608,494,437,24,438,222,129,810,965,138,203,435,606,162,233,47,107,202,799,674,401,619,774,532,237,877,800,836}

    Returns: 49011

  17. {579,511,426,706,70,967,664,785,413,595,409,137,799,621,334,969,416,653,504,606,379,576,913,703,563,376,656,328,97,863,475,208,837,502,723,497,335,742,182,946,710,287}

    {761,228,356,726,820,470,590,836,762,774,200,624,577,601,343,912,223,424,400,823,74,981,198,67,205,787,482,310,919,310,636,239,771,363,441,169,316,803,75,144,945,596}

    Returns: 89255

  18. {916,129,206,881,211,836,616,895,366,317,112,491,422,310,770,401,321,120,131,99,706,899,924,324,982,774,720,694,877,158,330,614,510,210,840,199,538,55,497,9,311,108,272,953,72,542,802,864,162,709}

    {611,873,868,122,949,912,31,408,318,368,766,524,793,163,700,368,513,322,935,887,326,362,523,671,409,711,663,61,847,711,923,747,548,661,780,921,615,795,478,96,245,38,678,809,510,898,696,555,920,852}

    Returns: 133046

  19. {8,18,39,398,553,651,715,729,802,933,988}

    {67,315,298,957,127,599,402,899,716,702,139}

    Returns: 13100

  20. {1,16,75,124,185,186,212,222,236,296,360,363,387,405,420,435,476,518,578,586,714,734,743,777,831,843,902,967}

    {782,804,876,573,891,994,637,658,104,251,229,811,750,692,266,155,154,353,534,396,331,963,478,881,480,155,478,789}

    Returns: 58514

  21. {49,120,246,250,424,516,612}

    {245,80,275,951,525,751,791}

    Returns: 8006

  22. {99,105,481,638,710,715,717,777,804,814,887,939,972,994}

    {10,102,865,131,449,223,6,47,9,966,491,111,821,127}

    Returns: 10070

  23. {167,318,619,629,643,661,784,845,916,978,995}

    {838,923,592,582,641,739,596,412,754,255,737}

    Returns: 19952

  24. {167,173,175,244,296,353,417,488,492,522,540,561,591,620,621,647,709,729,767,771,776,796,815,940}

    {357,327,891,784,406,522,210,793,60,639,867,826,969,694,341,80,95,416,72,971,713,764,588,86}

    Returns: 42793

  25. {3,45,53,127,148,153,176,211,292,303,311,344,411,522,558,609,648,670,675,689,727,731,738,797,860,941,994}

    {395,350,529,119,788,930,947,490,716,589,911,806,193,582,497,44,606,795,628,840,103,744,835,983,948,97,919}

    Returns: 61395

  26. {56,83,108,114,125,127,176,227,233,234,246,256,323,448,467,477,531,563,571,635,709,794,822,850,869,890,893}

    {104,874,806,27,434,15,447,771,745,52,513,734,363,839,668,199,492,550,117,688,709,117,962,916,361,103,307}

    Returns: 46031

  27. {74,136,344,436,566,698,846,908}

    {750,690,235,915,686,590,787,876}

    Returns: 13870

  28. {42,120,215,245,304,401,512,516,542,581,632,681,701,771,781,889,927,939}

    {850,503,557,365,744,671,1,513,600,238,679,169,86,109,300,747,786,664}

    Returns: 27914

  29. {232,923}

    {156,7}

    Returns: 170

  30. {8,22,32,59,66,97,98,114,136,141,200,208,227,231,244,296,297,307,316,326,329,350,420,465,489,491,492,502,568,576,602,617,757,815,888,941,950}

    {688,374,732,376,343,571,142,817,716,120,430,534,773,995,741,21,332,139,861,254,97,503,18,792,458,510,639,862,15,19,859,583,370,218,188,94,441}

    Returns: 65338

  31. {277,527,591,803,865,919}

    {689,113,967,650,37,605}

    Returns: 5947

  32. {10,68,90,97,116,119,149,155,175,191,198,226,228,260,291,308,319,361,380,395,405,423,446,448,606,617,698,731,757,945,958}

    {385,206,584,258,384,908,348,902,65,842,468,386,114,518,198,805,879,123,647,850,664,858,959,311,78,98,858,499,871,258,124}

    Returns: 57355

  33. {33,59,99,100,117,142,190,233,267,275,315,359,360,364,404,414,450,465,471,533,544,582,607,665,713,740,758,773,803,808,812,850,879,917,958}

    {815,355,614,697,367,269,873,340,752,439,967,20,484,532,791,274,876,980,962,31,798,180,204,188,403,827,213,339,793,550,517,68,972,237,999}

    Returns: 73870

  34. {22,80,88,96,145,150,201,205,242,248,286,323,421,431,448,449,453,492,493,506,566,569,595,647,691,739,775,860,904}

    {598,464,926,187,578,426,494,932,995,323,422,385,544,784,75,542,935,494,528,205,52,577,947,955,117,538,528,387,390}

    Returns: 57746

  35. {49,207,347,414,415,560,590,653,694,709,816,840,869,877,891,913}

    {227,715,301,192,429,928,309,559,483,978,549,214,212,854,506,21}

    Returns: 21978

  36. {26,38,61,63,68,77,85,87,97,107,115,141,144,180,220,239,274,280,298,306,310,316,333,393,404,408,411,448,475,489,537,540,581,630,644,663,769,786,806,838,852,855,888,895,924,965,985}

    {641,408,327,880,375,180,517,825,912,78,663,653,549,720,936,635,852,708,761,121,538,662,336,722,401,215,560,157,826,331,658,469,396,895,288,920,748,246,912,663,861,181,914,430,542,502,295}

    Returns: 116341

  37. {84,87,115,187,561,919}

    {819,284,610,400,344,788}

    Returns: 7252

  38. {14,34,60,62,115,122,174,199,225,227,278,352,377,419,440,452,512,550,614,669,721,815,833,835,845,869,881,955,958,984,992,999}

    {12,885,513,312,670,360,497,618,665,77,146,921,580,307,793,323,287,328,562,274,159,405,54,502,211,21,735,360,241,244,11,633}

    Returns: 47665

  39. {217,281,474,492}

    {234,829,538,160}

    Returns: 2853

  40. {153,710}

    {788,477}

    Returns: 1742

  41. {234,564,832,858,874}

    {770,853,892,512,888}

    Returns: 8220

  42. {104,153,155,199,267,270,296,307,388,400,412,417,419,447,460,467,503,561,566,589,639,647,675,678,681,696,712,862,948,970,993}

    {127,806,345,842,45,474,149,417,663,846,210,615,327,210,190,155,4,890,256,452,518,64,134,668,190,184,995,579,735,500,399}

    Returns: 47016

  43. {8,14,28,89,145,170,229,276,331,366,403,491,501,504,505,597,610,821,912}

    {789,983,555,47,976,274,630,472,7,572,761,806,581,176,699,98,27,98,68}

    Returns: 26422

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: