Boxing

TCO04 Round 3 · 2004-09-07 · by dgoodman

TCO04 Round 3 · 2004-09-07 · by dgoodman · Greedy, Sorting

Show categories

Class Name: Boxing

Return Type: int

Method Name: maxCredit

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

Problem Statement

In Olympic boxing, there are five judges who press a button when they think that a particular boxer has just landed a punch. The times of the button presses are recorded, and the boxer receives credit for a punch if at least three of the judges press their buttons within 1 second of each other.

This "algorithm" needs a lot of refinement. Here is the version that you should implement. Find the maximum number of disjoint time intervals that can be chosen such that each interval is of duration 1 second or less and contains button presses from at least 3 different judges. Two intervals are disjoint if every time within one interval is strictly less than every time in the other. We give the boxer credit for one punch during each interval.

The duration of an interval is the amount of time between the instant when it starts and when it ends, and a punch may be included in an interval if its recorded time is at the start, end, or in between. So, for example, the interval from 1 to 4 has duration 3, and a punch recorded at time 1, 2, 3, or 4 is in that interval. The intervals 1 to 4 and 5 to 22 are disjoint, but the intervals 1 to 4 and 4 to 22 are not disjoint.

Create a class Boxing that contains a method maxCredit that is given five int[]s, a, b, c, d, and e, representing the times of the button presses of the five judges in milliseconds. The method returns the maximum credits that can be given to the boxer.

Constraints

Each of the five arguments will contain between 0 and 50 elements inclusive.
Each element of each of the arguments will be between 0 and 180,000 inclusive.
The elements within each of the arguments will be in strictly increasing order.

Examples

{1,2,3,4,5,6}
{1,2,3,4,5,6,7}
{1,2,3,4,5,6}
{0,1,2}
{1,2,3,4,5,6,7,8}
Returns: 6

This match had a fast start, with 6 punches credited in the first 6 milliseconds of the match! One way to choose 6 disjoint intervals is to choose [1,1], [2,2], [3,3], [4,4], [5,5], [6,6] each of which contains button presses from judges a, b, and c. There are three button presses in the time interval from 7 through 8, but only from two different judges so no additional credit can be given.

{100,200,300,1200,6000}
{}
{900,902,1200,4000,5000,6001}
{0,2000,6002}
{1,2,3,4,5,6,7,8}
Returns: 3

One way to form three intervals is [0,1000], [1001,2000], [6000,6002]

{5000,6500}
{6000}
{6500}
{6000}
{0,5800,6000}
Returns: 1

Any interval that doesn't include 6000 will not have enough button presses, so we can form only one disjoint interval with credit for a punch.

{}
{}
{}
{}
{}
Returns: 0

{180000}
{1,2,3,4,5,6,179000,179500,179800}
{5,10,1000,10000}
{5,10,1000,10000}
{6,9000}
Returns: 3

{2699,10692,13011,15965,17741,19186,23392,32495,32890,33294,38153,41040,48392,54352,55114,55658,55960,56201,64961,65481,65515,75634,78801,79643,83789,89641,96181,96216,104873,106920,117908,118745,120013,122753,124907,125091,126876,129105,133341,135052,136473,137495,139277,142103,143967,144712,150713,153393,158784,161182}
{1595,8642,8954,11045,11249,20771,27970,31274,36528,36892,41520,44978,54877,57368,65224,69869,73501,75231,76272,76423,78302,83535,87222,88010,88361,88945,92000,93747,97352,98511,98960,102550,102990,106636,115539,120722,122265,122430,126235,134111,143167,149823,151733,153758,155472,156083,158202,166624,172914,175590}
{3780,9366,13367,23559,24191,24831,25786,26391,26794,26852,31798,37596,38421,48740,49811,56623,62882,77821,82774,85865,87313,91804,92493,92818,95129,95923,104007,110764,113758,114294,115821,122485,126932,133926,136982,138418,138999,145410,149647,150652,151485,153397,156791,156801,159556,160288,161454,161636,166235,178516}
{5054,10277,11234,13012,17143,20271,22171,23615,28055,35313,48476,53922,59118,61729,64751,65548,68138,74352,85808,87073,90894,90962,95082,101435,102635,103405,104385,104656,104760,110629,130051,134159,135014,136227,140978,141735,143163,149823,149917,154906,158519,160314,162052,168874,170552,172221,175517,176894,177644,177679}
{2388,3005,5419,7320,8811,8870,10630,21793,22133,23869,35905,37104,37474,37490,37978,39589,43939,44835,49094,50658,57209,59529,70009,74916,81029,87448,89111,89635,91942,97418,100352,104035,107523,113736,114910,123639,124246,126071,135449,136225,141088,142377,155102,156125,163533,163921,164128,164941,167598,168811}
Returns: 32

{2699,10692,13011,15965,17741,19186,23392,32495,32890,33294,38153,41040,48392,54352,55114,55658,55960,56201,64961,65481,65515,75634,78801,79643,83789,89641,96181,96216,104873,106920,117908,118745,120013,122753,124907,125091,126876,129105,133341,135052,136473,137495,139277,142103,143967,144712,150713,153393,158784,161182} {1595,8642,8954,11045,11249,20771,27970,31274,36528,36892,41520,44978,54877,57368,65224,69869,73501,75231,76272,76423,78302,83535,87222,88010,88361,88945,92000,93747,97352,98511,98960,102550,102990,106636,115539,120722,122265,122430,126235,134111,143167,149823,151733,153758,155472,156083,158202,166624,172914,175590} {3780,9366,13367,23559,24191,24831,25786,26391,26794,26852,31798,37596,38421,48740,49811,56623,62882,77821,82774,85865,87313,91804,92493,92818,95129,95923,104007,110764,113758,114294,115821,122485,126932,133926,136982,138418,138999,145410,149647,150652,151485,153397,156791,156801,159556,160288,161454,161636,166235,178516} {5054,10277,11234,13012,17143,20271,22171,23615,28055,35313,48476,53922,59118,61729,64751,65548,68138,74352,85808,87073,90894,90962,95082,101435,102635,103405,104385,104656,104760,110629,130051,134159,135014,136227,140978,141735,143163,149823,149917,154906,158519,160314,162052,168874,170552,172221,175517,176894,177644,177679} {2388,3005,5419,7320,8811,8870,10630,21793,22133,23869,35905,37104,37474,37490,37978,39589,43939,44835,49094,50658,57209,59529,70009,74916,81029,87448,89111,89635,91942,97418,100352,104035,107523,113736,114910,123639,124246,126071,135449,136225,141088,142377,155102,156125,163533,163921,164128,164941,167598,168811}

{1520,1846,7333,8112,20247,27916,39498,41761,46386,47793,56674,57549,61237,61738,61807,65566,69075,71904,74585,80694,84588,86505,88568,89512,91125,99605,104067,105132,109113,111132,112180,112192,124246,125499,132535,136731,137175,143796,144887,145500,146398,150481,154549,154625,159865,163845,164236,175503,175900,176126}
{2573,2723,5513,5935,8194,12985,23445,29571,31423,31487,40780,51677,56402,59271,60194,60478,66049,70507,73577,74547,75331,77356,80258,81166,83826,87223,88214,89516,97263,102691,111577,117020,118327,119370,119660,125980,130251,139707,142443,148094,157423,166045,167681,167759,167818,168658,169568,170767,175423,175720}
{959,4395,7172,8529,9331,14385,23960,25489,31966,35544,36902,43935,45973,50360,51612,60847,62728,64504,69043,69729,70709,70853,73450,73670,78050,78098,84248,85529,94807,95321,96076,99179,100936,104392,106920,107507,110199,113120,129867,131702,140539,142123,142408,145029,146598,158440,162276,163556,165301,176549}
{6720,7433,7788,11690,17426,20105,23451,26032,36674,38158,39144,41710,42534,44682,48068,52603,58238,59746,60568,68524,80900,83011,87298,88995,91297,94327,95120,96803,106949,108191,108590,116531,120351,122883,124316,129214,129599,135157,140186,142868,143710,143892,146237,150549,151505,153595,154854,155600,156528,170935}
{2234,15006,18258,19351,20627,25780,27578,28999,29014,30624,35196,35837,36317,41041,51208,58629,62003,62009,65021,68516,68598,83627,92390,97218,103272,110723,119850,120544,122313,124948,125626,127582,128559,132029,132666,136231,137211,140195,143206,143535,146053,148029,160479,161179,163014,165505,169279,171856,176947,179620}
Returns: 31

{1520,1846,7333,8112,20247,27916,39498,41761,46386,47793,56674,57549,61237,61738,61807,65566,69075,71904,74585,80694,84588,86505,88568,89512,91125,99605,104067,105132,109113,111132,112180,112192,124246,125499,132535,136731,137175,143796,144887,145500,146398,150481,154549,154625,159865,163845,164236,175503,175900,176126} {2573,2723,5513,5935,8194,12985,23445,29571,31423,31487,40780,51677,56402,59271,60194,60478,66049,70507,73577,74547,75331,77356,80258,81166,83826,87223,88214,89516,97263,102691,111577,117020,118327,119370,119660,125980,130251,139707,142443,148094,157423,166045,167681,167759,167818,168658,169568,170767,175423,175720} {959,4395,7172,8529,9331,14385,23960,25489,31966,35544,36902,43935,45973,50360,51612,60847,62728,64504,69043,69729,70709,70853,73450,73670,78050,78098,84248,85529,94807,95321,96076,99179,100936,104392,106920,107507,110199,113120,129867,131702,140539,142123,142408,145029,146598,158440,162276,163556,165301,176549} {6720,7433,7788,11690,17426,20105,23451,26032,36674,38158,39144,41710,42534,44682,48068,52603,58238,59746,60568,68524,80900,83011,87298,88995,91297,94327,95120,96803,106949,108191,108590,116531,120351,122883,124316,129214,129599,135157,140186,142868,143710,143892,146237,150549,151505,153595,154854,155600,156528,170935} {2234,15006,18258,19351,20627,25780,27578,28999,29014,30624,35196,35837,36317,41041,51208,58629,62003,62009,65021,68516,68598,83627,92390,97218,103272,110723,119850,120544,122313,124948,125626,127582,128559,132029,132666,136231,137211,140195,143206,143535,146053,148029,160479,161179,163014,165505,169279,171856,176947,179620}

12)

{0,981,3613,26000,26176,37010,38435,39040,40685,42425,46970,59261,67421,67920,82003,85701,87573,91240,93491,107579,112368,113824,116747,121687,125755,127324,132032,140824,143746,144757,146730,155636,156018,157475,162649,163964,165479,170919,177957,179764,179965}
{0,1217,4153,5425,17053,19129,43622,46089,48103,50301,53492,56102,68174,84843,85637,87136,87185,88702,95409,95797,101068,104223,106991,108238,108955,117189,119639,121061,124599,125297,126114,134470,138386,145528,147670,152412,162297,164351,165708,168293,172580}
{0,11051,13830,19854,30421,36371,36535,36897,37306,38723,38925,41350,46265,48062,58292,64193,68744,70567,72253,76984,82827,95247,101210,101222,102896,108648,109826,110615,119751,127846,131990,138495,141718,145700,146602,146685,147124,150007,172043,177263,179134}
{0,1348,7290,9987,12606,13130,15817,22158,30099,30741,37397,38311,59532,72507,82249,84112,84427,85130,92552,95084,95409,97456,101816,104606,106746,111065,112492,113485,116757,117245,118106,118496,124949,135786,136212,151069,157902,161266,167618,175037,179129}
{0,6109,7876,8417,9118,15800,15935,21154,26751,30028,34785,35328,38739,39685,42901,49852,56923,63140,67867,83832,92868,93990,95129,99411,100246,106167,106358,109043,109910,118188,118844,123839,128368,137816,154556,154889,158067,168585,173068,175219,175501}
Returns: 24

{5990,6985,17723,18784,20958,26433,27925,29068,34574,39404,39961,52385,61619,67571,69079,71683,76016,77748,79929,79942,83772,86008,90871,92029,92895,95040,99406,106093,109832,111714,114326,115461,118375,123873,124070,127204,130167,134872,135251,139682,141782,142837,151104,158085,160856,163874,170734,173038,173124,179615} {12605,13835,16403,18397,18568,19172,19645,23229,25607,31723,32089,32436,33012,42898,44695,55663,60634,64704,65858,66595,67057,67500,69060,69671,70288,75940,79076,79608,94714,114741,118019,123599,130401,131280,136012,138743,141284,142172,148411,149675,150070,152978,153206,157338,157356,159875,162145,163073,173452,174169} {6314,11673,18740,32338,36256,38728,39063,42030,45585,46830,52297,61046,61085,66019,72246,73199,73617,85000,91849,97412,97723,100716,100927,102447,103616,116332,120475,123782,139454,143663,144075,150883,151120,152183,153475,153661,154452,157076,159166,161365,165992,171242,171868,172309,172784,175837,175902,178248,178859} {7540,13808,17898,19074,19394,27970,40304,48853,49506,50631,52266,52473,54344,55260,59663,60235,62136,63861,67360,67520,67660,72177,74169,77411,83827,88394,89716,93588,98557,104525,106318,110903,116276,118109,119318,119392,122442,122623,125319,129273,137152,137260,141872,147669,148620,151715,154407,163392,163960,168826} {1307,3302,3646,6741,10217,24069,25045,25617,36166,38588,40843,49777,51433,51524,63389,65744,69457,70002,71456,73600,74296,74620,75943,78866,82864,83867,85497,85517,90879,94100,95914,105759,108018,110401,112565,114407,115743,116012,119734,126263,135184,137207,144413,145286,146748,147420,150406,151795,154445,170406}

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

Coding Area

Language: C++17 · define a public class Boxing with a public method int maxCredit(vector<int> a, vector<int> b, vector<int> c, vector<int> d, vector<int> e) · 24 test cases · 2 s / 256 MB per case