Statistics

Problem Statement for "LimitedMemorySeries1"

Problem Statement

You are given an array X that contains n integers. You are then given some queries. Each query is described by a single integer q. The answer to the query should be the q-th smallest element of the array X. Here, q is a 0-based index. (That is, q=0 means we want the smallest element, q=1 is the second smallest, and so on.)

Right now this task probably seems too easy. After all, you can simply sort the array X and then you'll be able to answer each query in constant time.

Here's the catch: the memory limit in this problem is really small. So small that you cannot even store the array X into memory.

You will be given the ints n, x0, a, and b. You will also be given the int[] query containing the queries.

Use the following pseudocode to generate the array X: 
X[0] = x0
for i = 1 to n-1:
        X[i] = (X[i-1] * a + b) % (10^9+7).
(Watch out for integer overflow.)

Return the sum of answers to all the queries given in query.

Definition

Class:
LimitedMemorySeries1
Method:
getSum
Parameters:
int, int, int, int, int[]
Returns:
long
Method signature:
long getSum(int n, int x0, int a, int b, int[] query)
(be sure your method is public)

Notes

  • Due to some infrastructure limits the memory limit is set to 13 MB. Note that this should correspond to an actual memory limit of only 1 MB. If your solution allocates more than 1 MB of memory, it may exceed the memory limit.

Constraints

  • n will be between 1 and 5,000,000, inclusive.
  • x0, a and b will be between 0 and 1,000,000,006, inclusive.
  • query will contain between 1 and 100 elements, inclusive.
  • Each element in query will be between 0 and (n-1), inclusive.

Examples

  1. 5

    100

    1

    5

    {0,3}

    Returns: 215

    Using the pseudocode in the problem statement you should generate the array X = {100,105,110,115,120}. The answers to the two queries are 100 and 115. Hence, we should return 100 + 115 = 215.

  2. 5

    123456789

    987654321

    1000000006

    {0,1,2,3}

    Returns: 733028692

    X = {123456789, 259106858, 113077375, 244317875, 252176653}

  3. 5000000

    482995837

    512849030

    120583724

    {4854010,3139503,1855546,219904,846357,2624639,891260,217467,4940091,4802760,2424821,424076, 3848272,2062765,2922407,4850301,1279972,4929307,2035456,3562859,1749594,4089499,3797495,1013980, 1650805,1245213,3020379,4661668,427170,1176815,292944,2435328,420809,4170355,2635197,3940607, 4311718,2098572,4868054,30319,4588969,1460677,1335028,3921495,3621970,4459335,966000,3686977, 2316560,1634961,2280624,1940395,3321546,3168811,1856547,3859093,4340475,1382782,3482928,2517843, 185008,1135373,2821050,3260484,4821220,1700954,3243343,2183615,394339,2630121,1811267,1060542, 3898314,892312,2015580,11161,4965095,2128470,2320933,1095881,3938450,1887098,975426,2098073,3300937, 1145560,2894728,1026181,3259403,4509345,3610224,3584456,1877483,2665752,2243671,616205,504849,3068426, 1471925,4144568}

    Returns: 49684994148

  4. 1

    1

    1

    1

    {0}

    Returns: 1

  5. 5000000

    9283721

    5235235

    1546532

    {3462691,855833,553671,1990051,3686326,2801888,2508455,1190388,403166,3876851,3048240,2168407,3257209,1637115,3724211,2282966,4218501,1565262,1168701,3991378,1705255,4952401,2791595,333787,4022053,4690590,4687228,974991,4044838,1487334,3621119,980055,4788745,2657201,307639,931461,3745432,4001272,1224744,4092625,1044467,1546296,1599061,690753,3271718,796750,1975745,2143997,3693472,4455550,1505598,2530738,3653023,1628438,3618730,739623,2768440,2992148,1886172,807216,3640120,3917983,1559407,4403308,3516658,1932176,2321962,2070958,4994318,2398602,3680512,2864136,136905,1155377,1005395,98751,1829019,4307884,3069354,432191,4678862,183820,4002584,4061019,4285998,906618,4483166,194987,3599915,2096107,580347,651205,2485272,3379371,414058,855299,409113,3212565,4189512,280215}

    Returns: 48409676366

  6. 4874985

    1

    1

    1

    {3564739,4778232,2857208,4704362,2079949,4559880,3780355,143007,1147045,1473571,180464,867290,4498984,2400090,2851571,2546042,140391,3511219,4290678,1651559,2434219,4704870,1268257,1282647,2797318,754808,1456283,1890187,1672487,2595358,897109,3798016,3773141,4260022,682713,2950295,3802609,684292,3503660,1310128,104580,604729,446289,1518298,4854965,3128196,2845506,2050034,3089540,721648,4703915,1680792,4054514,1020254,4202128,214848,2217625,1091940,2969841,2910351,627528,907014,120880,1782223,4209765,2129079,2712296,2407461,2736451,773457,4830385,1906722,927202,3145714,1852093,3437555,1801204,735176,2646454,2595118,4204358,4812343,812941,4200302,990586,1776088,2804789,1603800,479713,1146958,3537920,3630324,1967814,4317305,2767692,987069,3269091,4809321,3243455,1820283}

    Returns: 238441077

  7. 4999999

    910293847

    482019302

    102940291

    {4699465,2853836,655444,2985557,3554272,4505394,763069,3582532,3845672,4382722,1120959,4711820,3215150,1665072,3914212,817028,4220742,2283244,4153298,4311860,1574012,419983,4401743,3943741,4930115,1621976,4536830,1030608,492790,4913993,4081474,3468110,2210227,3110343,3720367,4300461,4787881,3336905,2265279,1979439,1400704,4772426,1780077,714862,59604,4612465,3418912,2736879,4213470,4854676,2168181,424476,1564905,4552941,3580016,2041686,3868951,2079723,1558422,325391,1935981,2555619,2992413,4769181,2225651,2231324,1012327,1740166,3603178,4716690,3098682,652345,4886433,3750455,4825626,262115,3256405,2145733,562014,3881515,1466251,2514464,1035468,1832245,836057,4252986,2696980,3167569,4434727,1294119,3972419,213542,2805396,1132143,4410382,2021695,3233561,3027860,3374384,431222}

    Returns: 55470858085

  8. 4999997

    1

    1

    928198392

    {4821596,2204554,447617,3160159,968519,3109985,1323691,2438819,3036927,3058558,2426838,4189008,25031,1499814,3170129,4150124,1406099,4622658,3089063,4120331,2587975,4517095,3086748,4384557,393442,2446134,23318,3696654,1523530,1635521,1871686,1589453,739381,1831617,1315940,2873376,2731017,3807883,419317,2298823,3781815,2487943,1123047,905282,175356,2818351,2864565,3802996,2398704,774807,233661,682924,889829,3809775,545278,1861373,1301050,3123646,505873,4805708,1933181,23181,1490128,651594,974392,3076163,1594723,444677,3314050,3441289,4415284,4321964,4380985,1746985,3207370,137277,4781408,4595139,268314,4638024,4227963,4920982,3615692,29089,3324136,1700263,3324830,4710220,279546,4919127,15304,2648358,4302527,1831363,3315664,4758606,2243797,636487,2268518,1206516}

    Returns: 47930107618

  9. 4999997

    0

    0

    0

    {928975,2337421,625830,2782775,1898605,3610720,2007834,2520480,854049,2947327,1565908,2936121,1673359,3007937,2077809,4369908,1233217,60731,1438429,236364,2798689,636327,4280277,4047893,3757752,3509852,446979,4258707,1293288,1537333,2923050,2368166,3322603,3772727,4187081,4829314,2215225,307260,4261761,2315791,3886278,4819149,4282614,1796015,1592589,3714155,3443160,4308734,2779749,1459464,2716620,1379422,1540849,2711264,4090151,3787369,1187683,4476734,4439765,4784434,2409211,2718029,3698076,576160,2748820,1575818,3613972,1736099,4611152,4797081,2666175,3995732,3785228,1905475,355235,4367701,4080824,3693594,2109486,3623045,757140,3493284,2434951,2263034,2394113,2073975,2467967,4423563,4736391,1413957,192774,4676740,2098281,255412,3365697,4872467,4337834,2122209,155552,227019}

    Returns: 0

  10. 5000000

    1

    1

    200

    {1361955, 2579012, 3145516, 1140462, 3515280, 1969585, 2888635, 1402539, 3152102, 3176572, 1402892, 2860889, 4580638, 870044, 1139319, 3509022, 4027666, 1263304, 1082555, 3212774, 563715, 1389629, 4113528, 1147999, 801172, 2151740, 301173, 1585275, 845005, 2071050, 3573723, 2123762, 4467290, 1231662, 1265400, 4374333, 690249, 3571510, 1747709, 4313372, 3215695, 4204466, 4608448, 2733264, 1517316, 253431, 1956091, 1457954, 3156706, 1354013, 3398859, 2040410, 3974602, 3000642, 2883250, 4556873, 2264704, 461189, 2444309, 2035008, 986538, 206284, 2553407, 142614, 2099860, 1205950, 144412, 2641318, 4344367, 64713, 1507263, 4420687, 4726669, 434270, 3692316, 461042, 1329638, 2850352, 4523791, 4794871, 497239, 203769, 1091347, 4237001, 3054686, 2246324, 2178252, 625749, 1162463, 4505508, 1356542, 1738703, 692962, 1102988, 3986003, 2173997, 2688147, 3502197, 3916697, 2545898 }

    Returns: 45752824300

  11. 5000000

    482995837

    512849030

    120583724

    {4854010, 3139503, 1855546, 219904, 846357, 2624639, 891260, 217467, 4940091, 4802760, 2424821, 424076, 3848272, 2062765, 2922407, 4850301, 1279972, 4929307, 2035456, 3562859, 1749594, 4089499, 3797495, 1013980, 1650805, 1245213, 3020379, 4661668, 427170, 1176815, 292944, 2435328, 420809, 4170355, 2635197, 3940607, 4311718, 2098572, 4868054, 30319, 4588969, 1460677, 1335028, 3921495, 3621970, 4459335, 966000, 3686977, 2316560, 1634961, 2280624, 1940395, 3321546, 3168811, 1856547, 3859093, 4340475, 1382782, 3482928, 2517843, 185008, 1135373, 2821050, 3260484, 4821220, 1700954, 3243343, 2183615, 394339, 2630121, 1811267, 1060542, 3898314, 892312, 2015580, 11161, 4965095, 2128470, 2320933, 1095881, 3938450, 1887098, 975426, 2098073, 3300937, 1145560, 2894728, 1026181, 3259403, 4509345, 3610224, 3584456, 1877483, 2665752, 2243671, 616205, 504849, 3068426, 1471925, 4144568 }

    Returns: 49684994148

  12. 5000000

    42

    24

    531

    {4299593, 3386301, 3032025, 3797765, 2676423, 707517, 2860830, 3597306, 1101714, 728184, 3918200, 207691, 4815262, 1068493, 4259218, 1267134, 3357408, 730195, 4379678, 2822501, 169204, 4791690, 468004, 2643694, 4415942, 874394, 4931787, 890763, 836306, 1699147, 1253141, 290295, 3973059, 4478205, 4586792, 4934680, 756675, 317526, 3989652, 1304212, 2654491, 4529758, 100014, 2742899, 1074465, 2829282, 4163376, 850014, 3789123, 464809, 2132574, 1178514, 3684094, 1858677, 591108, 1438554, 1757349, 28634, 1720085, 1009940, 3698317, 1360850, 3841515, 538041, 2255086, 1209474, 2064547, 4748102, 114231, 4330846, 4524785, 109372, 148600, 2935670, 4644385, 3583430, 2273069, 4771503, 2378754, 2126306, 356477, 2330880, 3615861, 1196756, 1748218, 3708343, 1846614, 275614, 3287892, 4633824, 3419481, 1715619, 3236345, 3179789, 4311082, 4100399, 3515567, 4475957, 1027677, 3434364 }

    Returns: 49267020997

  13. 5000000

    17

    352941179

    0

    {1361955, 2579012, 3145516, 1140462, 3515280, 1969585, 2888635, 1402539, 3152102, 3176572, 1402892, 2860889, 4580638, 870044, 1139319, 3509022, 4027666, 1263304, 1082555, 3212774, 563715, 1389629, 4113528, 1147999, 801172, 2151740, 301173, 1585275, 845005, 2071050, 3573723, 2123762, 4467290, 1231662, 1265400, 4374333, 690249, 3571510, 1747709, 4313372, 3215695, 4204466, 4608448, 2733264, 1517316, 253431, 1956091, 1457954, 3156706, 1354013, 3398859, 2040410, 3974602, 3000642, 2883250, 4556873, 2264704, 461189, 2444309, 2035008, 986538, 206284, 2553407, 142614, 2099860, 1205950, 144412, 2641318, 4344367, 64713, 1507263, 4420687, 4726669, 434270, 3692316, 461042, 1329638, 2850352, 4523791, 4794871, 497239, 203769, 1091347, 4237001, 3054686, 2246324, 2178252, 625749, 1162463, 4505508, 1356542, 1738703, 692962, 1102988, 3986003, 2173997, 2688147, 3502197, 3916697, 2545898 }

    Returns: 45757356213

  14. 5000000

    1

    2

    0

    {4854010, 3139503, 1855546, 219904, 846357, 2624639, 891260, 217467, 4940091, 4802760, 2424821, 424076, 3848272, 2062765, 2922407, 4850301, 1279972, 4929307, 2035456, 3562859, 1749594, 4089499, 3797495, 1013980, 1650805, 1245213, 3020379, 4661668, 427170, 1176815, 292944, 2435328, 420809, 4170355, 2635197, 3940607, 4311718, 2098572, 4868054, 30319, 4588969, 1460677, 1335028, 3921495, 3621970, 4459335, 966000, 3686977, 2316560, 1634961, 2280624, 1940395, 3321546, 3168811, 1856547, 3859093, 4340475, 1382782, 3482928, 2517843, 185008, 1135373, 2821050, 3260484, 4821220, 1700954, 3243343, 2183615, 394339, 2630121, 1811267, 1060542, 3898314, 892312, 2015580, 11161, 4965095, 2128470, 2320933, 1095881, 3938450, 1887098, 975426, 2098073, 3300937, 1145560, 2894728, 1026181, 3259403, 4509345, 3610224, 3584456, 1877483, 2665752, 2243671, 616205, 504849, 3068426, 1471925, 4144568 }

    Returns: 49627881573

  15. 500000

    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, 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, 0, 0, 0 }

    Returns: 0

  16. 5000000

    0

    0

    199

    {14383, 30886, 67777, 86915, 122793, 138335, 160386, 185492, 216649, 241421, 252362, 290027, 318690, 345059, 372763, 388926, 405540, 433426, 464172, 480736, 505211, 545368, 552567, 581429, 615782, 646530, 672862, 690123, 724067, 728135, 763929, 779802, 809022, 848058, 858069, 898167, 911393, 943456, 950011, 978042, 1001229, 1027373, 1059421, 1094919, 1113784, 1148537, 1150198, 1194324, 1223315, 1239370, 1266413, 1278526, 1301091, 1343980, 1359956, 1391873, 1406862, 1449170, 1456996, 1497281, 1502305, 1545925, 1552084, 1586327, 1610336, 1626505, 1650846, 1696729, 1711313, 1725857, 1766124, 1778895, 1819582, 1825545, 1873814, 1883367, 1915434, 1940364, 1969043, 1988750, 2021087, 2026808, 2067276, 2097178, 2120788, 2143584, 2155403, 2177651, 2217754, 2237399, 2274932, 2295060, 2324676, 2343368, 2372739, 2385012, 2411226, 2448586, 2473094, 2497539 }

    Returns: 19900

  17. 5000000

    5

    0

    1

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

    Returns: 7

  18. 5000000

    483995837

    512849031

    720583724

    {4854010, 3139503, 1855566, 219904, 846355, 2624639, 891260, 217467, 4940091, 4802760, 2424821, 424076, 3848272, 2062765, 2922407, 4850301, 1279972, 4929307, 2035456, 3562859, 1749594, 4089499, 3797495, 1013980, 1650805, 1245213, 3020379, 4661668, 427170, 1176815, 292944, 2435328, 420809, 4170355, 2635197, 3940607, 4311718, 2098572, 4868054, 30319, 4588969, 1460677, 1335028, 3921495, 3621970, 4459335, 966000, 3686977, 2316560, 1634961, 2280624, 1940395, 3321546, 3168811, 1856547, 3859093, 4340475, 1382782, 3482928, 2517843, 185008, 1135373, 2821050, 3260484, 4821220, 1700954, 3243343, 2183615, 394339, 2630121, 1811267, 1060542, 3898314, 892312, 2015580, 11161, 4965095, 2128470, 2320933, 1095881, 3938450, 1887098, 975426, 2098073, 3300937, 1145560, 2894728, 1026181, 3259403, 4509345, 3610224, 3584456, 1877483, 2665752, 2243671, 616205, 504849, 3068426, 1471925, 4144568 }

    Returns: 49644991099

  19. 5000000

    0

    0

    0

    {4854010, 3139503, 1855546, 219904, 846357, 2624639, 891260, 217467, 4940091, 4802760, 2424821, 424076, 3848272, 2062765, 2922407, 4850301, 1279972, 4929307, 2035456, 3562859, 1749594, 4089499, 3797495, 1013980, 1650805, 1245213, 3020379, 4661668, 427170, 1176815, 292944, 2435328, 420809, 4170355, 2635197, 3940607, 4311718, 2098572, 4868054, 30319, 4588969, 1460677, 1335028, 3921495, 3621970, 4459335, 966000, 3686977, 2316560, 1634961, 2280624, 1940395, 3321546, 3168811, 1856547, 3859093, 4340475, 1382782, 3482928, 2517843, 185008, 1135373, 2821050, 3260484, 4821220, 1700954, 3243343, 2183615, 394339, 2630121, 1811267, 1060542, 3898314, 892312, 2015580, 11161, 4965095, 2128470, 2320933, 1095881, 3938450, 1887098, 975426, 2098073, 3300937, 1145560, 2894728, 1026181, 3259403, 4509345, 3610224, 3584456, 1877483, 2665752, 2243671, 616205, 504849, 3068426, 1471925, 4144568 }

    Returns: 0

  20. 5

    2

    1

    0

    {0, 1, 2, 3, 4 }

    Returns: 10

  21. 5000000

    0

    1

    0

    {4854010, 3139503, 1855546, 219904, 846357, 2624639, 891260, 217467, 4940091, 4802760, 2424821, 424076, 3848272, 2062765, 2922407, 4850301, 1279972, 4929307, 2035456, 3562859, 1749594, 4089499, 3797495, 1013980, 1650805, 1245213, 3020379, 4661668, 427170, 1176815, 292944, 2435328, 420809, 4170355, 2635197, 3940607, 4311718, 2098572, 4868054, 30319, 4588969, 1460677, 1335028, 3921495, 3621970, 4459335, 966000, 3686977, 2316560, 1634961, 2280624, 1940395, 3321546, 3168811, 1856547, 3859093, 4340475, 1382782, 3482928, 2517843, 185008, 1135373, 2821050, 3260484, 4821220, 1700954, 3243343, 2183615, 394339, 2630121, 1811267, 1060542, 3898314, 892312, 2015580, 11161, 4965095, 2128470, 2320933, 1095881, 3938450, 1887098, 975426, 2098073, 3300937, 1145560, 2894728, 1026181, 3259403, 4509345, 3610224, 3584456, 1877483, 2665752, 2243671, 616205, 504849, 3068426, 1471925, 4144568 }

    Returns: 0

  22. 5000000

    3124

    14124

    12444542

    {0, 0, 3976080, 3329348, 2199095, 1373430, 3019720, 2900985, 4593726, 495757, 281010, 1677082, 2023908, 418829, 1583040, 1339407, 1252351, 3342090, 2780664, 4151532, 4012632, 402433, 569023, 4911772, 2024590, 2309173, 2156886, 934629, 4729683, 548041, 973756, 4403606, 4112926, 1479398, 2133379, 406462, 3998112, 4715461, 4425999, 3867277, 3196011, 4920801, 4411843, 833078, 4357191, 3645540, 2761956, 4060876, 2001962, 2013344, 2577420, 1985692, 3825367, 3393566, 622763, 1380995, 3632564, 2198387, 4960359, 1751462, 1063370, 3010044, 996630, 1838148, 2266980, 1344459, 3295216, 3476964, 3059501, 488192, 1687139, 2730700, 4030032, 3680858, 1482472, 1002989, 4818224, 1647113, 2432191, 299453, 614423, 906845, 1835570, 3487574, 3567491, 4305369, 4098823, 175472, 1397095, 18308, 4231589, 2900799, 3051026, 2307275, 4828766, 3026595, 1328232, 1077445, 161039, 3086186 }

    Returns: 48698252567

  23. 5000000

    381

    492983

    8478294

    {2900000, 2900001, 2900002, 2900003, 2900004, 2900005, 2900006, 2900007, 2900008, 2900009, 2900010, 2900011, 2900012, 2900013, 2900014, 2900015, 2900016, 2900017, 2900018, 2900019, 2900020, 2900021, 2900022, 2900023, 2900024, 2900025, 2900026, 2900027, 2900028, 2900029, 2900030, 2900031, 2900032, 2900033, 2900034, 2900035, 2900036, 2900037, 2900038, 2900039, 2900040, 2900041, 2900042, 2900043, 2900044, 2900045, 2900046, 2900047, 2900048, 2900049, 2900050, 2900051, 2900052, 2900053, 2900054, 2900055, 2900056, 2900057, 2900058, 2900059, 2900060, 2900061, 2900062, 2900063, 2900064, 2900065, 2900066, 2900067, 2900068, 2900069, 2900070, 2900071, 2900072, 2900073, 2900074, 2900075, 2900076, 2900077, 2900078, 2900079, 2900080, 2900081, 2900082, 2900083, 2900084, 2900085, 2900086, 2900087, 2900088, 2900089, 2900090, 2900091, 2900092, 2900093, 2900094, 2900095, 2900096, 2900097, 2900098, 2900099 }

    Returns: 58025195192

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: