LexicographicPartition
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
for i = 0 .. len(Aprefix)-1:
A[i] = Aprefix[i]
state = seed
for i = len(Aprefix) .. n-1:
state = (1103515245 * state + 12345)
A[i] = state modulo (2*Arange+1)
A[i] = A[i] - Arange
state = state modulo 2^31
If this array A isn't positive partitionable, return {-1}. Otherwise, find an array B that describes a valid partition of A. If there are multiple possibilities for B, pick the lexicographically smallest one. Return an array that contains the value length(B) and then the first min(len(B),200) elements of B, in order.
Notes
- Given two different sequences A[0..a-1] and B[0..b-1] such that neither is a prefix of the other, the lexicographically smaller sequence is the one that has a smaller value at the first index at which they differ. For example, {3, 7, 100} < {3, 10, 12, 45} because 7 < 10.
Constraints
- n will be between 1 and 200,000 inclusive.
- All elements of Aprefix will be between -10^6 and 10^6 inclusive.
- Aprefix will contain between 0 and min(n,500) elements inclusive.
- seed will be between 1 and 10^9 inclusive.
- Arange will be between 0 and 10^6 inclusive.
Examples
0)
1
{-1000000}
787052618
452164
Returns: {-1 }
1)
79
{-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}
875945258
87344
Returns: {-1 }
2)
499
{-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,-99781,0,-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,-235929,-881865,-935662,-550901}
48383914
551177
Returns: {-1 }
3)
498
{-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,-389528,-414782,-320200,-773586,-867010,-132763,0,-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,-946308,-912460,-154027,-645873,-715398}
107232746
644627
Returns: {-1 }
4)
1
{999997}
228279041
970393
Returns: {1, 1 }
128)
3
{3,-7,8}
1
1
Returns: {2, 1, 2 }
A = {3,-7,8}. The lexicographically smallest sequence that describes a valid partition is indeed the sequence B={1,2} mentioned in the statement. Thus, we return the array {length(B),1,2} = {2,1,2}.
129)
5
{0,1,0,1,2}
42
47
Returns: {3, 2, 2, 1 }
The optimal B is {2,2,1}.
Submissions are judged against all 154 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class LexicographicPartition with a public method vector<int> positiveSum(int n, vector<int> Aprefix, int seed, int Arange) · 154 test cases · 2 s / 256 MB per case