SequenceMerger

TCO10 Qual 1 · 2010-04-11 · by soul-net

TCO10 Qual 1 · 2010-04-11 · by soul-net · Math, Search, Sorting

Show categories

Class Name: SequenceMerger

Return Type: int[]

Method Name: getVal

Arg Types: (vector<string>, vector<int>)

Problem Statement

In this problem, you will be given descriptions of several integer sequences, and you will be required to return elements at certain positions of the union of all the given sequences. The union of several sequences is a sequence containing all the elements of those sequences, sorted in non-decreasing order. For each integer x, the number of occurrences of x in the union is equal to the total number of occurrences of x in all the given sequences. For example, if we are given sequences (3, 2, 2, 3), (1) and (5, 7, 1), their union is the sequence (1, 1, 2, 2, 3, 3, 5, 7).

Each of the given sequences will be an arithmetic sequence, a geometric sequence or an explicit sequence.

An arithmetic sequence is described by three positive integers A, B and C. The sequence contains exactly C elements: A, A+B, A+B+B, ..., A+B*(C-1). Formally, the sequence is { A+B*x | x an integer between 0 and C-1, inclusive}.
A geometric sequence is described by three positive integers A, B and C. The sequence contains exactly C elements: A, A*B, A*B*B, ..., A*B^(C-1). Formally, the sequence is { A*B^x | x an integer between 0 and C-1, inclusive}.
An explicit sequence is just a non-empty sequence of arbitrary positive integers.

Each sequence will be represented as a String, where the first character is 'A', 'G' or 'E', denoting arithmetic, geometric or explicit sequences, respectively. The second character will always be a space. After that is a list of positive integers, where each integer is written with no leading zeroes, consecutive integers are separated by a single space, and there are no leading or trailing spaces. In the case of arithmetic and geometric sequences, this list will always contain exactly three integers, A, B and C, in that order, as described above for each type of sequence. For explicit sequences, the list will contain one or more integers, explicitly representing the members of the sequence.

You will be given a String[] seqs, where each element represents a sequence as described in the previous paragraph, and a int[] positions, which contains a list of 1-based positions. Return a int[] containing the same number of elements as positions, such that its i-th element is the element at position positions[i] of the union of all the sequences in seqs. If the union contains less than positions[i] elements or if the element at position positions[i] of the union is strictly greater than 1000000000 (10^9), the i-th element of the return must be -1 instead. See examples for further clarification.

Notes

The elements of the given sequences don't necessarily fit within 32-bit or 64-bit integer types.

Constraints

positions will contain between 1 and 50 elements, inclusive.
Each element of positions will be between 1 and 1000000000 (10^9), inclusive.
seqs will contain between 1 and 50 elements, inclusive.
Each element of seqs will contain between 3 and 50 characters, inclusive.
Each element of seqs will be formatted as described in the problem statement.

Examples

{"E 1 1000000000 1000000001"}
{1,2,3,4}
Returns: {1, 1000000000, -1, -1 }

The sequence here has only 3 elements. The first two elements are returned normally. The element at position 3 is strictly greater than 1000000000, so you must return -1 in that place. There is no element at position 4, so you must also return -1 there.

{"A 1 1 10", "G 1 2 4"}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
Returns: {1, 1, 2, 2, 3, 4, 4, 5, 6, 7, 8, 8, 9, 10, -1 }

The arithmetic sequence is 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. The geometric sequence is 1, 2, 4, 8. Therefore, the resulting sequence is 1, 1, 2, 2, 3, 4, 4, 5, 6, 7, 8, 8, 9, 10.

{"A 1000000000 1000000000 1000000000","G 100000000000000000 1000000000000 100000000000000", "E 1000000000000000 10000000 10 1111"}
{1,2,3,4,5,6,7,8,9,10}
Returns: {10, 1111, 10000000, 1000000000, -1, -1, -1, -1, -1, -1 }

Watch out for big numbers.

{"G 1 1 999999999", "E 2"}
{1,999999999,1000000000}
Returns: {1, 1, 2 }

A lot of 1s and a 2.

{"A 100 341 1524", "G 1 3 45235", "E 653 87 12341 8785 123 543"}
{100000,1,10,10000,100,1000}
Returns: {-1, 1, 441, -1, 28403, 334621 }

{"A 6814209772886 295079114 1000000009","A 30292388011356732898 7 845174052","A 1000000001 725 487051722964061","A 2743556217493760517698483100189 873740 999999991","A 75332389293609 337 3927546236930713312197316","A 1000000002 999999997 2288389491","A 2989776506745222153 72647 778552629453288","A 9281471269505392193 4526569803 23160220023","A 726120836384204 9 69882745892873543484"}
{130555846,42,598314137}
Returns: {-1, -1, -1 }

// 5-19 are all arithmetic sequences

20)

{"G 768934467814522451310990076533 404 407621195","G 506047399221639863 840 294","G 3004206509995463169244141563435 2 1000000004","G 175473209032770990 981769905897412 36","G 3665104738831803115225319704450699 6476810 4","G 460611383249792029 1261333 886700","G 68852857311 77616010856 55792","G 436436547945 75320249330236411 547628007","G 472527807102352712045 97553100115056180079 6","G 70741131538712584394351168213381 45 1000000000","G 488777488758181826721056107267537 999999994 5","G 4047263847326953180121808757 99 999999999","G 1000000006 3202286 9185262103883185959373","G 670429552216355 999999992 872827443","G 6197899063787606161681 76603809 9319018","G 93524727911964068192755991410397 66 148852","G 4509094841748156453 1192129832891114134 5069","G 952180950522164085232032060 1764916 598912750774","G 967622230532500 3066945663926 89","G 1526166903758474 5706074064688813132690 862832","G 661529310072181262482930 776960 75","G 769994807025235243 4676 4313680","G 667314672290 2 1295937","G 440932508040505309707484127 2015786852187487 312","G 3909023936654200471656548499 4432802473616156 72","G 66298507187 727881895 650625528968782035","G 1000000009 890613 564309557578913165592","G 8636922998 1000000005 7802","G 925750454549 3790011032152699 3","G 942560851912533735298774082 999999998 5818","G 160075649484862252170481690 83 575","G 1000000003 32144 743405101188083743","G 87923997246148238196 2534358551 332891779","G 1302075703290337131277806 62 7889356","G 1000000006 57 7","G 286960581009578093 1000000003 55601564","G 65180943650522159685975626900115658 5161 4","G 575718806540 26999997 286711246","G 416242952063 114 282478","G 14158919487360280 93160 784716619262951048","G 86886924458036894011111172 692 6932572","G 73779886859043521 9 1793296890559","G 2667541689781220264605493958 4760654 5891","G 535091898151358062297784578298 248 906889","G 26012928136513922142640522552450760 49115 51","G 4110229451876317853802475712669 872637 56","G 92937866093414843179244474 160260785913 889525","G 324197150755655532836318966660 14 1000000007","G 2836877285 1006 74757016","G 11176184201250525278846 22 19056440"}
{8,45954256,999999995,999999997,14692323,481251,1,682,90693762,999999992,689592909,350426,261905,35157,86959,999999996,1000000000,85,9,3,6827220,62426,258092226,946,329589,61,999999994,98745,42274,74271464,1630,62794,4648,932,6284308,3540,756,14305,7250154,999999994,80086112,27,39028599,82926,7,5,999999996,715,1134,706609003}
Returns: {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }

// 20 - 50 are all geometric sequences

51)

{"G 8250060 3171910192 41808131981","G 13781574970419894001 6883825687296104 53152921","G 1000000009 7479146 91982","G 506 1 31525","G 91 2272366487345311 8584","A 3 7523699522253590298790 115","A 999999992 11506989338294519970701 9068","A 9546903 52898470 6674999"}
{467013,9,7420,3643,301722,999999993,999999993,1751554,918231561,32010,33735,4,5,59,625431636,74721738,168,50641662,4195,2,181703560,5599,5,648551646,999999991,999999993,79,51318,72968888,49,2,153288454,7424,78,1940918,583974,632084531,7889192,7,78748551,67,9,282387797,81917477,696038,15117,37,7479047,85345,821}
Returns: {-1, 506, 506, 506, -1, -1, -1, -1, -1, -1, -1, 506, 506, 506, -1, -1, 506, -1, 506, 91, -1, 506, 506, -1, -1, -1, 506, -1, -1, 506, 91, -1, 506, 506, -1, -1, -1, -1, 506, -1, 506, 506, -1, -1, -1, 506, 506, -1, -1, 506 }

// 51 - 70 is a mix of arithmetic and geometric

71)

{"E 24","E 84173","E 1078617556963434748622800581412","E 80057948","E 56635492488222889471","E 262103583","E 999999999","E 14707731651939","E 9070","E 626168"}
{128100604,217348,826,61952045,7820136,47896,8,6049,266817951,6204,2991,9,396345754,999999997,999999992,95157,46,88,5,97292,776,16270,2553,37564097,9929727,999999996,190765,5615128,6305354,747,40995428}
Returns: {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 80057948, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }

// 71 - 77 are explicit sequences

78)

{"A 999999999 15537848441 992","A 999999996 20929899789132982 52232995754","A 35844504880 923 545975","A 82797 968118209331376969004148670409353 3314115","E 942126200340"}
{999999993,2,56608088,45907276,87151,815968,5175546,68,55668277,595,60691,71411,82363,2,509726190,613232202,958422,83410664,515,59750921,52884,275094,549,3307414,504,999999993,31,7126,36690938,3306044,999999991,559771032,47935921,999999995,999999992,6,483933614,16820,429188268,1827,5,77825950,2544073,2183255,8,7840639,999999991,22,28015835,468331}
Returns: {-1, 999999996, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 999999996, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }

// 78 - 97 are arithmetic and explicit

98)

{"E 4373","E 91337267012000","E 235 412 5906","E 44297284684136907741129516310317","E 999999997","E 257","E 70982 659 208 9 9 99","E 64431","E 4662041799829177835489482976892189559160889","E 251687363603995431097547619","E 1469315436482207","E 7697 9617 6100","G 31778865 1 9436336","E 7936311051 463825051300294013386","G 6385 1 80","E 727860","E 83191943094","E 3484013","E 7116","E 216381255","E 367388173920842948151624873","E 6620","G 427 193572 6593310934286110765078499840","E 2188283902652068298729914","E 5799333","E 667088 161677 494029 91405 304364 3724112 627563","E 2488603173599037473031955360","E 8539950275781969542145","E 6941 5257 37251 3617 9550","E 506490783646082088621822","E 5 3 5 6 6 5 5 3 3 6 4 4 5 4 5 5 4 6 3 5 4 4 6 4","E 27945 10 5 5 25 21 7397 8 22 4259","G 52 3 7","E 4694933","E 4403916","E 18941 734 2179 431 8862","G 9 60 3","G 550 1285694 1","E 4 9 4 14 9 30 4 9 3 26 30 30 8 3 3 3 9 5 25 9 5","E 1362414","G 79 80 2","E 649 7443 3952 7761 8742 8104 636 537","E 75591612 63320 445682 42040668 937348687 1546","E 58613 4954 754 5474 6239","E 77825","E 941989","E 33038704184703622281335","E 7359515783834102463813652","E 62533744","E 999999991"}
{7955989,5267695,49505754,246218640,77,95}
Returns: {31778865, 31778865, -1, -1, 2179, 6385 }

// 98 - 117 are geometric and explicit

118)

{"E 4373","E 91337267012000","E 235 412 5906","E 44297284684136907741129516310317","E 999999997","E 257","E 70982 659 208 9 9 99","E 64431","E 4662041799829177835489482976892189559160889","E 251687363603995431097547619","E 1469315436482207","E 7697 9617 6100","G 31778865 1 9436336","E 7936311051 463825051300294013386","G 6385 1 80","E 727860","E 83191943094","E 3484013","E 7116","E 216381255","E 367388173920842948151624873","E 6620","G 427 193572 6593310934286110765078499840","E 2188283902652068298729914","E 5799333","E 667088 161677 494029 91405 304364 3724112 627563","E 2488603173599037473031955360","E 8539950275781969542145","E 6941 5257 37251 3617 9550","E 506490783646082088621822","E 5 3 5 6 6 5 5 3 3 6 4 4 5 4 5 5 4 6 3 5 4 4 6 4","E 27945 10 5 5 25 21 7397 8 22 4259","G 52 3 7","E 4694933","E 4403916","E 18941 734 2179 431 8862","G 9 60 3","G 550 1285694 1","E 4 9 4 14 9 30 4 9 3 26 30 30 8 3 3 3 9 5 25 9 5","E 1362414","G 79 80 2","E 649 7443 3952 7761 8742 8104 636 537","E 75591612 63320 445682 42040668 937348687 1546","E 58613 4954 754 5474 6239","E 77825","E 941989","E 33038704184703622281335","E 7359515783834102463813652","E 62533744","E 999999991"}
{7955989,5267695,49505754,246218640,77,95}
Returns: {31778865, 31778865, -1, -1, 2179, 6385 }

// 118 - 137 are all types of sequences

138)

{"E 9 8 7 9 4 7 3 7 8 1 2 3 1 4 9 3 1 8 5 2 4 6 6 5","E 5 5 5 2 2 3 4 2 2 4 2 4 5 3 5 4 5 4 2 3 2 4 4 4","E 5 6 8 7 6 7 3 6 6 5 8 4 4 5 3 7 3 7 4 4 4 8 6 7","E 6 9 8 9 4 6 5 8 4 5 9 5 5 8 8 9 7 6 7 6 9 3 10 7","E 7 8 8 9 8 8 8 8 8 8 9 9 9 9 8 8 9 8 7 7 8 8 9 9","E 5 5 4 4 4 5 5 2 4 5 5 2 5 4 2 5 2 4 4 5 3 5 3 4","E 3 3 5 3 3 4 3 5 4 5 6 4 4 5 6 4 5 5 3 5 4 6 5 3","E 8 5 9 4 3 8 8 9 5 4 6 7 9 7 7 3 6 9 4 7 4 3 7 7","E 5 5 4 3 4 5 5 6 5 3 5 6 6 5 6 6 3 5 4 5 3 4 6 4","E 6 8 5 3 7 3 6 7 4 8 3 5 6 3 7 6 6 3 7 7 7 4 6 8","E 5 5 5 5 5 6 6 4 5 5 6 6 6 6 5 4 4 6 4 6 5 5 5 4","E 4 7 4 7 6 8 5 5 7 6 7 7 7 8 5 5 7 6 8 8 5 6 4 4","E 8 8 9 9 8 7 8 9 9 7 8 9 8 9 7 7 7 7 9 9 7 7 9 7","E 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6","E 3 4 2 4 2 3 3 3 4 3 2 3 3 2 2 2 4 3 2 3 3 4 3 4","E 5 5 6 7 6 7 7 7 7 7 6 7 6 7 7 7 5 5 5 5 5 7 5 5","E 5 6 6 4 7 6 5 6 7 7 4 6 6 4 5 4 6 6 5 7 6 5 7 4","E 2 1 1 1 2 2 1 1 1 2 1 1 2 1 2 2 1 1 1 2 2 1 1 1","E 9 9 8 8 9 9 9 9 8 9 9 8 8 9 9 9 9 9 9 9 9 9 9 8","E 3 6 4 4 2 3 5 6 2 6 2 3 4 2 5 2 4 5 6 4 3 6 3 3","E 5 4 6 6 6 4 3 4 6 3 6 3 6 6 6 6 6 3 4 4 5 5 6 6","E 6 7 5 9 9 9 8 6 9 6 7 9 9 6 9 9 5 9 8 8 7 4 6 5","E 2 3 2 1 3 2 1 3 1 2 2 1 1 2 2 2 2 1 3 1 2 2 1 3","E 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5","E 6 2 4 4 5 6 8 5 9 3 3 5 5 6 2 6 4 8 5 9 5 2 3 3","E 9 5 8 8 7 9 6 5 8 5 6 7 5 9 9 8 7 9 8 7 6 9 7 5","E 7 4 3 4 5 7 6 4 6 4 6 6 6 3 5 6 7 4 7 4 4 4 4 4","E 2 2 3 2 3 4 1 4 4 3 1 1 3 1 4 3 4 1 2 2 4 1 1 1","E 6 2 5 7 7 7 2 8 5 5 2 8 4 7 2 6 2 5 9 8 3 3 6 3","E 5 3 5 4 5 5 5 5 5 3 3 4 5 5 3 3 4 5 4 4 3 3 3 4","E 3 5 2 5 2 5 4 2 5 5 4 3 3 4 2 2 3 4 3 4 4 2 5 4","E 7 7 8 6 7 8 9 6 8 7 9 8 7 9 9 6 7 9 6 6 6 6 6 7","E 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9","E 6 6 4 5 5 4 4 4 6 6 5 6 6 6 4 4 5 6 5 5 6 5 4 5","E 5 6 5 6 6 5 5 6 5 5 6 5 5 5 6 6 6 5 6 5 6 5 5 5","E 5 3 2 2 7 6 4 2 5 6 4 5 9 5 3 8 4 4 8 2 4 7 8 6","E 8 8 9 9 9 9 8 9 8 8 8 9 8 8 9 9 8 9 9 8 9 8 9 8","E 3 3 2 3 4 2 4 4 4 3 2 2 1 2 1 2 4 2 3 3 2 4 3 3","E 4 3 3 5 4 3 5 3 3 5 3 5 5 3 3 3 4 3 5 4 3 4 3 4","E 7 9 9 8 8 9 9 7 9 7 9 8 9 8 8 7 7 9 7 11 9 7 7 7","E 4 5 4 4 7 4 5 7 1 4 3 5 6 4 5 4 3 5 5 6 5 6 5 6","E 4 3 3 2 3 4 2 3 4 3 4 4 4 4 2 3 4 2 4 2 3 2 2 2","E 2 3 3 1 3 2 3 2 3 3 2 3 3 3 3 1 3 2 2 2 3 1 1 1","E 2 5 6 6 4 2 4 3 7 7 2 2 8 6 6 2 2 8 7 7 6 1 5 6","E 4 7 5 7 4 3 3 4 5 7 5 5 5 3 3 6 6 5 5 5 4 5 7 4","E 1 1 1 2 1 1 2 1 2 2 1 2 1 2 2 1 1 1 2 1 1 2 2 1","E 7 6 2 3 8 2 6 6 4 6 7 2 2 4 4 7 6 6 3 6 8 8 7 3","E 5 5 6 5 5 5 5 6 5 6 5 6 5 6 6 5 5 5 6 6 6 6 6 5","E 8 8 8 8 8 7 7 8 8 7 8 8 7 7 8 8 8 7 7 7 8 7 8 8","E 3 5 6 2 7 6 5 6 3 7 5 2 6 6 6 4 5 5 7 7 2 2 6 7"}
{8437475,49740,999999992,602033,8,638376,26900853,9055,56230156,7277347,35543,4583210,671567,2,64659,619311570,69628831,74599966,4090,999999992,31372,7941,28591262,3070216,70432,198490141,4358,99034,65430162,916603836,340224327,9684,34765,14965613,70576405,703145698,1000000000,2,93361834,7567,72259006,117247897,30,515633771,152,20128271,9480,40432719,6,476743173}
Returns: {-1, -1, -1, -1, 1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, -1, -1, -1, 1, -1, 2, -1, -1, -1, 1, -1 }

// 138 and 139 are long explicit sequences // 139 makes my solution run pretty slow

140)

{"G 95 729176519456693423 235066368","G 8 1617193837 3607395865861353145692549471678389","A 135965306 694301957 3097","A 7320888884758182856311867671700 285726 258"}
{4387,190551,2,23707363,1514,395558,2,911,859223067,3681,31404,399,893977,14152753,4425317,229249904,4,2}
Returns: {-1, -1, 95, -1, -1, -1, 95, -1, -1, -1, -1, -1, -1, -1, -1, -1, 830267263, 95 }

// all the rest are randoms that catch some tricky bugs

Submissions are judged against all 177 archived test cases, of which 14 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SequenceMerger with a public method vector<int> getVal(vector<string> seqs, vector<int> positions) · 177 test cases · 2 s / 256 MB per case