Statistics

Problem Statement for "CoolFunction"

Problem Statement

The function f: R -> R is called cool if there are integer numbers a0 <= a1 <= ... <= ak-1 (k >= 1) such that f(x) = |x - a0| + |x - a1| + ... + |x - ak-1| for every real value of x.

You will be given a int[] values, containing n elements. You should find a cool function f such that f(i) = values[i] for every i, where 0 <= i < n. Return a int[], containing the values a0, a1, ..., ak-1 for this function. If there are many possible answers, choose the one with the smallest number of elements. If tie still exists, return the lexicographically smallest int[]. Constraints will guarantee that values corresponds to at least one cool function.

Definition

Class:
CoolFunction
Method:
restore
Parameters:
int[]
Returns:
int[]
Method signature:
int[] restore(int[] values)
(be sure your method is public)

Constraints

  • values will contain between 1 and 50 elements, inclusive.
  • Each element of values will be between 0 and 50, inclusive.
  • values will correspond to at least one cool function.

Examples

  1. {0}

    Returns: {0 }

    |x| is acceptable here.

  2. {50}

    Returns: {-50 }

    Here there are two variants with k=1: |x-50| and |x+50|. The second one is lexicographically smaller.

  3. {2, 4}

    Returns: {-2, 0 }

  4. {3, 3}

    Returns: {-2, 1 }

  5. {5, 1}

    Returns: {1, 1, 1, 2 }

    The return is not necessarily strictly increasing.

  6. {10, 4, 6}

    Returns: {1, 1, 1, 1, 2, 4 }

  7. {35,34}

    Returns: {35 }

  8. {43,34,41}

    Returns: {1, 1, 1, 1, 1, 1, 1, 1, 35 }

  9. {25,17,19,41}

    Returns: {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

  10. {22,18,22,28,38}

    Returns: {-10, 0, 0, 1, 1, 1, 1, 2, 3, 3 }

  11. {40,26,20,30,40,50}

    Returns: {1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 5, 15 }

  12. {31,23,23,27,31,39,47}

    Returns: {-9, 1, 1, 1, 1, 2, 2, 4, 4, 6 }

  13. {33,26,25,26,27,28,37,46}

    Returns: {-8, 1, 1, 1, 2, 5, 5, 5, 5 }

  14. {1,1}

    Returns: {0, 1 }

  15. {50,0,50}

    Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

  16. {0,50}

    Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  17. {32,23,18,15,16}

    Returns: {1, 1, 2, 3, 3, 4, 4, 4, 10 }

  18. {17,11,9,9,15}

    Returns: {0, 1, 1, 2, 3, 3, 3, 4 }

  19. {15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34}

    Returns: {15 }

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

    Returns: {-1 }

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

    Returns: {50 }

  22. {50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50}

    Returns: {-1, 49 }

  23. {6,6,6}

    Returns: {-4, 2 }

  24. {21,20,19,18,17,16,15,14,13,12,11,10,9}

    Returns: {21 }

  25. {20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26}

    Returns: {20 }

  26. {34,32,30,28,26,24,22,20,18,16,14,12,10,8,6,4,2,0,2,4,6,8,10,12,14,16,18,20,22,24,26,28}

    Returns: {17, 17 }

  27. {15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39}

    Returns: {-15 }

  28. {32,30,28,26,24,22,20,18,16,14,12,10,8,6,4,2,2,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36}

    Returns: {15, 17 }

  29. {47,44,41,38,35,32,29,26,25,24}

    Returns: {7, 9, 31 }

  30. {41,26,23,24,29,36}

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

  31. {13,7,5,5,11,17,23,29}

    Returns: {1, 1, 2, 3, 3, 3 }

  32. {42,34,32,32,38}

    Returns: {1, 1, 1, 2, 3, 3, 3, 28 }

  33. {18,32,46}

    Returns: {-18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  34. {50,37,24}

    Returns: {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 26 }

  35. {39,30}

    Returns: {1, 1, 1, 1, 1, 1, 1, 1, 31 }

  36. {40,30,20}

    Returns: {2, 2, 2, 2, 2, 2, 2, 2, 2, 22 }

  37. {31,20,9,6,13,24,35}

    Returns: {2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4 }

  38. {17,5}

    Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6 }

  39. {13,0}

    Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

  40. {41,24,19,24}

    Returns: {1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 10 }

  41. {16,0,16,32}

    Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

  42. {0,23}

    Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  43. {31,13,9}

    Returns: {1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4 }

  44. {18,16,50}

    Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

  45. {18,14,46}

    Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

  46. {50,25,0}

    Returns: {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

  47. {50,50}

    Returns: {-49, 1 }

  48. {50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50, 50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50, 50,50,50,50,50,50,50,50,50,50}

    Returns: {-1, 49 }

  49. {47,41,35,29,23,17,11,5,1,7,13,19,25,31,37,43}

    Returns: {7, 8, 8, 8, 8, 8 }

  50. {38,34,30,26,22,18,14,10,10,10,10,12,14,16,18,22,26,30,34,38,42,46,50}

    Returns: {7, 7, 10, 14 }

  51. {48,43,38,33,28,23,20,17,18,19,20,21,22,23,24,27,32,37,42,47}

    Returns: {5, 7, 7, 14, 15 }

  52. {50,46,42,40,38,36,34,32,30,28,26,24,22,20,20,20,20,22,24,26,30,34,38,42,46,50}

    Returns: {2, 13, 16, 19 }

  53. {47,44,41,38,35,32,29,28,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48}

    Returns: {6, 8, 33 }

  54. {50,48,46,44,42,40,38,36,34,32,30,28,26,24,22,20,18,16,14,12,10,8,8,8,8,8,8,8,8,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48}

    Returns: {21, 29 }

  55. {50,47,44,41,38,35,32,29,26,23,20,17,14,11,8,5,2,1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49}

    Returns: {16, 17, 17 }

  56. {50,46,42,38,34,30,26,22,18,14,10,6,4,4,6,10,14,18,22,26,30,34,38,42,46}

    Returns: {11, 12, 13, 14 }

  57. {46,41,36,31,28,27,26,25,24,23,22,21,22,23,24,29,34,39,44,49}

    Returns: {3, 4, 11, 14, 14 }

  58. {49,38,31,28,29,30,31,34,41,50}

    Returns: {1, 1, 2, 2, 3, 3, 6, 7, 7, 8, 9 }

  59. {40,20,0,20,40}

    Returns: {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

  60. {47,16,15,46}

    Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

  61. {34}

    Returns: {-34 }

  62. {48, 32, 32, 32, 48 }

    Returns: {-12, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3, 3, 3, 4 }

  63. {0, 50 }

    Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

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: