PartitionArray
SRM 762 · 2019-07-01 · by teja349
SRM 762 · 2019-07-01 · by teja349 · Greedy
Problem Statement
Problem Statement
An array A is called positive partitionable if we can divide A into one or more contiguous subarrays such that each element belongs to exactly one of the subarrays and the sum of each subarray is positive.
For example, the array {3,-7,8} is positive partitionable. One valid way of splitting this array is to split it into {3} and {-7,8}. The array {0,1,0,1,2} is also positive partitionable. The array {-1,2,-3,4,-5} and the array {0} are not positively partitionable.
A partition of an array can be described by listing the lengths of the partitions, in order. For example, {3} has length 1 and {-7,8} has length 2, hence the partition of {3,-7,8} into {3} and {-7,8} can be described by the sequence {1,2}. The sequences {2,3}, {2,2,1}, and {4,1} describe different three valid ways of partitioning the sequence {0,1,0,1,2}.
You are given the
Constraints
- a will have between 1 and 500 elements, inclusive.
- All elements of a will be between -10^6 and 10^6, inclusive.
Examples
0)
{-1000000}
Returns: {-1 }
1)
{-547836,-574054,-789614,-149878,-539453,-270012,-966746,-831756,-894677,-146209,-464224,-811270,-235061,-575473,-307897,-950572,-723360,-319470,-747139,-173517,-848786,-393184,-766631,-801390,-784365,-192236,-375611,-399653,-492630,-450208,-589498,-716748,-881370,-317001,-636127,-761563,-643597,-548779,-611316,-574763,-862501,-720295,-899636,-917094,-465905,-435369,-923871,-550242,-935506,-962798,-852703,-290158,-634751,-970946,-183880,-25449,-279278,-326390,-610936,-240984,-12895,-602683,-571111,-859157,-948689,-560441,-852161,-171403,-97578,-737618,-520858,-680520,-803894,-947657,-448728,-717779,-919305,-393493,-5244,-408761,-84101,-357817}
Returns: {-1 }
2)
{-274180,-40763,-175731,-943348,-600315,-186306,-785970,-448194,-646680,-223576,-970119,-683937,-895019,-775837,-595258,-170937,-383920,-835365,-623268,-725581,-226649,-147649,-823749,-934296,-614895,-62965,-481838,-385609,-233078,-929752,-537081,-747572,-797233,-856205,-460394,-976175,-110241,-588527,-585465,-28785,-353015,-855918,-912818,-929689,-57358,-213349,-436170,-584909,-51331,-572377,-338536,-717652,-46734,-176116,-284653,-375464,-500338,-334905,-545579,-124120,-523601,-806629,-652606,-508773,-716899,-458957,-99591,-700958,-435693,-773097,-912115,-27464,-207708,-164605,-872972,-853499,-748497,-791842,-831167,-59134,-123097,-602780,-140446,-727330,-235548,-725131,-344323,-266613,-657981,-243156,-621289,-696738,-10683,-366242,-808580,-197374,-253286,-541142,-976417,-614922,-522172,-626152,-132606,-141649,-359954,-392473,-925129,-282073,-408127,-681793,-373470,-109508,-907088,-147092,-1087,-498892,-96246,-631333,-50595,-9513,-938661,-694418,-380548,-731973,-75916,-495052,-969197,-804791,-669770,-160770,-164217,-276528,-730562,-189525,-808880,-196883,-64765,-715011,-43649,-781134,-290089,-640654,-350744,-902180,-968184,-373732,-762578,-712946,-765443,-94739,-788868,-524728,-200610,-603207,-679564,-812280,-977661,-892451,-180012,-949696,-524814,-504624,-697399,-415660,-395962,-898141,-738754,-305479,-407303,-248588,-939237,-439721,-521407,-242753,-766786,-215585,-938349,-732820,-105215,-835064,-742500,-413223,-355634,-366755,-174694,-465744,-139676,-187721,-949097,-835972,-797539,-177671,-397130,-905193,-864179,-203266,-710405,-716456,-999345,-221473,-805145,-409537,-701698,-754550,-620244,-251921,-506750,-954386,-887943,-752080,-321836,-740140,-134277,-38790,-289016,-599564,-568805,-431822,-977893,-595843,-606548,-687865,-136276,-889163,-687412,-308495,-886826,-679778,-568748,-849895,-987250,-974490,-874824,-673688,-558869,-475073,-280573,-541970,-453579,-440773,-339843,-326398,-550302,-462185,-996248,-896980,-685500,-22606,-306134,-232122,-170237,-936764,-601775,-22080,-249553,-238254,-538425,-29825,-515696,-618717,-515491,-2855,-133374,-144646,-620192,-256174,-656067,-273377,-845651,-448155,-868628,-175737,-41632,-646733,-510812,-842703,-257998,-166779,-989492,-715918,-66884,-510930,-800717,-863957,-843537,-176863,-980435,-613453,-382964,-721534,-617046,-346458,-795724,-736901,-248388,-373208,-176374,-145931,-805388,-676235,-248938,-505464,-751194,-934313,-138134,-286326,-888656,-447863,-15551,-394497,-433650,-10061,-848582,-166903,-474445,-401729,-331442,-329069,-801079,-320303,-862804,-495155,-584244,-840043,-221661,-677462,-134604,-964547,-822803,-213180,-889875,-126711,-758627,-931981,-835498,-260429,-365999,-109595,-694901,-372274,-925262,-602140,-408097,-408674,-556492,-120572,-719852,-274433,-336978,-960595,-499229,-744836,-300928,-857618,-89802,-343084,-677977,-739276,-935377,-475589,-881914,-925324,-622647,-189665,-259291,-675992,-228131,-753451,-491667,-736821,-490798,-629928,-906001,-844879,-475736,-278920,-268272,-301715,-568426,-207078,-286939,-266540,-401597,-504829,-131289,-178342,-979063,-891661,-187710,-629175,-554083,-8095,-724820,-724747,-696679,-647459,-214186,-721085,-20629,-103916,0,-647685,-438653,-823075,-800729,-190338,-943975,-102454,-793216,-801642,-6369,-851644,-625812,-290272,-929651,-264619,-847145,-705413,-588380,-594038,-472227,-344722,-331952,-56172,-135690,-191736,-957158,-887956,-28610,-972359,-923050,-544995,-14846,-271032,-852945,-83092,-188932,-205351,-125319,-639905,-684483,-973663,-772923,-24274,-793677,-72345,-195217,-292500,-213334,-533720,-884255,-133074,-837866,-113787,-583192,-878814,-303083,-611000,-65808,-291983,-574993,-318136,-835433,-33932,-930456,-79494,-239385,-294077,-196981,-12172,-54657,-874082,-997627,-714960,-384736,-349705,-323095,-693332,-33870,-249286,-433323,-786737,-125693,-944396,-164439,-82268,-902331,-337582,-160715,-403682,-668143,-333928,-216261,-668277,-840924,-586106}
Returns: {-1 }
3)
{-881865,-935662,-550901,-609553,-448823,-942743,-987321,-12955,-885986,-916196,-133665,-499919,-236221,-779008,-618275,-920018,-513791,-816369,-807351,-976988,-741487,-323921,-845714,-217421,-209689,-800578,-533645,-953720,-840335,-942067,-970365,-849471,-324783,-369023,-842190,-500962,-824513,-73471,-868495,-856666,-1279,-754491,-223739,-753837,-6003,-893381,-855146,-766135,-177589,-736396,-190494,-351616,-208663,-150101,-333487,-726096,-121544,-143264,-133645,-781491,-762545,-26791,-805934,-634028,-309643,-127590,-957711,-215003,-611263,-775706,-616195,-914762,-498291,-425585,-698263,-202044,-502963,-767304,-51331,-625785,-102353,-544204,-342183,-323283,-539804,-31547,-957888,-431770,-831996,-544134,-438107,-315147,-875935,-846437,-843173,-465542,-405290,-8836,-513387,-311556,-346107,-589987,-385364,-169310,-556069,-629578,-85954,-615118,-360563,-115086,-381409,-531309,-528749,-93571,-434848,-255036,-830169,-955084,-809694,-535926,-900041,-138594,-675373,-223921,-358620,-7534,-461689,-942661,-879432,-665391,-292272,-200887,-988874,-550386,-433877,-265694,-907376,-686499,-265465,-266761,-394178,-880108,-545976,-452529,-433604,-87844,-646072,-286296,-195674,-808279,-479120,-400506,-330294,-288502,-622234,-884256,-538791,-614303,-683635,-896232,-262256,-502993,-122605,-505398,-151380,-52959,-94777,-767561,-302305,-288552,-395481,-752493,-382009,-388131,-408706,-824427,-866179,-256463,-444722,-60925,-439169,-770175,-653431,-109582,-48027,-118689,-733196,-959318,-647137,-406637,-532407,-383250,-759207,-206495,-835987,-281799,-474417,-365241,-638515,-994190,-742389,-485914,-356467,-223582,-738633,-961543,-207376,-865833,-678259,-182640,-49519,-784127,-387957,-534468,-538405,-679473,-889858,-817513,-220555,-112070,-918749,-716855,-998783,-894146,-185159,-260773,-333663,-563032,-574446,-670429,-971248,-10406,-891477,-706775,-646131,-959690,-902949,-811322,-311087,-297389,-164971,-306235,-701633,-68701,-92818,-266971,-206187,-62886,-686555,-288060,-200162,-375030,-304004,-237477,-662732,-365789,-34837,-339147,-445776,-342839,-560041,-541394,-49732,-364873,-169734,-149834,-980898,-287037,-942228,-860767,-793737,-239327,-717705,-1000000,-299753,-392776,-949799,-481708,-558359,-622965,-325376,-121129,-812948,-301927,-254429,-382576,-846598,-415257,-288556,-402066,-206711,-798700,-816409,-568399,-552366,-239883,-970999,-358731,-35543,-730713,-145436,-573471,-169144,-443031,-900381,-225286,-135352,-522489,-546434,-871132,-282204,-671349,-776203,-256779,-361061,-319991,-87813,-467570,-604146,-709508,-161417,-911792,-563397,-443427,-1000000,-808763,-93061,-418328,-397512,-551422,-529958,-743605,-236621,-407268,-951605,-71633,-660486,-238556,-997199,-963581,-493807,-984061,-229026,-595376,-355931,-436589,-959652,-20643,-340262,-944770,-969248,-853778,-722079,-620506,-268042,-710798,-778761,-581840,-757023,-693010,-901798,-604323,-733708,-492097,-805987,-343062,-841766,-263466,-378544,-310623,-155123,-940666,-39142,-179618,-34458,-56741,-926204,-2694,-356145,-568555,-255713,-653509,-310936,-110700,-398391,-3716,-648865,-895059,-483796,-141774,-717174,-424002,-129984,-357397,-814046,-173828,-725158,-402496,-579665,-678949,0,-414782,-320200,-773586,-867010,-132763,-369456,-82470,-715240,-147975,-793648,-101057,-572293,-730431,-351090,-750898,-120816,-994973,-541657,-800496,-133729,-842655,-907484,-608422,-438184,-468633,-440832,-923252,-182651,-426975,-758636,-706241,-441118,-377836,-405404,-311753,-3934,-544941,-175264,-510450,-946578,-651123,-30966,-361781,-405347,-871879,-328953,-181142,-147854,-735272,-243464,-109469,-704812,-881660,-509044,-291949,-941383,-981349,-451579,-103611,-483716,-315448,-937929,-572674,-404095,-958964,-241816,-514058,-132207,-337967,-949909,-615931,-585139,-765241,-650096,-555773,-885765,-683888,-179739,-334302,-502979,-938835,-582668,-605042,-786912,-593715,-725453,-458164,-515608,-217653,-415661,-784831,-708452,-732969,-685530,-17692,-728333,-861287,-334374}
Returns: {-1 }
4)
{999997}
Returns: {1 }
68)
{3,-7,8}
Returns: {1, 2 }
The first example from the problem statement.
69)
{0,1,0,1,2}
Returns: {4, 1 }
Remember that you may return the description of any partition of the input sequence into one or more pieces, each with a positive sum. Each valid answer will be accepted.
Submissions are judged against all 101 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PartitionArray with a public method vector<int> positiveSum(vector<int> a) · 101 test cases · 2 s / 256 MB per case