Statistics

Problem Statement for "MulticoreProcessingEasy"

Problem Statement

In the last several years CPU manufacturers have been making processors with an ever-increasing number of processing cores. Utilizing multiple cores to process workloads sometimes creates challenges for developers. When a processing workload gets split into multiple parts, there is often some performance penalty caused by having to split the work and recombine the results. For example, a job that takes 1000 ms on a single core might be expected to run in 500 ms across two cores, but in reality ends up taking 650 ms.

Your team has a workload that needs to be processed. The workload requires jobLength units of computation. If we use multiple cores to process the job, the computation will be split equally among all cores. For example, if you split 1000 units of computation among 3 cores, each core will get exactly 1000/3 units of computation to perform.

You have several available systems that can be used for the computation. Each system has some number of cores. All cores in a system have the same speed of computation. You need to choose a single system that will be used to process the workload, and you need to choose how many cores of that system will be used for the computation.

The description of the systems you have is given in the int[]s speed and cores. For each valid i you own a system with cores[i] cores such that each of the cores can execute speed[i] units of computation per millisecond.

Due to the overhead with parallelization, the computation will take additional corePenalty milliseconds for each core used beyond the first. This constant is the same for all systems you have.

You are given the int jobLength, the int corePenalty, and the int[]s speed and cores. Find the best system you should use and the best number of cores you should use on that system. Return the smallest positive integer T such that it is possible to execute the entire computation in T milliseconds or less.

Definition

Class:
MulticoreProcessingEasy
Method:
fastestTime
Parameters:
int, int, int[], int[]
Returns:
int
Method signature:
int fastestTime(int jobLength, int corePenalty, int[] speed, int[] cores)
(be sure your method is public)

Constraints

  • jobLength will be between 1 and 1000000000, inclusive.
  • corePenalty will be between 0 and 1000000, inclusive.
  • speed will have between 1 and 50 elements, inclusive.
  • cores will have the same number of elements as speed.
  • Each element of speed will be between 1 and 1000000, inclusive.
  • Each element of cores will be between 1 and 1000, inclusive.

Examples

  1. 2000

    5

    {40,20}

    {2,4}

    Returns: 30

    The first system is twice as fast as the second one, but the first system only has two cores while the second one has four. Their raw processing power is the same, but using more cores incurs the core penalty multiple times. Thus, in this particular case it is better to use the first system. If we use both cores, each of them has to do 1000 steps of computation, and with speed 40 this will take exactly 25 milliseconds. We then add the 5-millisecond core penalty to compute that the total running time for this option is exactly 30 milliseconds.

  2. 2000

    5

    {10,20}

    {2,4}

    Returns: 40

    Now, the faster machine is also the one with more cores. Even with the core penalty it's far faster overall.

  3. 1000

    0

    {10}

    {3}

    Returns: 34

    We need to perform 1000 units of computation. On a system with 3 cores, each with speed 10, we will need 1000/(3*10) = 33.3333333... milliseconds of time. The correct return value is this exact value rounded up to the nearest integer: 34 milliseconds is the smallest integer amount of milliseconds sufficient for the computation.

  4. 10000

    5

    {39,37,44}

    {8,16,6}

    Returns: 63

    These are roughly the specs of some current-day CPUs.

  5. 1000000000

    123

    {40,30,25}

    {10,12,4}

    Returns: 2501107

  6. 480534008

    74888

    {232464,981662,181446,741278,701356,189679,711892,276396}

    {430,693,363,518,143,452,324,762}

    Returns: 490

  7. 227712273

    580756

    {67846,292357}

    {349,638}

    Returns: 779

  8. 74052785

    32147

    {717975,89603,404970,685354,247403,554201,557766,50248,217572,4876,682574,761651}

    {777,1000,478,460,751,971,296,937,239,875,923,886}

    Returns: 98

  9. 837525779

    487178

    {7043,940108,907609,958058,965117,701816,712633,252311,526244,256796,744507,412411,398595,157624,795744,204335,917793,678311,307295,646592,599708,85131,515757}

    {807,793,661,645,428,738,767,77,208,23,18,75,70,541,15,163,37,653,959,311,652,509,501}

    Returns: 868

  10. 292242385

    108084

    {845803,677663,464188,989445,865324,838432,417243,950608,539801,676205,599371,568105,945964,93220,903657,897971,49540,949941,526672,453605,688867,441971}

    {236,581,697,395,394,503,849,224,821,89,770,562,424,933,560,777,111,780,582,341,259,565}

    Returns: 296

  11. 808160576

    808372

    {802907,285533,680595,19955,76669,116650,40906,56977,306297,61496}

    {135,976,617,831,668,635,603,491,496,453}

    Returns: 1007

  12. 306690942

    898439

    {696550,366425,399264,327164,752854,240817,797946,583072,160898}

    {959,336,341,4,138,291,619,218,30}

    Returns: 385

  13. 279659972

    873273

    {410023,412700,631891,135674,746665,875775}

    {947,738,769,70,356,905}

    Returns: 320

  14. 963017962

    588983

    {314171}

    {281}

    Returns: 3066

  15. 620690933

    490229

    {663918,497175,312579,872451,278074,423337,25167,286527,953726,767374,191490,6189,365043,834928,565631,880749,789431,447883,449345,424846,895684,791200,932114,879302,302457,360445,853318,558015,357608,435046,424105,157595,19850,237600,611823,562653,173618,676846}

    {364,801,260,724,901,28,60,12,599,573,935,783,386,30,904,409,124,47,613,373,413,847,849,904,6,682,918,730,716,927,844,375,15,902,241,342,395,780}

    Returns: 651

  16. 142912690

    160121

    {516300,931614,560187,199063,871732,718077,734312,498112,52375,416332,917671,977902,62157,19330,458804,778974,197486,918747,492491,597408,820787,365869,893747,828341,675506,624472,726582,932358,528642,664529,523431,96773,786779,491134,258818,456265,657446,5431,245275,397745,614450,832563,616383}

    {507,727,543,556,566,689,178,949,255,827,612,292,443,509,241,587,866,421,117,833,459,336,552,164,446,525,334,906,641,118,691,631,132,870,78,936,585,459,643,511,856,14,255}

    Returns: 147

  17. 860311831

    863582

    {13591,852367,480012,129792,734992,762564,959033,597584,688722,142358,473554,886387,154054,667651,83728,531994,627552,245228,603899,177434,875639,510284,635182,655418,234979,927661,717954,459093,5162,298042,641027,278367,16875,432996,659506,385596,689309,452835,149598,607198,847529,623455,86835,552918,477570,181212,185614}

    {892,453,309,363,549,61,905,990,867,329,660,243,503,859,15,271,937,187,484,276,97,94,450,952,24,389,536,354,610,978,272,721,492,23,412,206,867,377,793,705,717,61,144,93,892,994,201}

    Returns: 898

  18. 634519382

    604280

    {789788,143490,633048,823768,722595,851143,82250,212163,593916,924424,218191,872925,340552,767988,391686,488941,848556,359811,463709,214482,799687,364241,701776,395321,969050,591698,710096,600154,203589,676381,523555,246270,209794,233718,844302,539083,915056,848220,269421,237000,149480}

    {77,17,292,638,699,83,205,3,130,648,634,939,545,230,20,233,559,717,688,426,423,446,11,688,992,71,957,157,205,89,594,704,619,524,496,907,500,796,428,331,81}

    Returns: 655

  19. 260949646

    400566

    {418111,892181,203684,258994,126235,205918,661100,82926,871571,473374,684977,210733,804184,775881,346000,442973,845704,791684,341538,640619,280090,788822}

    {523,959,513,11,902,176,236,777,844,453,156,109,887,968,939,333,276,97,566,983,896,598}

    Returns: 293

  20. 642301615

    620018

    {192286,553928,237479,948530,262335,784026,316977,291278,187468,873099,385714,986273,306167,490596,789070,612875,184166,583596,792072,205495,897175,529349,557512,323643,988812,601354,769204,222607,167801,971743,296981}

    {155,278,788,743,312,155,738,665,459,331,444,435,203,172,367,466,279,814,661,546,533,786,412,246,232,140,290,749,120,35,777}

    Returns: 650

  21. 953708765

    895381

    {318172,38590,477636,526609,327855,853107,201085,894926,244836,557977,473551,894396,835051,673060,170502,120593,633968,239341,285053,511176,74745,441349,369501,966716,76818,52145,395732,225040,75601,318372,199683,82537,312481,280424,638064}

    {970,154,873,254,434,915,878,879,184,766,697,56,646,690,249,579,87,442,93,359,887,857,835,242,157,594,130,622,983,832,838,80,275,115,454}

    Returns: 987

  22. 593789741

    152496

    {199627,587265,37699,896,431452,14352,527148,504188,617819,302243,679382,237252,361757,95294,852230,623138,899648,196106,637775,37903,317476,768231,68186,785333,776237,20245,291547,992580,453604,893546,590986,826896,989162,296471,987062,223785,327743,456493,390438,735564,758884,777495,583300,270814,928906,985322,472675,705546,325774,236033}

    {691,256,687,680,613,197,184,862,366,774,159,804,545,554,604,563,922,439,367,297,153,226,884,92,253,89,379,41,784,494,448,828,452,606,66,252,6,527,13,479,5,600,536,522,156,855,545,871,941,617}

    Returns: 599

  23. 587002222

    179670

    {710974,768646,285835,465868,441546,415262,586733,227593,454060,775352,831916,369526,783323,586182,450115,119369,579214,66521,814654,984980,463038,543776,57413,118813,98182,781974,811651,272064,659618,976972,335855,200408,928585,155386,603150,429955,196198,213720,536165,721513,181355,102757,994052,79632,628211,910544,797838,263228,304218,877724}

    {30,761,923,651,48,735,670,245,182,677,80,779,301,201,777,892,901,571,775,600,505,807,810,201,696,436,503,632,990,986,265,666,524,687,658,680,177,328,564,974,386,755,685,77,436,825,1000,199,879,534}

    Returns: 591

  24. 654435637

    432355

    {440750,102723,635381,944774,96400,3470,950313,446009,244235,79084,167663,605022,196886,15612,657911,188080,749000,662008,891330,444251,683438,814144,794368,312915,858209,633489,575352,429828,660738,41936,273581,436960,80129,55314,500166,780142,99,374810,932744,87047,600128,164865,52006,743714,358224,827902,403593,513529,903659,476597}

    {266,239,290,95,269,805,163,672,445,59,747,882,914,24,686,320,789,489,446,788,341,557,195,36,207,90,375,694,222,723,922,411,685,163,958,799,292,828,49,2,980,452,99,375,969,671,722,762,404,110}

    Returns: 689

  25. 139684344

    150653

    {900841,834783,283378,602784,612441,40049,293907,985834,981132,680423,532021,110121,278188,613073,529506,977084,449475,264025,217224,460337,755440,215461,363545,219623,917826,495465,459263,3752,316524,810797,386226,231613,157179,672737,492812,141676,480354,48599,914007,31570,558824,5561,76237,402941,440152,707960,199216,989369,975415,378582}

    {427,89,1000,762,135,123,757,359,941,805,130,396,779,924,572,863,444,25,11,376,208,536,600,5,45,170,347,772,440,505,680,41,178,851,962,972,305,325,575,679,609,486,808,103,493,778,956,77,175,186}

    Returns: 142

  26. 1000000000

    123456

    {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,31,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,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,31,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}

    Returns: 3019934

  27. 1000000000

    0

    {1}

    {1}

    Returns: 1000000000

  28. 1000

    100

    {1000 }

    {3 }

    Returns: 1

  29. 70

    50

    {7 }

    {2 }

    Returns: 10

  30. 1000

    500000

    {20, 40, 50 }

    {20, 40, 50 }

    Returns: 20

  31. 1000

    0

    {10 }

    {3 }

    Returns: 34

  32. 1000

    1201

    {120, 130 }

    {120, 130 }

    Returns: 8

  33. 1

    100

    {1000000 }

    {1000 }

    Returns: 1

  34. 10

    10

    {1 }

    {2 }

    Returns: 10

  35. 1

    1000000

    {1 }

    {1000 }

    Returns: 1

  36. 1000

    0

    {1 }

    {3 }

    Returns: 334

  37. 10

    1000

    {1, 1, 1 }

    {10, 10, 10 }

    Returns: 10

  38. 1000

    100000

    {40 }

    {2 }

    Returns: 25

  39. 2000

    5

    {2000, 20 }

    {2, 4 }

    Returns: 1

  40. 1000

    50000

    {20, 40, 50 }

    {20, 40, 50 }

    Returns: 20

  41. 2000

    500

    {20 }

    {4 }

    Returns: 100

  42. 10000

    500000

    {20, 40, 50 }

    {20, 40, 50 }

    Returns: 200

  43. 200

    100

    {40 }

    {2 }

    Returns: 5

  44. 10

    100

    {1 }

    {2 }

    Returns: 10

  45. 100

    1000000

    {10 }

    {2 }

    Returns: 10

  46. 1

    5

    {10 }

    {10 }

    Returns: 1

  47. 100

    1000

    {1 }

    {2 }

    Returns: 100

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: