Statistics

Problem Statement for "ColourHolic"

Problem Statement

Vendelín has a part-time job in an "all for 1 euro" bargain store. He was given the task of putting several items into a row on one long shelf in the display window.


Vendelín is shape-blind: he only cares about the items' colours. This time, he sees that each of his items comes in one of just 4 colours: turquoise, magenta, beige and lavender (but don't worry, we've numbered them 0 through 3 for your convenience). Also, in order to attract customers, he wants each two adjacent items on the shelf to have different colours.


You're given an int[] n with 4 elements. For each i, Vendelín has n[i] items of colour i.


Compute and return the number of sequences of items such that no two adjacent items share the same colour. Since this number can get very large, return it modulo 1,000,000,009.

Definition

Class:
ColourHolic
Method:
countSequences
Parameters:
int[]
Returns:
int
Method signature:
int countSequences(int[] n)
(be sure your method is public)

Constraints

  • n will contain exactly 4 elements.
  • Each element of n will be between 0 and 50,000, inclusive.
  • There will be at least 1 item, so the elements of n won't all be equal to 0.
  • At least 2 elements of n won't exceed 200.

Examples

  1. {1,0,2,3}

    Returns: 10

    There are 10 possible sequences of 1 turquoise (colour 0), 2 beige (colour 2) and 3 lavender (colour 3) items with no two adjacent items sharing the same colour. For example, (0,3,2,3,2,3) or (3,2,0,3,2,3) are valid sequences of colours. However, (3,2,2,3,2,3) isn't valid.

  2. {1,1,1,1}

    Returns: 24

    All 4! permutations of these items are valid.

  3. {42,42,42,9001}

    Returns: 0

    There are way too many items of colour 3. In any sequence, there would be two adjacent items of this colour.

  4. {8,0,0,8}

    Returns: 2

  5. {0,5,1,3}

    Returns: 4

  6. {4,2,1,3}

    Returns: 1074

  7. {15,900,357,22}

    Returns: 0

  8. {110,30000,200,29999}

    Returns: 118115350

    Make sure you're using 109+9 as the modulus!

  9. {0,0,1,0}

    Returns: 1

  10. {2,0,0,0}

    Returns: 0

  11. {0,1,0,1}

    Returns: 2

  12. {2,0,0,1}

    Returns: 1

  13. {5,0,0,0}

    Returns: 0

  14. {50000,0,49999,0}

    Returns: 1

  15. {50000,0,0,50000}

    Returns: 2

  16. {0,0,49992,49990}

    Returns: 0

  17. {0,49999,0,0}

    Returns: 0

  18. {1,1,0,1}

    Returns: 6

  19. {1,1,0,2}

    Returns: 6

  20. {1,1,0,3}

    Returns: 2

  21. {10,0,20,10}

    Returns: 2217072

  22. {10,0,21,10}

    Returns: 184756

  23. {10,0,9,55}

    Returns: 0

  24. {0,10,9,8}

    Returns: 12748518

  25. {0,1,45,45}

    Returns: 270

  26. {0,4000,1,4001}

    Returns: 16002

  27. {0,4000,4000,1}

    Returns: 24000

  28. {1500,1520,200,0}

    Returns: 60429169

  29. {2,2,2,2}

    Returns: 864

  30. {2,2,3,2}

    Returns: 1686

  31. {2,50000,2,50000}

    Returns: 826279104

  32. {40,47,0,42}

    Returns: 427442006

  33. {200,200,200,200}

    Returns: 633377502

  34. {200,199,200,200}

    Returns: 161286308

  35. {200,201,200,200}

    Returns: 548618418

  36. {200,201,199,200}

    Returns: 377969678

  37. {200,201,198,200}

    Returns: 78933789

  38. {199,199,199,198}

    Returns: 903983381

  39. {199,199,199,199}

    Returns: 247406595

  40. {200,201,200,203}

    Returns: 272436774

  41. {199,201,201,200}

    Returns: 990170716

  42. {4,40,400,420}

    Returns: 699730170

  43. {1,10,100,105}

    Returns: 546228900

  44. {0,10,100,105}

    Returns: 512698447

  45. {50000,200,200,50000}

    Returns: 947551947

  46. {50000,200,199,50000}

    Returns: 281708049

  47. {50000,199,199,50000}

    Returns: 652623679

  48. {50000,199,199,49000}

    Returns: 0

  49. {190,199,5000,4900}

    Returns: 343265018

  50. {190,199,50000,49800}

    Returns: 557418406

  51. {190,1,49999,49999}

    Returns: 378303083

  52. {200,49999,49999,1}

    Returns: 361321927

  53. {200,49999,49999,200}

    Returns: 914232214

  54. {200,49999,201,200}

    Returns: 0

  55. {200,49999,210,200}

    Returns: 0

  56. {50000,50000,98,98}

    Returns: 756510847

  57. {50000,49999,198,199}

    Returns: 798886135

  58. {50000,49000,198,199}

    Returns: 0

  59. {49000,200,200,49999}

    Returns: 0

  60. {10000,0,200,20000}

    Returns: 0

  61. {10000,0,1,10003}

    Returns: 0

  62. {0,400,200,200}

    Returns: 789733872

  63. {0,401,200,200}

    Returns: 23711554

  64. {0,402,200,200}

    Returns: 0

  65. {0,510,200,200}

    Returns: 0

  66. {0,50000,200,200}

    Returns: 0

  67. {60,142,36282,43211}

    Returns: 0

  68. {142,36,45100,14274}

    Returns: 0

  69. {15,172,83,114}

    Returns: 54344093

  70. {52,37,0,95}

    Returns: 0

  71. {99,100,689,313}

    Returns: 0

  72. {26973,45861,98,94}

    Returns: 0

  73. {36448,6046,18,95}

    Returns: 0

  74. {68,12719,68,12741}

    Returns: 948606847

  75. {87,47830,43375,65}

    Returns: 0

  76. {100,47830,43375,100}

    Returns: 0

  77. {84,21831,97,63}

    Returns: 0

  78. {101,75,1,83}

    Returns: 732292681

  79. {35523,35556,33,84}

    Returns: 643718892

  80. {151,73,22519,22362}

    Returns: 499118849

  81. {200, 200, 5000, 5000 }

    Returns: 471897699

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: