Statistics

Problem Statement for "MulticoreProcessing"

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 long 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:
MulticoreProcessing
Method:
fastestTime
Parameters:
long, int, int[], int[]
Returns:
long
Method signature:
long fastestTime(long jobLength, int corePenalty, int[] speed, int[] cores)
(be sure your method is public)

Constraints

  • jobLength will be between 1 and 10^18, inclusive.
  • corePenalty will be between 0 and 1000000000, 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 1000000000, inclusive.
  • Each element of cores will be between 1 and 1000000000, 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. 1000000000000000000

    123

    {40,30,25}

    {10,12,4}

    Returns: 2500000000001107

  6. 121353559944773712

    316486377

    {383181876,390265928,575079954,151419060,169094273,639144431,956012623,963017854,56290172,666937269,34643595,260339901,295003482,34258130,767915770,740671828,335276894,419502965,467136642,787452259,789583492,530390920,1006748,485240395,439505459,906509534,277836443,589950090,424119049,799580591,436517167,11140347}

    {684458949,94584073,470775297,779056117,584560404,182114164,576442537,292565797,270091786,105270101,684802385,624363662,833131873,840743937,381987755,837888703,368264169,771020576,381455107,334824866,855449132,976306886,948093808,11478876,969120804,851261775,211216278,698379491,765902267,741948081,310675123,787106518}

    Returns: 126013822

  7. 843888576801255729

    846837270

    {156939573,825429155,482639528,315686609,154411466,623356914,347891479,401238479,475478221,560052260,778314080,346901528,581874516,898307700,844308785,132418309,101256538,854539304,143691650,368622247,895529669,543968026,142545353,394056603,909436645,311628298,241203469,809434375,845095752,92960550}

    {191997279,674835066,332112403,179194464,284033016,346909675,22779254,798794967,889410054,124060617,721123474,701234375,45504179,478908369,743284402,199751020,897491942,247508180,231674469,945724040,410755627,140086033,452670917,413737913,212345381,954478523,722776654,435816099,124194780,437135349}

    Returns: 927924536

  8. 433804703836778241

    334885678

    {151614708,245653137,168239951,655103317,520787807,228530949,177155448,558689023,651447577,569471725,431656105,958547551,88057567,402412429,138713920,511919337,75869948,988471326,207017781,245497963,557242065}

    {423605895,450399537,153730300,243803752,614328220,367558454,206815496,129203600,484569787,631963404,177939787,378479885,418723205,19496870,931486899,58751429,132840963,718939458,943657066,755706345,67824546}

    Returns: 438864227

  9. 433690715626875249

    494245705

    {258660651,565505758,785687773,267306516,979470959,465058345,362341970,751317872,105089833,102408884,291688506,218344171,922185819,239071824,74721340,744249072,884234179,160062554,453991113,145799126,791444913,153370005,253881114}

    {638280257,963756951,949234918,702922275,973674921,867173253,749516746,635606448,589300909,169779521,44314486,839749565,707790512,813765380,363831560,331672303,646181647,764132173,174956969,562684419,372947674,14796405,339844529}

    Returns: 442780577

  10. 581315095495981218

    4388473

    {962734713,524466365,150187416,419936086,41571132,710163094,628200936,229425850,982939074,589454192,181615335,443501784,378334608,890944481,585868451,126475416,809376907,401096847,807205938,495994231,344196087,133385837,852521326,744746738,785370556,356905455,906527026,740020283,400888024,946131578,323401686,139887743,951421846,644164230,214542553,326180105,220166093,642989613,796747028,687203140,173994095,418177210,225435836,836563582,413065441,498971242,613636416}

    {844389807,324466186,214346166,725756193,77897262,453541136,615639400,133386043,716160324,987185699,930132865,539724465,918740833,203547766,582341291,743090607,153085723,899859265,559767994,945716389,728234920,67901865,337903777,537730606,120495072,865154772,17202775,32601849,984741901,231446583,216388321,459229842,967072487,475115213,329566585,423171080,643737804,453380415,375599920,40430831,353213876,465373379,261320645,792174132,368494998,822464038,264547649}

    Returns: 97556955

  11. 622314703127807767

    588347177

    {116480019,693739548,323188053,794314967,644988679,374213163,235854822,297538761,57452488,798211111,233794007,130508906,62049773,830595343,809534665,21423101,865033238,259119901,346691284,30025824,671058413,616331966,417960970,132640177,524925277,207095161,329596657,440361989,754939933,207581754,625208630,124199711,241366122,421606630}

    {885448839,269631526,455803972,933734376,262789223,286639868,25288105,905700747,970187810,674514364,690101202,851990098,846047555,503716068,955618445,515181847,122591033,801754301,904362570,962373239,291701461,573774359,126425573,473683138,707935669,652126894,913832814,426378818,841749451,477140499,290598900,689370235,859031316,113263790}

    Returns: 719411320

  12. 766168203495784460

    559009464

    {940161987,3455952,73769237,434029128,713407379,978790792,748523284,185585191}

    {835837872,942092546,556734547,935624200,356912205,101598996,369296207,951200424}

    Returns: 782770139

  13. 682229043832741084

    46814368

    {696780816,337164610,167501750,332408238,704818943,707514935,148926206,711964908,910376863,352609582,407720324,763733121,311808109,940846951,673446126,431034746,448970092,456309104,498673263,774590797,224326310,230805257,649397271,952672791,657331300,40823562}

    {552885325,380459513,926961732,558929655,19376388,29140817,54005242,493758785,498269444,198205386,271957555,268296425,22600716,872069915,470406207,933427121,54067632,387276662,622996439,146807505,875099474,694030991,949649975,694518042,691826406,183959601}

    Returns: 319473368

  14. 480131502848608983

    97221509

    {789152205,68651405,986114781,885483529,588341642,580170725,597696139,995085523,723678647,973879077,41152298,618899154,69927926,214738616,429582645,453295618,956846123,598124457,554345034,160692725,989615945,105689350}

    {68868185,144901035,460338323,234412737,774087815,94858574,324688247,287380424,205802077,532620851,69702130,362158134,246328910,981619720,247075146,600361110,31485842,429805078,629689763,763987987,996392520,875309457}

    Returns: 338472885

  15. 369479249857814217

    96821902

    {696740884,460280954,874729906,383670964,449969032,74973109,245599708,804830092,320792197,138012452,726563790,733035391,45109352,543004906,964012781,992678884,149507007}

    {753443138,274329427,564600659,719450076,706493272,739785872,903863809,341266496,979809616,566210298,565280445,93988885,209891090,44759778,743589698,212113709,882095563}

    Returns: 282924002

  16. 284878836676139508

    786794193

    {725631204,647814878,979836047,554716654,518388280,191562428,554517261,719801765,606079264}

    {392245464,878674381,847851763,420906854,85752137,764422854,389669635,530611606,131460440}

    Returns: 290741332

  17. 20407747366292069

    229220074

    {21595754,755437296,713814388,590278866,618984973,554472304,254178412,918395420,585444399,539272232,691502811,853197351,189072438,492311945,276016299,655731761,949746117,370649711,123237086,134037375,830627989,466767164,209950551,135491224,612216187,546016041,827019838,973336006,485713837,517306897,370547456,87487847,472958824,192079889}

    {338911187,706379334,862859400,363504145,128690585,141826006,745766989,847889409,885183628,624202499,457252770,199589927,603009249,618895401,153418398,420502125,60792388,308903692,273456713,691857254,154884135,62871844,412691255,974034777,758189855,135224120,605017577,564342984,555847369,110805139,971383465,465566576,133970180,193386024}

    Returns: 20966807

  18. 375117278609491729

    724652324

    {751146254,793574511,990485606,989639377,467518026,6679215,607402357,593482287,87456383,823189856,756149816,321309798,67396289,589913021,220611367,598917499}

    {847414978,536618676,790325507,776381183,518277168,517826445,520507642,344728541,806306727,567389718,23232236,859244524,1200589,75980371,942105200,2724458}

    Returns: 378720576

  19. 33537531234028355

    384077866

    {811443066,573857379,566207992,643287114,964704250,858164219,540487893,105929642,786301873,555837871,526105181,469222388,200412487,555769817,919359670,484288913,136429776,533285475,232449349,1181726,379945123,894540274,143036370,535492479,836175559,216422586,678190485,453499680,967494943,494975844,185155898,932910619,85372489,816021407,314065874,336361204,156080881,347968896,39789714,846248648,378166528,689237268,787532172,695183519,160377749,683244111,632825683,830068204,536128891}

    {436717330,695388330,740925715,852270289,569661402,952451183,847351349,568810553,157262607,727914018,934329988,989285018,913659006,525412827,3954757,373374003,613877428,650739053,127801526,15224102,469039510,497734887,637461839,373260018,30106946,876274926,656163849,877113079,584572361,652548986,117874288,960749494,484790217,926610465,455190589,658500347,540613769,57065671,971487502,562950649,182509799,889252724,608013988,480265927,656172396,647876988,348632740,262070836,933790781}

    Returns: 34664297

  20. 412362397658246154

    821440432

    {59194144,693745742,720194045,308194954,837323366,738323714,274382459,428637020,173217323,789606699,766232717,771946479,25674664,710545566,520936781,559125104,741510217,123315655,195506982,887819944,172070973,818849031,909553275,74250281,833433816,760573458,868639456,842649298,609038493,532247575,427031150}

    {380984971,557922239,137576716,396434009,996007442,932025196,2646100,43657896,477358502,335755481,657893478,688484217,807448142,85898060,105998934,188002495,769284514,308252298,229609933,557606804,763943741,687236670,700800488,827422105,492470996,935003897,485684951,401300667,5261526,912745904,222296894}

    Returns: 453368054

  21. 875497227731324432

    436882337

    {190514979,879330445,848150914,589538558,163684508,839044447,778930942,733197861,252464245,345425476,319363040,926635216,699213806,697362358,130575654,888446513,250354333,510285510,948091660,644320082,345465339,322000443,562256220,226330584,179548043,969832650,385898957,230958180}

    {505097946,120384723,943607390,231999896,2288977,84709809,324874177,883123462,28465786,624121208,255825267,722014989,190245457,975074041,949774080,87524599,359232056,569152336,713049094,816966068,636639560,840360322,524328684,207373399,543907689,847031443,812761130,934689712}

    Returns: 888247440

  22. 578462729157315456

    421170917

    {246245033,101424242,113842465,834355477,814588667,935031802,384145704,278655870,933824824,159758770,963914873,795525998,979941430,701625643,128273876,990689606,291878177,570721036,535215318,726517858,689973207,392784732,608875888,462885740,534105261,864889,997556687,693990585,818938521,233969000,49894206,291425011,173355920,247536974,957738373,147508162,359757037,484911916,97204228,977792078,578529330,903487942,574730910,793219518,292424040,912062301,874121015,760842166,515206687,842146599}

    {614464518,213910429,751519849,419698887,164045525,539415151,528459408,682723480,86274894,174885123,489988960,586667965,41415070,437593203,575595798,790776204,986414625,731000821,108090014,810736372,806631698,15502519,430417499,857439549,548234701,492187836,246285795,756256074,514756278,72427395,396762275,238992870,144255598,397731079,547655049,825734810,349022399,157283176,780023480,549523931,844186095,580039176,498501770,45592383,814464963,20459041,654090463,293210933,153791863,464620290}

    Returns: 579879557

  23. 182880525065154661

    899701177

    {400726540,132430800,761373879,659051846,536964201,493898066,493274333,664261960,351036081,105307040,635592748,951613796,588180233,642076489,937876881,366643406,944484918,179312637,366070971,284218504,155413117,483494841,160192398,799936600,489529904,113584210,959847622,350857466,223516283,60354056,894630922,101038161,317801663,261223194,532073199,308783180,917726088,987860293,643554281,545474177,391764384,453882462,399587579,553527049,566180264,176084549,84331174,861085710,772109100,871874284}

    {175130079,648534289,536707410,38915041,684445069,205708112,711385835,674854150,201944592,143273410,127049121,705666575,191700984,943412365,513171788,513374670,917037730,399600832,144685230,755716631,873147260,189675946,555134055,803820853,167292449,980935934,756427768,273677419,426764226,569672896,715639481,23792413,980523396,576236604,264661128,206350851,349590410,762445488,761937850,33046179,838255637,770584432,385707472,188057151,905635218,939306745,714545609,439773637,459702428,179669002}

    Returns: 185127924

  24. 293910860223699996

    271747653

    {858509270,63209847,768567475,630123139,881290049,177908512,261757020,624204835,426996348,10056340,88576580,122019678,488504701,990336388,890063567,739135318,566507983,912075163,322497626,419489676,275512080,58016697,536637097,178016618,835497594,752672654,213643657,136292197,785213682,121752512,598075590,571514867,288172560,489867302,418378566,609596567,653676368,350925902,311459739,666543383,370070040,348354260,613132521,954420732,92721490,707140539,821517325,379692697,142991250,768850737}

    {907233359,610257212,588411978,461578434,27307878,56375285,330453729,932094192,73166044,626437981,369476435,203180479,548086657,183851853,365805175,168064389,229013687,492354221,943269837,977768287,714506116,57023297,804710425,441655372,939780092,220744818,645309673,489032835,860029368,220480818,446271286,515484874,9844124,32743333,131850615,483726512,32288054,374070464,64996381,683794276,548681017,950283475,518390501,921198311,423042329,462468258,199008858,829240794,542531823,526792974}

    Returns: 296778816

  25. 314843122145273285

    23276805

    {330183526,567068450,294383771,177573096,193485986,850410779,97917027,902352354,55423392,940021844,424710076,662209188,652595358,231079215,296145644,368951154,525404212,620099950,951322051,626814540,245469234,268982272,348598080,731323768,640179470,471369582,205251441,278936904,606736956,528760246,531142519,424071658,69007083,523990362,1131443,818460009,941854453,749867004,878146037,106069431,790361341,128748448,668380827,19545315,365770377,737449423,244304884,799357239,562851581,314552006}

    {268946143,181355603,762221733,720217301,437958237,49394574,621231392,769782060,568668992,995336237,147128309,454667510,521685108,768927917,139750409,224796756,644707281,344186379,773065130,330499757,986923238,383559089,330298124,521759858,999068677,746174131,27940569,183055217,112400940,772698664,408645179,53735578,625614024,453209747,558165975,282358263,609522087,437786838,278650099,322297235,709319358,297076967,622777023,497463643,437044733,838921112,854115877,836824056,215246695,722984057}

    Returns: 152568727

  26. 10

    10

    {1 }

    {2 }

    Returns: 10

  27. 2269415

    60

    {89, 23, 46, 36, 48, 47, 47, 45, 15, 39, 96, 86, 95 }

    {44, 61, 38, 28, 84, 42, 41, 63, 29, 69, 68, 98, 62 }

    Returns: 2322

  28. 1000000000000000000

    1000000000

    {1 }

    {1000000000 }

    Returns: 63244553204946

  29. 100

    10

    {10 }

    {20 }

    Returns: 10

  30. 1000

    1

    {50 }

    {10000 }

    Returns: 8

  31. 873033661793980928

    575470385

    {929799979, 966896958 }

    {249200867, 249632737 }

    Returns: 902923166

  32. 1001

    5

    {2 }

    {100 }

    Returns: 96

  33. 100000

    1000

    {10 }

    {100 }

    Returns: 5334

  34. 10000

    5

    {39, 37, 44 }

    {8, 6, 1000000 }

    Returns: 63

  35. 100000000000000001

    1000000000

    {500000000 }

    {2 }

    Returns: 200000001

  36. 1000000000

    10000000

    {1 }

    {1000000000 }

    Returns: 190000000

  37. 1000000000000000000

    100000

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    Returns: 19900000

  38. 999999999999999994

    1

    {2 }

    {1 }

    Returns: 499999999999999997

  39. 999999999999999999

    100

    {100 }

    {100 }

    Returns: 100000000009900

  40. 40

    10

    {1 }

    {335 }

    Returns: 30

  41. 100000

    100

    {5, 5, 5, 5, 5, 5, 5, 5, 5, 5 }

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    Returns: 2729

  42. 10000000000

    1

    {1 }

    {1000000000 }

    Returns: 199999

  43. 1

    1000000000

    {1 }

    {123 }

    Returns: 1

  44. 100000000000

    0

    {1 }

    {1000000000 }

    Returns: 100

  45. 100000000000000000

    1000000000

    {1000000000, 1000000000 }

    {100000000, 1000000000 }

    Returns: 100000000

  46. 1000

    0

    {131072 }

    {131072 }

    Returns: 1

  47. 430675856537057621

    754291586

    {1 }

    {5 }

    Returns: 86135174324577869

  48. 1000000000000000000

    12

    {1234, 1235, 1236 }

    {1000000000, 200000000, 200000005 }

    Returns: 197065844

  49. 1000000000000000000

    300000

    {300000 }

    {300000 }

    Returns: 1999700011

  50. 10000000000000

    100000

    {100000 }

    {100000 }

    Returns: 6225000

  51. 3

    4

    {1 }

    {2 }

    Returns: 3

  52. 999999999999999999

    0

    {1, 1 }

    {1, 1 }

    Returns: 999999999999999999

  53. 999999998000000001

    0

    {999999998 }

    {1000000000 }

    Returns: 2

  54. 999999999999999998

    1

    {1 }

    {1 }

    Returns: 999999999999999998

  55. 1000000000

    0

    {1, 1 }

    {1, 1000000000 }

    Returns: 1

  56. 999999999999999998

    0

    {1, 1 }

    {1, 1 }

    Returns: 999999999999999998

  57. 1000000000000000000

    100

    {100 }

    {1000000000 }

    Returns: 1999999900

  58. 741361

    505948

    {48030 }

    {16448 }

    Returns: 16

  59. 962768465676381896

    516548029

    {302116448 }

    {368843516 }

    Returns: 2095344817

  60. 36

    1

    {1 }

    {13 }

    Returns: 11

  61. 7654321

    1

    {1 }

    {1000000000 }

    Returns: 5533

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: