Statistics

Problem Statement for "DecorationDay"

Problem Statement

Partuki and Haverta are playing a game. Partuki places several groups of coins in front of Haverta, and asks her to select one or more of the groups. The groups must be selected so that counts of coins in them do not share any common divisors greater than 1. For example, you could choose a group of 4 coins, a group of 3 coins, and a group of 2 coins because 4, 3 and 2 share no common divisors greater than 1. However, you could not chose a group of 4 coins and a group of 2 coins because 4 and 2 share the common divisor 2.

You are given a int[] groups, each element of which is the number of coins in a single group. Determine the number of different ways in which Haverta can make a valid selection, and return this number modulo 10000003.

Definition

Class:
DecorationDay
Method:
howMany
Parameters:
int[]
Returns:
int
Method signature:
int howMany(int[] groups)
(be sure your method is public)

Constraints

  • groups will contain between 1 and 50 elements, inclusive.
  • Each elements of groups will be between 1 and 100000, inclusive.

Examples

  1. {2, 4, 3}

    Returns: 3

    There are 3 valid selections - {2, 3}, {4, 3} and {2, 4, 3}.

  2. {2, 2, 2, 4}

    Returns: 0

    Groups in any valid selection share the common divisor 2, so there are no valid selections.

  3. {2, 6, 15}

    Returns: 2

    Haverta can choose {2, 15} or {2, 6, 15}.

  4. {2, 5, 98872, 23298, 32872, 23111}

    Returns: 45

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

    Returns: 1002

  6. {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}

    Returns: 9072755

  7. {77619, 40445, 39949, 86247, 28405, 5541, 90560, 351, 89653, 61893, 73932, 83706, 97555, 1138, 67318, 15532, 76313, 80432, 92631, 60908, 38747, 73281, 20524, 7540, 17040, 7928, 45305, 20581, 84199, 21932, 44570, 18247, 48264, 28456, 23784, 95789, 39561, 13919}

    Returns: 7684857

  8. {70807, 25481, 7004, 63236, 69457, 71629, 62520, 20376, 23993, 27988, 90245, 81559}

    Returns: 4055

  9. {86136, 47495, 92522, 13284, 64068, 58146, 31380}

    Returns: 62

  10. {82477, 77231, 19036, 30735, 63918, 45608, 36985, 68435, 33700, 54850, 83450, 77943, 74274, 69083, 29135, 23936, 21106, 22281, 4087, 79318, 33993, 26002, 81158, 67713, 42502, 77561, 68019, 75948, 65415}

    Returns: 6853035

  11. {17052, 38284, 92231, 9439, 46070, 85594, 48248, 7234, 58037}

    Returns: 444

  12. {69369, 84501, 6931, 62946, 21524, 25476, 9569, 41323, 23671, 17513, 74344, 92072, 12428, 52218, 81146, 35800, 2711, 1692, 39194, 40403, 43788, 38582, 85925, 38307, 87883, 35296, 18011, 62220, 61081, 78778, 37038, 48907, 21724, 52281, 51462, 93436, 94130, 18876, 39502, 27414, 90991, 96861, 30206, 91986}

    Returns: 3594365

  13. {96547, 43590, 51337, 22625, 26867, 33460, 71355, 14825, 63335, 10979, 30475, 98476, 8311, 38880, 72679, 29894, 11540, 80794, 14278, 90466}

    Returns: 1047554

  14. {76389, 13227, 57362, 66311, 29130, 5606, 89838, 99528, 96623, 14041, 77516, 88047, 36638, 42999, 37656, 94467, 60341, 3016}

    Returns: 261126

  15. {19149, 99306, 74538, 40639, 5351, 94361, 76434, 60052, 86227, 85419}

    Returns: 980

  16. {51582, 49801, 42052, 10992, 49606, 78696, 1482, 92221, 45929, 44654, 73421, 44576, 35985, 94307, 26935, 61638, 72143, 18767, 85553, 15071, 91926, 8107, 99855, 51523, 23415, 50485}

    Returns: 7107308

  17. {60591, 94549, 79101, 25591, 63053, 23652, 44252}

    Returns: 113

  18. {71698, 64035, 18309, 31232, 74208, 92435, 14387, 23212, 1964, 62003, 50178, 14051, 27034, 74458, 78490, 21275, 45956, 86768}

    Returns: 260064

  19. {66948, 75674, 50440, 43683, 81589, 70915, 38046, 70516, 31569, 8993, 77961, 53746, 39286}

    Returns: 8014

  20. {68062, 72480, 75618, 9011, 72289, 61788, 41922, 40832, 10920, 48882, 52536, 34167, 93869, 79339, 41736, 14202, 17072, 88162}

    Returns: 253428

  21. {19602, 63175, 83383, 80545, 41073, 99587, 6877, 49901, 65232, 95873, 36046, 66607, 58327, 20649, 77790, 43043, 24923, 46790, 81612, 68225, 7201, 47938, 10261, 36105, 58945, 30302, 51331, 31339, 11686, 57387, 23043, 96371, 90705}

    Returns: 9930168

  22. {71892, 28336, 60061, 46776, 23227, 42848, 75006, 35423, 35572, 85242, 78339, 76473, 76835, 951}

    Returns: 16139

  23. {27191, 4040, 24669, 49874, 62934, 76816, 51210, 92636, 78686, 69960, 27289, 86699, 7413, 42093, 26644}

    Returns: 32197

  24. {41213, 14655, 64151, 32204}

    Returns: 11

  25. {19252, 42556, 19759, 81655, 64296, 40521, 73082, 71585, 29266, 37746, 55957}

    Returns: 1975

  26. {85874, 32299, 86520, 78649, 19591, 60047, 41164, 11619, 93917, 43814, 33517, 34338, 46563, 23990, 5105, 55612, 89787, 97321, 11810, 44545, 44970, 54647, 66951, 87933, 48111, 5040, 69697, 63223, 18928, 49512, 12529, 96042, 57392, 91551, 56823, 6653, 75614, 85644, 36757, 5664, 77575, 88997, 22738, 87397, 11466}

    Returns: 878108

  27. {94778, 47257, 40396, 37276, 32290, 81790, 7138, 53028, 46410, 99110, 71692, 75012, 76923, 49230, 47970, 13486, 42192, 22997, 99365, 49229, 10194, 27511, 56824, 93685, 65403, 56906, 49096, 65099, 17979, 66740, 54662, 99054, 14809, 3815, 90006, 47777, 87921, 97370, 68992, 75063, 47996, 2150, 10851, 51833, 6349, 27162}

    Returns: 4562441

  28. {790, 52664, 88283, 44918, 68232, 88109, 51419, 76090, 43711, 53826, 42036, 96006, 28780, 53487, 82754, 3771, 75148, 51826, 63514, 29822, 20111, 97490, 86667, 19751, 38788}

    Returns: 3488710

  29. {91312, 25017, 5411, 58171, 65710, 55052}

    Returns: 53

  30. {98827, 85424, 42374, 1605, 2637, 39517, 62952, 84221, 8750, 15859, 69220, 65628, 12559, 49570, 6509, 91323, 23945, 83495, 78151, 92568, 20586}

    Returns: 2096462

  31. {55709, 11423, 5405, 91608, 37201, 40949}

    Returns: 57

  32. {81216, 58381, 68865, 42415, 89577, 8345, 47319, 91350, 52849, 10918, 53634, 64739, 87033, 58055, 26478, 36066, 21865, 58975, 62959, 98434, 45441, 97205, 70641, 2940, 62231, 45540, 18173, 68148, 49650, 26927, 94660, 20729, 61090, 60050, 57771, 61222, 32313}

    Returns: 8732564

  33. {11155, 57739, 11050, 81783, 74212, 49733, 17661, 1938, 45334, 95306, 49484, 91830, 16828, 93345, 45981, 29228, 7981, 10893, 58812, 9089, 33136, 683, 80883, 59703, 69411, 49905, 92329, 4573, 2344, 47798, 30197, 38521, 68557, 66000, 702, 41505, 84535, 93753, 80977, 56745, 82602, 96843, 6173, 56182, 82615}

    Returns: 876714

  34. {89774, 26481, 57250, 60321, 90884, 29431, 61454, 21540, 69743, 94862, 97416, 45108, 36937, 43442, 33069, 90370, 23440, 60046}

    Returns: 257974

  35. {6859, 87743, 36742, 48589, 55297, 59241, 63248, 53692, 51690, 54385, 54787, 38322, 61857, 30888, 15015, 14433, 32795, 62244, 45708, 21802, 92516, 73369, 64535}

    Returns: 8387053

  36. {28488, 94198, 47511, 87916, 96077, 13631, 96918, 6410, 1405, 97795, 19307, 87067, 39970, 70809, 4780, 13760, 9162, 35132, 20128, 38819, 81162, 22528}

    Returns: 4186005

  37. {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}

    Returns: 9072755

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

    Returns: 7554058

  39. {2, 4, 2, 4, 8, 2, 4, 8, 8, 4, 2, 4, 8, 4, 2, 4,8, 4,2, 4, 8, 2, 4, 8, 2, 4, 8, 8, 4, 2, 4, 8, 4,2, 4,8, 4, 2, 4, 8, 8, 4, 2, 2, 4,4, 4, 8}

    Returns: 0

  40. {2, 2, 3}

    Returns: 3

    Here there are three ways to make a selection: pile 0 (2 coins) and pile 2 (3 coins); pile 1 (2 coins) and pile 2 (3 coins); all three piles.

  41. {100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000}

    Returns: 0

  42. {100000, 99999, 99998, 99997, 99996, 99995, 99994, 99993, 99992, 99991, 99990, 99989, 99988, 99987, 99986, 99985, 99984, 99983, 99982, 99981, 99980, 99979, 99978, 99977, 99976, 99975, 99974, 99973, 99972, 99971, 99970, 99969, 99968, 99967, 99966, 99965, 99964, 99963, 99962, 99961, 99960, 99959, 99958, 99957, 99956, 99955, 99954, 99953, 99952, 99951}

    Returns: 5386375

  43. {1}

    Returns: 1

  44. {1, 1}

    Returns: 3

  45. {1, 100000, 100000}

    Returns: 4

  46. {100000}

    Returns: 0

  47. {1, 100000, 99999}

    Returns: 5

  48. {2, 1}

    Returns: 2

  49. {2, 6, 15 }

    Returns: 2

  50. {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: 5451922

  51. {42, 18468, 6335, 26501, 19170, 15725, 11479, 29359, 26963, 24465, 5706, 28146, 23282, 16828, 962, 492, 2996, 11943, 4828, 5437, 32392, 14605, 3903, 154, 293, 12383, 17422, 18717, 2, 19896, 5448, 21727, 14772, 11539, 1870, 19913, 25668, 26300, 17036, 9895, 28704, 23812, 31323, 30334, 17674, 4665, 15142, 7712, 28254, 6869 }

    Returns: 1943159

  52. {99999, 99415, 98831, 98247, 97663, 97079, 96495, 95911, 95327, 94743, 94159, 93575, 92991, 92407, 91823, 91239, 90655, 90071, 89487, 88903, 88319, 87735, 87151, 86567, 85983, 85399, 84815, 84231, 83647, 83063, 82479, 81895, 81311, 80727, 80143, 79559, 78975, 78391, 77807, 77223, 76639, 76055, 75471, 74887, 74303, 73719, 73135, 72551, 71967, 71383 }

    Returns: 8940492

  53. {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229 }

    Returns: 9072705

  54. {11, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 4, 2, 42, 42, 42, 42, 42, 42, 42 }

    Returns: 4536377

  55. {2 }

    Returns: 0

  56. {46, 4572, 234, 7, 324, 67, 34, 73, 437, 78, 346, 37, 568, 346, 58, 3456, 85, 346, 68, 36, 6487, 3457, 685, 47, 4568, 457, 345, 643, 7, 4567, 745, 457, 324, 6, 34 }

    Returns: 9465620

  57. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 3, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 9, 27, 81, 243, 729, 18, 54, 162, 486, 1458, 36, 108, 324, 972, 2916, 5832, 5, 50, 15 }

    Returns: 5771112

  58. {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 }

    Returns: 3741502

  59. {6, 10, 15 }

    Returns: 1

  60. {40051, 32625, 50524, 77311, 97146, 39100, 69636, 63902, 75553, 4736, 29315, 91378, 58264, 9596, 74372, 5629, 70414, 1, 64751, 6469, 6382, 58322, 89, 52687, 1813, 43626, 67096, 15074, 24897, 48841, 17302, 81300, 81465, 67825, 58610, 94962, 2, 5, 58863, 19848, 49333, 4530, 6557, 7596, 14125, 80929, 63891, 84539, 12553, 44994 }

    Returns: 5501284

  61. {3 }

    Returns: 0

  62. {46, 4572, 234, 7, 324, 67, 34, 73, 437, 78, 346, 37, 568, 346, 58, 3456, 85, 346, 68, 36, 6487, 3457, 685, 47, 4568, 457, 345, 643, 7, 4567, 745, 457, 324, 6, 34, 2325, 235, 46, 23, 6, 3426, 236, 234, 32, 436 }

    Returns: 7972844

  63. {15, 21, 35 }

    Returns: 1

  64. {5, 5, 5, 5, 5, 90090, 44444, 51553, 31555, 51553, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 3, 3, 3, 3, 3, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6 }

    Returns: 9786227

  65. {6, 15, 10 }

    Returns: 1

  66. {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, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 }

    Returns: 4536378

  67. {36773, 42610, 7363, 28950, 18729, 58356, 27092, 63702, 22718, 84511, 98077, 3248, 49764, 82133, 49776, 58939, 23076, 44080, 54760, 35073, 32683, 98841, 54511, 55363, 12597, 7814, 96907, 33314, 29484, 39951, 48755, 67899, 27564, 34503, 49728, 45555, 60391, 48907, 49939, 81830, 87155, 92792, 43670, 65782, 86463, 8507, 93159, 13846, 60168, 15228 }

    Returns: 195857

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: