Statistics

Problem Statement for "LittleElephantAndIntervalsDiv2"

Problem Statement

Little Elephant from the Zoo of Lviv has some balls arranged in a row. Each ball can be painted in one of two possible colors: black or white. Initially all the balls are painted white.

You are given an int M, which represents the number of balls in the row. The balls are numbered from left to right, starting from 1. You are also given two int[]s L and R. To repaint balls, Little Elephant wants to use a robot. The robot will paint the balls in several consecutive stages. For each i, the i-th stage (1-based index) will look as follows: First, the robot will choose one of the two colors: white or black. Then, the robot will paint the balls with indices from L[i-1] to R[i-1], inclusive, using the chosen color. (Painting a ball covers all previous layers of paint.)

Return the number of different colorings Little Elephant can get after the last stage. (Two colorings are considered different if there exists some ball that is white in one coloring and black in the other one).

Definition

Class:
LittleElephantAndIntervalsDiv2
Method:
getNumber
Parameters:
int, int[], int[]
Returns:
int
Method signature:
int getNumber(int M, int[] L, int[] R)
(be sure your method is public)

Constraints

  • M will be between 1 and 100, inclusive.
  • L will contain between 1 and 10 elements, inclusive.
  • R will contain the same number of elements as L.
  • Each element of R will be between 1 and M, inclusive.
  • i-th element of L will be between 1 and R[i], inclusive.

Examples

  1. 4

    {1, 2, 3}

    {1, 2, 3}

    Returns: 8

    In the three stages the robot will choose the color for balls number 1, 2, and 3. The choices are independent of each other. The last, fourth ball will always remain white. Thus there are 2*2*2 = 8 different colorings.

  2. 3

    {1, 1, 2}

    {3, 1, 3}

    Returns: 4

    In the first stage the robot colors all three balls. The color chosen for the first stage does not matter, because in the second stage the robot will repaint ball 1, and in the third stage it will repaint balls 2 and 3.

  3. 100

    {47}

    {74}

    Returns: 2

  4. 100

    {10, 20, 50}

    {20, 50, 100}

    Returns: 8

  5. 1

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: 2

  6. 42

    {5, 23, 4, 1, 15, 2, 22, 26, 13, 16}

    {30, 41, 17, 1, 21, 6, 28, 30, 15, 19}

    Returns: 512

  7. 5

    {1, 2, 1, 4, 1, 1, 3, 2, 1, 4}

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

    Returns: 16

  8. 23

    {14, 18, 2, 3, 15, 4, 3, 9, 17, 19}

    {20, 19, 7, 15, 22, 6, 3, 13, 20, 23}

    Returns: 256

  9. 43

    {6, 11, 1, 3, 10, 6, 13, 13, 18, 5}

    {31, 11, 1, 13, 24, 33, 43, 13, 22, 5}

    Returns: 128

  10. 57

    {11, 12, 17, 1, 28, 19, 21, 10, 50, 19}

    {42, 24, 32, 7, 38, 50, 31, 12, 51, 19}

    Returns: 256

  11. 91

    {55, 6, 17, 80, 83, 24, 2, 54, 62, 61}

    {61, 12, 22, 82, 91, 27, 4, 54, 68, 68}

    Returns: 512

  12. 96

    {23, 53, 95, 29, 71, 48, 10, 96, 16, 78}

    {24, 53, 96, 35, 78, 55, 17, 96, 21, 87}

    Returns: 512

  13. 99

    {66, 87, 84, 79, 10, 52, 86, 4, 66, 74}

    {74, 93, 84, 87, 11, 57, 95, 11, 69, 75}

    Returns: 128

  14. 93

    {78, 54, 47, 28, 43, 26, 85, 47, 39, 69}

    {79, 58, 53, 36, 51, 27, 88, 55, 39, 76}

    Returns: 512

  15. 98

    {5, 51, 70, 3, 78, 2, 22, 21, 56, 63}

    {8, 54, 71, 10, 82, 8, 23, 30, 62, 66}

    Returns: 256

  16. 95

    {84, 25, 23, 61, 94, 68, 4, 26, 64, 37}

    {88, 34, 28, 64, 95, 72, 12, 34, 64, 45}

    Returns: 512

  17. 92

    {86, 42, 49, 47, 59, 67, 47, 36, 21, 11}

    {92, 49, 51, 49, 68, 74, 48, 44, 22, 15}

    Returns: 1024

  18. 93

    {61, 48, 51, 69, 55, 22, 7, 52, 27, 19}

    {69, 50, 56, 78, 59, 23, 9, 53, 34, 21}

    Returns: 1024

  19. 100

    {76, 1, 4, 62, 2, 56, 3, 83, 89, 18}

    {78, 1, 13, 70, 11, 59, 8, 88, 95, 25}

    Returns: 1024

  20. 93

    {57, 16, 78, 82, 49, 47, 89, 27, 19, 34}

    {66, 17, 84, 90, 54, 51, 90, 32, 27, 43}

    Returns: 1024

  21. 94

    {18, 50, 84, 33, 6, 8, 87, 49, 48, 67}

    {23, 56, 84, 39, 10, 12, 92, 49, 50, 71}

    Returns: 512

  22. 97

    {11, 42, 9, 72, 42, 91, 15, 62, 47, 71}

    {15, 43, 9, 74, 47, 92, 21, 62, 52, 76}

    Returns: 256

  23. 93

    {62, 49, 14, 48, 67, 49, 22, 3, 74, 11}

    {63, 59, 20, 67, 86, 53, 32, 12, 87, 13}

    Returns: 256

  24. 99

    {60, 6, 66, 62, 59, 85, 36, 63, 54, 83}

    {67, 24, 68, 79, 73, 99, 48, 76, 61, 99}

    Returns: 128

  25. 98

    {36, 98, 43, 65, 10, 1, 50, 74, 48, 28}

    {46, 98, 48, 65, 17, 20, 55, 78, 60, 29}

    Returns: 256

  26. 94

    {79, 52, 60, 49, 79, 5, 89, 49, 31, 2}

    {84, 57, 72, 51, 83, 12, 94, 59, 46, 13}

    Returns: 128

  27. 91

    {60, 6, 50, 57, 83, 5, 91, 82, 38, 10}

    {77, 6, 69, 81, 83, 24, 91, 91, 56, 19}

    Returns: 32

  28. 99

    {52, 86, 70, 46, 6, 21, 33, 88, 61, 59}

    {71, 86, 80, 56, 26, 22, 51, 99, 68, 74}

    Returns: 512

  29. 98

    {80, 78, 44, 42, 43, 26, 14, 4, 89, 29}

    {98, 80, 47, 62, 55, 47, 25, 4, 98, 45}

    Returns: 512

  30. 91

    {34, 14, 68, 45, 1, 15, 13, 89, 60, 16}

    {45, 25, 71, 60, 14, 30, 25, 89, 68, 31}

    Returns: 256

  31. 98

    {12, 89, 50, 52, 10, 44, 6, 55, 58, 2}

    {12, 98, 60, 66, 18, 51, 26, 73, 82, 2}

    Returns: 128

  32. 92

    {1, 65, 3, 42, 33, 66, 18, 88, 14, 51}

    {26, 77, 16, 48, 39, 72, 45, 92, 40, 58}

    Returns: 512

  33. 93

    {70, 54, 58, 50, 50, 70, 57, 51, 52, 68}

    {76, 65, 67, 55, 72, 75, 69, 55, 74, 93}

    Returns: 16

  34. 100

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

    Returns: 1024

  35. 100

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

    {100, 100, 100, 100, 100, 100, 100, 100, 100, 100}

    Returns: 1024

  36. 100

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

    {100, 99, 98, 97, 96, 95, 94, 93, 92, 91}

    Returns: 1024

  37. 100

    {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}

    {4, 4, 8, 8, 12, 12, 16, 16, 20, 20}

    Returns: 1024

  38. 100

    {3, 1, 7, 5, 11, 9, 15, 13, 19, 17}

    {4, 4, 8, 8, 12, 12, 16, 16, 20, 20}

    Returns: 32

  39. 100

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 1}

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 99}

    Returns: 2

  40. 100

    {1, 1, 2, 3, 4, 5, 6, 7, 8, 9}

    {99, 1, 2, 3, 4, 5, 6, 7, 8, 9}

    Returns: 1024

  41. 100

    {1, 50, 50}

    {50, 100, 50}

    Returns: 8

  42. 100

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    {100, 100, 100, 100, 100, 100, 100, 100, 100, 100}

    Returns: 2

  43. 42

    {5, 23, 4, 1, 15, 2, 22, 26, 13, 16 }

    {30, 41, 17, 1, 21, 6, 28, 30, 15, 19 }

    Returns: 512

  44. 4

    {1, 1, 3 }

    {3, 2, 3 }

    Returns: 4

  45. 3

    {1, 2 }

    {3, 2 }

    Returns: 4

  46. 3

    {1, 1, 2 }

    {3, 1, 3 }

    Returns: 4

  47. 4

    {1, 1, 1, 1 }

    {4, 4, 4, 4 }

    Returns: 2

  48. 10

    {1, 5, 5 }

    {10, 10, 5 }

    Returns: 8

  49. 4

    {1, 2, 2 }

    {4, 2, 2 }

    Returns: 4

  50. 3

    {1, 3 }

    {3, 3 }

    Returns: 4

  51. 1

    {1, 1, 1 }

    {1, 1, 1 }

    Returns: 2

  52. 10

    {1, 3, 6 }

    {9, 4, 7 }

    Returns: 8

  53. 50

    {1, 3 }

    {10, 6 }

    Returns: 4

  54. 100

    {10, 20, 30, 40, 50 }

    {90, 80, 70, 60, 50 }

    Returns: 32

  55. 5

    {1, 2, 3 }

    {5, 4, 3 }

    Returns: 8

  56. 3

    {1, 1 }

    {3, 3 }

    Returns: 2

  57. 6

    {4, 3 }

    {5, 6 }

    Returns: 2

  58. 100

    {1, 1, 2, 8, 10, 56, 14 }

    {1, 10, 100, 9, 54, 58, 16 }

    Returns: 64

  59. 10

    {1, 2 }

    {6, 5 }

    Returns: 4

  60. 100

    {10, 10, 10 }

    {20, 20, 20 }

    Returns: 2

  61. 4

    {1, 2 }

    {4, 3 }

    Returns: 4

  62. 4

    {1, 3, 4 }

    {1, 3, 4 }

    Returns: 8

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: