Statistics

Problem Statement for "InverseHaar1D"

Problem Statement

The Haar wavelet transform is possibly the earliest wavelet transform, introduced by Haar in 1909. The 1-dimensional version of this transform operates on a sequence of integer data as follows: First separate the sequence into pairs of adjacent values, starting with the first and second values, then the third and fourth values, etc. Next, calculate the sums of each of these pairs, and place the sums in order into a new sequence. Then, calculate the differences of each of the pairs (subtract the second value of each pair from the first value), and append the differences in order to the end of the new sequence. The resulting sequence is a level-1 transform. Note that this requires the input sequence to have an even number of elements.

The above describes a level-1 transform. To perform a level-2 transform, we repeat the above procedure on the first half of the sequence obtained from the level-1 transform. The second half of the sequence remains unchanged from the previous level. This pattern continues for higher level transforms (i.e., a level-3 transform operates with the first quarter of the sequence, and so on). Note that this is always possible when the number of elements is a power of 2.

Given the output of a level-L 1D Haar transform in int[] transformedData, create a class InverseHaar1D with a method transform which returns the original data. That is, when a level-L 1D Haar transform is applied to your return value, one should obtain transformedData.

See the examples for clarification.

Definition

Class:
InverseHaar1D
Method:
transform
Parameters:
int[], int
Returns:
int[]
Method signature:
int[] transform(int[] transformedData, int L)
(be sure your method is public)

Constraints

  • transformedData will contain exactly 2, 4, 8, 16 or 32 elements.
  • Each element of transformedData will be between -10000 and 10000, inclusive.
  • L will be between 1 and log2(# of elements in transformedData) inclusive.
  • The elements of transformedData will constitute a valid Haar transform.

Examples

  1. {101, -53}

    1

    Returns: {24, 77 }

    Consider the sequence {24, 77}. Then, the level-1 Haar transform is simply {24+77, 24-77} = {101, -53}, which is exactly transformedData.

  2. {3, 8, -1, -2}

    1

    Returns: {1, 2, 3, 5 }

    Consider the sequence {1, 2, 3, 5}. Start by forming 3=1+2, the sum of the first pair; 8=3+5, the sum of the second pair; -1=1-2, the difference of the first pair; and finally, -2=3-5, the difference of the second pair. To form the output, we create a sequence of the sums in order, and the differences in order. Then, the output for the Haar wavelet transform would be {3, 8, -1, -2}, which is exactly transformedData.

  3. {11, -5, -1, -2}

    2

    Returns: {1, 2, 3, 5 }

    From the previous example, the level-1 Haar transform of {1, 2, 3, 5} gives {3, 8, -1, -2}. Then, the level-2 transform of {1, 2, 3, 5} is simply {11, -5, -1, -2} (11=3+8, -5=3-8), which is once again exactly transformedData.

  4. {369, 477, 451, 262, 47, 135, -125, -2, 18, -23, 30, 101, -5, -18, 54, -20, 11, 45, -5, 70, -24, 2, -50, 15, 55, -62, -23, -17, 44, -8, -44, -52}

    3

    Returns: {62, 51, 70, 25, 32, 37, 81, 11, 72, 96, 70, 68, 43, 93, 25, 10, 67, 12, 11, 73, 56, 79, 68, 85, 68, 24, 15, 23, 6, 50, 12, 64 }

  5. {20, 0, -4, 4, -1, -1, 1, 1}

    3

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

  6. {3, -1}

    1

    Returns: {1, 2 }

  7. {58, -4}

    1

    Returns: {27, 31 }

  8. {115, 160, 25, -16}

    1

    Returns: {70, 45, 72, 88 }

  9. {190, -104, -1, -35}

    2

    Returns: {21, 22, 56, 91 }

  10. {154, 83, 145, 98, -26, -79, 47, 84}

    1

    Returns: {64, 90, 2, 81, 96, 49, 91, 7 }

  11. {125, 208, -39, -110, 17, 70, 17, 33}

    2

    Returns: {30, 13, 76, 6, 33, 16, 96, 63 }

  12. {412, 34, 9, 95, 64, -55, -8, 17}

    3

    Returns: {90, 26, 26, 81, 67, 75, 32, 15 }

  13. {77, 173, 37, 27, 22, 97, 127, 68, 47, -25, -29, 5, -20, 67, 53, 18}

    1

    Returns: {62, 15, 74, 99, 4, 33, 16, 11, 1, 21, 82, 15, 90, 37, 43, 25 }

  14. {215, 207, 248, 194, 67, 49, -68, -16, 47, 18, -50, 71, -34, -20, -21, 57}

    2

    Returns: {94, 47, 46, 28, 39, 89, 75, 4, 28, 62, 69, 89, 34, 55, 81, 24 }

  15. {429, 449, -145, 89, -56, 63, -45, -114, -21, 75, -23, -6, 14, -39, -15, 5}

    3

    Returns: {11, 32, 87, 12, 76, 99, 53, 59, 63, 49, 59, 98, 9, 24, 76, 71 }

  16. {930, -44, 67, -61, 47, -130, 41, 44, -19, -64, -29, -39, 25, -80, 5, -25}

    4

    Returns: {66, 85, 20, 84, 0, 29, 60, 99, 76, 51, 3, 83, 82, 77, 45, 70 }

  17. {171, 69, 129, 69, 99, 150, 129, 27, 117, 163, 160, 75, 88, 133, 51, 181, 25, -51, -9, 31, -51, -44, 37, -19, -43, -29, -12, -17, 46, -1, -3, -13}

    1

    Returns: {98, 73, 9, 60, 60, 69, 50, 19, 24, 75, 53, 97, 83, 46, 4, 23, 37, 80, 67, 96, 74, 86, 29, 46, 67, 21, 66, 67, 24, 27, 84, 97 }

  18. {219, 221, 207, 171, 208, 215, 165, 262, -41, 65, 49, -73, -108, -19, 39, 14, -45, 22, -45, 74, 22, -31, -35, -50, -24, 30, 74, -21, -6, 17, -60, -24}

    2

    Returns: {22, 67, 76, 54, 49, 94, 76, 2, 75, 53, 24, 55, 7, 42, 36, 86, 13, 37, 94, 64, 86, 12, 48, 69, 48, 54, 40, 23, 39, 99, 50, 74 }

  19. {619, 542, 332, 465, 75, 20, -38, -17, 41, -16, -53, -65, -87, -9, 110, 67, 2, -15, 70, 46, -72, -17, -14, -29, 0, -17, -40, 49, -1, 37, -16, 85}

    3

    Returns: {98, 96, 69, 84, 99, 29, 95, 49, 21, 93, 75, 92, 42, 56, 67, 96, 15, 15, 50, 67, 24, 64, 73, 24, 83, 84, 47, 10, 69, 85, 86, 1 }

  20. {659, 785, -19, -15, 28, 47, 9, 132, 128, -20, 83, -52, 21, -100, 34, 82, -39, -13, 1, 31, 30, 37, -19, 71, 57, -36, 44, -40, -48, -22, -60, 22}

    4

    Returns: {56, 95, 5, 18, 32, 31, 57, 26, 84, 54, 46, 9, 14, 33, 85, 14, 83, 26, 26, 62, 44, 0, 52, 92, 51, 99, 47, 69, 24, 84, 24, 2 }

  21. {1504, -368, -18, 50, 5, 17, -19, -151, 48, 61, -53, -62, -29, 42, 26, 53, -12, 44, -24, -23, -51, -62, -8, 36, 34, -33, -17, -59, 8, 30, -17, 54}

    5

    Returns: {41, 53, 45, 1, 37, 61, 7, 30, 0, 51, 21, 83, 15, 23, 68, 32, 69, 35, 50, 83, 66, 83, 24, 83, 47, 39, 45, 15, 79, 96, 88, 34 }

  22. {25, 3}

    1

    Returns: {14, 11 }

  23. {146, 150, 32, -14}

    1

    Returns: {89, 57, 68, 82 }

  24. {296, -4, 32, -14}

    2

    Returns: {89, 57, 68, 82 }

  25. {163, 73, 91, 78, -9, -29, -47, -74}

    1

    Returns: {77, 86, 22, 51, 22, 69, 2, 76 }

  26. {236, 169, 90, 13, -9, -29, -47, -74}

    2

    Returns: {77, 86, 22, 51, 22, 69, 2, 76 }

  27. {405, 67, 90, 13, -9, -29, -47, -74}

    3

    Returns: {77, 86, 22, 51, 22, 69, 2, 76 }

  28. {152, 102, 135, 158, 53, 180, 128, 98, 18, -18, 51, 0, -17, -18, 40, 50}

    1

    Returns: {85, 67, 42, 60, 93, 42, 79, 79, 18, 35, 81, 99, 84, 44, 74, 24 }

  29. {254, 293, 233, 226, 50, -23, -127, 30, 18, -18, 51, 0, -17, -18, 40, 50}

    2

    Returns: {85, 67, 42, 60, 93, 42, 79, 79, 18, 35, 81, 99, 84, 44, 74, 24 }

  30. {547, 459, -39, 7, 50, -23, -127, 30, 18, -18, 51, 0, -17, -18, 40, 50}

    3

    Returns: {85, 67, 42, 60, 93, 42, 79, 79, 18, 35, 81, 99, 84, 44, 74, 24 }

  31. {1006, 88, -39, 7, 50, -23, -127, 30, 18, -18, 51, 0, -17, -18, 40, 50}

    4

    Returns: {85, 67, 42, 60, 93, 42, 79, 79, 18, 35, 81, 99, 84, 44, 74, 24 }

  32. {171, 116, 166, 106, 137, 94, 15, 49, 162, 159, 100, 87, 67, 104, 76, 90, 13, -12, -8, -18, 47, -58, 9, -49, 28, 15, 36, -21, 37, 54, 18, -60}

    1

    Returns: {92, 79, 52, 64, 79, 87, 44, 62, 92, 45, 18, 76, 12, 3, 0, 49, 95, 67, 87, 72, 68, 32, 33, 54, 52, 15, 79, 25, 47, 29, 15, 75 }

  33. {287, 272, 231, 64, 321, 187, 171, 166, 55, 60, 43, -34, 3, 13, -37, -14, 13, -12, -8, -18, 47, -58, 9, -49, 28, 15, 36, -21, 37, 54, 18, -60}

    2

    Returns: {92, 79, 52, 64, 79, 87, 44, 62, 92, 45, 18, 76, 12, 3, 0, 49, 95, 67, 87, 72, 68, 32, 33, 54, 52, 15, 79, 25, 47, 29, 15, 75 }

  34. {559, 295, 508, 337, 15, 167, 134, 5, 55, 60, 43, -34, 3, 13, -37, -14, 13, -12, -8, -18, 47, -58, 9, -49, 28, 15, 36, -21, 37, 54, 18, -60}

    3

    Returns: {92, 79, 52, 64, 79, 87, 44, 62, 92, 45, 18, 76, 12, 3, 0, 49, 95, 67, 87, 72, 68, 32, 33, 54, 52, 15, 79, 25, 47, 29, 15, 75 }

  35. {854, 845, 264, 171, 15, 167, 134, 5, 55, 60, 43, -34, 3, 13, -37, -14, 13, -12, -8, -18, 47, -58, 9, -49, 28, 15, 36, -21, 37, 54, 18, -60}

    4

    Returns: {92, 79, 52, 64, 79, 87, 44, 62, 92, 45, 18, 76, 12, 3, 0, 49, 95, 67, 87, 72, 68, 32, 33, 54, 52, 15, 79, 25, 47, 29, 15, 75 }

  36. {1699, 9, 264, 171, 15, 167, 134, 5, 55, 60, 43, -34, 3, 13, -37, -14, 13, -12, -8, -18, 47, -58, 9, -49, 28, 15, 36, -21, 37, 54, 18, -60}

    5

    Returns: {92, 79, 52, 64, 79, 87, 44, 62, 92, 45, 18, 76, 12, 3, 0, 49, 95, 67, 87, 72, 68, 32, 33, 54, 52, 15, 79, 25, 47, 29, 15, 75 }

  37. {80, 0}

    1

    Returns: {40, 40 }

  38. {94, 94, 0, 0}

    1

    Returns: {47, 47, 47, 47 }

  39. {192, 0, 0, 0}

    2

    Returns: {48, 48, 48, 48 }

  40. {120, 120, 120, 120, 0, 0, 0, 0}

    1

    Returns: {60, 60, 60, 60, 60, 60, 60, 60 }

  41. {384, 384, 0, 0, 0, 0, 0, 0}

    2

    Returns: {96, 96, 96, 96, 96, 96, 96, 96 }

  42. {576, 0, 0, 0, 0, 0, 0, 0}

    3

    Returns: {72, 72, 72, 72, 72, 72, 72, 72 }

  43. {100, 100, 100, 100, 100, 100, 100, 100, 0, 0, 0, 0, 0, 0, 0, 0}

    1

    Returns: {50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50 }

  44. {284, 284, 284, 284, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    2

    Returns: {71, 71, 71, 71, 71, 71, 71, 71, 71, 71, 71, 71, 71, 71, 71, 71 }

  45. {544, 544, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    3

    Returns: {68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68 }

  46. {1408, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    4

    Returns: {88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88 }

  47. {144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 144, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    1

    Returns: {72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72 }

  48. {388, 388, 388, 388, 388, 388, 388, 388, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    2

    Returns: {97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97 }

  49. {776, 776, 776, 776, 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}

    3

    Returns: {97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97 }

  50. {1520, 1520, 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}

    4

    Returns: {95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 95 }

  51. {3200, 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}

    5

    Returns: {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100 }

  52. {-171, -69, -129, -69, -99, -150, -129, -27, -117, -163, -160, -75, -88, -133, -51, -181, -25, 51, 9, -31, 51, 44, -37, 19, 43, 29, 12, 17, -46, 1, 3, 13}

    1

    Returns: {-98, -73, -9, -60, -60, -69, -50, -19, -24, -75, -53, -97, -83, -46, -4, -23, -37, -80, -67, -96, -74, -86, -29, -46, -67, -21, -66, -67, -24, -27, -84, -97 }

  53. {-1408, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    4

    Returns: {-88, -88, -88, -88, -88, -88, -88, -88, -88, -88, -88, -88, -88, -88, -88, -88 }

  54. {-1504, 368, 18, -50, -5, -17, 19, 151, -48, -61, 53, 62, 29, -42, -26, -53, 12, -44, 24, 23, 51, 62, 8, -36, -34, 33, 17, 59, -8, -30, 17, -54} -

    5

    Returns: {-41, -53, -45, -1, -37, -61, -7, -30, 0, -51, -21, -83, -15, -23, -68, -32, -69, -35, -50, -83, -66, -83, -24, -83, -47, -39, -45, -15, -79, -96, -88, -34 }

  55. {-284, -284, -284, -284, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    3

    Returns: {-71, -71, -71, -71, 0, 0, 0, 0, -71, -71, -71, -71, 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: