Statistics

Problem Statement for "AlmostBipartiteMatching"

Problem Statement

The maximum matching of a graph is the largest possible set of edges in which no two edges share a common vertex.

Bipartite graphs are graphs whose nodes can be divided into two sets A and B such that each edge in the graph has one endpoint in A and one endpoint in B. In these graphs, the maximum matching problem can be perfectly solved in polynomial time using maximum flow algorithms.

In this problem you will be given a graph that is almost bipartite and you will have to calculate the maximum matching of that graph. An almost bipartite graph is a graph whose nodes can be divided into two sets A = {a0,...,anA-1} and B = {b0,...,bnB-1} such that all edges have one endpoint in A and one endpoint in B with the exception of the edges from ai to ai+1 that exist for every i between 0 and nA-2, inclusive, and the edges from bi to bi+1 that allways exist for every i between 0 and nB-2, inclusive.

You will be given nA and nB as two ints. The set of edges that have one endpoint in A and one endpoint in B is given as two int[]s edgesA and edgesB. The ith edge has one endpoint aedgesA[ i ] and one endpoint bedgesB[ i ]. Since they are always part of the graph, edges with two endpoints in the same set are implicit. Return the size of the maximum set of edges in this graph that do not share a vertex.

Definition

Class:
AlmostBipartiteMatching
Method:
maxMatching
Parameters:
int, int, int[], int[]
Returns:
int
Method signature:
int maxMatching(int nA, int nB, int[] edgesA, int[] edgesB)
(be sure your method is public)

Constraints

  • nA and nB will each be between 1 and 1000, inclusive.
  • edgesA will contain between 0 and 50 elements, inclusive.
  • edgesA and edgesB will contain the same number of elements.
  • Each element of edgesA will be between 0 and nA-1, inclusive.
  • Each element of edgesB will be between 0 and nB-1, inclusive.

Examples

  1. 3

    3

    {0,1,2}

    {0,1,2}

    Returns: 3

    A perfect matching can be achieved by using all the edges with one endpoint in each set. There are other ways to get the same result.

  2. 3

    3

    {0,1}

    {1,2}

    Returns: 2

  3. 6

    6

    {0,0,2,3}

    {2,4,5,1}

    Returns: 6

  4. 13

    16

    {5,2,6,2,7,2,7,6,2,6,1,3,0,10,12,11,10}

    {7,3,10,12,0,0,3,4,7,2,5,2,14,15,1,1,1}

    Returns: 14

  5. 1

    1

    {0}

    {0}

    Returns: 1

  6. 2

    2

    {}

    {}

    Returns: 2

  7. 1

    1

    {}

    {}

    Returns: 0

  8. 2

    2

    {0,0,1,1}

    {0,1,0,1}

    Returns: 2

  9. 1000

    1000

    {}

    {}

    Returns: 1000

  10. 999

    999

    {}

    {}

    Returns: 998

  11. 642

    340

    {607,530,534,394,289,167,261,525,287,59,234,512,95,112,170,417,524,457,479,315,299,236,497,430,38,345,636,525,433,455,529,380,176,133,409,11,363,633,251,251,1,21,516,125,245,474,459,261,16,590}

    {70,221,183,289,132,259,7,209,234,105,150,21,12,63,311,168,20,108,211,274,286,307,19,68,59,205,137,322,162,226,291,163,302,161,46,95,205,98,324,315,14,85,293,176,276,41,216,28,198,167}

    Returns: 491

  12. 246

    830

    {138,157,197,101,189,145,90,45,142,184,201,108,28}

    {630,8,582,82,379,560,66,36,631,32,769,611,498}

    Returns: 538

  13. 964

    400

    {343,435,146,304,210,25,264,470,87,961,820,417,652,900,45,336,271,796,260,670,718,539,620,56,822,58,63,855}

    {281,303,224,261,324,100,43,377,210,236,114,197,312,100,397,283,368,117,252,263,31,40,133,120,318,70,233,59}

    Returns: 682

  14. 834

    482

    {377,144,201,500,572,698,657,502,755,107,178,13,766,264,290,658,71,461,463,482,377,191}

    {287,223,158,117,281,40,23,400,168,450,303,422,448,255,38,276,460,367,134,417,47,71}

    Returns: 658

  15. 420

    518

    {407,307,78,61,11,239,413,259,236,364,94,148,279,183,328,182,281,129,288,65,240,311,98,132,263,188,13,419,129,416,181,221,412}

    {164,356,147,206,72,324,249,516,10,99,368,299,458,125,483,279,272,63,171,56,175,60,120,367,87,407,362,385,349,309,293,288,475}

    Returns: 469

  16. 558

    260

    {90,203,77,301,349,413,339,291,536,525,38,548,377,2,111,274,277,284,357,318,5,494,133,83,258,376,275,263,115,292,84,291,358,420,495,284,425,369,237,297,543,176,214,35,545,181,414,268,263,246}

    {38,7,182,5,129,159,240,243,234,30,9,65,110,10,183,106,67,241,53,85,59,37,71,193,235,62,34,165,153,83,127,71,128,115,229,178,141,161,141,148,13,232,210,224,121,179,168,217,158,46}

    Returns: 409

  17. 952

    548

    {301,739,643,222,588,747,381,59,563,847,630,79,857,210,900,346,64,680,355,198,364,247,0,890,396,646,626,71,698,486,688,41,482,150,695}

    {210,22,391,422,245,246,441,500,203,160,249,188,425,508,325,287,246,412,264,432,98,37,307,460,503,5,522,302,492,414,395,296,70,252,187}

    Returns: 750

  18. 748

    530

    {319}

    {220}

    Returns: 639

  19. 136

    946

    {56,107,80,71,40,123,44,92,131,113,15,34,107,108,10,103,72,60,9,117,128,5,117,101,130}

    {545,864,547,890,4,429,523,823,833,25,326,374,99,77,136,106,564,598,128,838,544,933,862,91,162}

    Returns: 541

  20. 668

    580

    {154,155,454,115,367,133,258,377,466,265,572,202,619,35,428,150,177,448,629,91,173,549,504,600,547,652,21,656,181,141,453,535,370,651,50,522,453,514,199}

    {325,109,239,161,144,34,459,130,83,554,55,115,102,440,216,105,116,133,315,443,407,482,533,92,546,52,194,565,44,298,562,212,392,142,389,43,539,176,541}

    Returns: 624

  21. 441

    544

    {61,332,265,191,209,216,385,74,146,19,191,9,279,203,180,272,59,7,193,355,360,260,116,406,156,330,439,302,249,138,113,270,348,248,186,304,248,359,95,193,274,194,66,62,91,283,421,148,107,69}

    {399,78,206,248,208,130,216,113,465,405,168,48,451,172,437,365,125,35,251,118,420,496,259,468,322,27,55,40,137,298,111,423,494,215,105,290,441,376,74,161,337,407,382,388,39,154,512,353,468,152}

    Returns: 492

  22. 997

    328

    {599,878,616,171,680,503,820,848,726,791,978,284,520,628,178,924,36,854,235,813,787,570,766,876,869,656,304,702,335,315,511,621}

    {205,269,228,216,111,121,218,283,47,60,319,270,46,215,155,299,202,224,186,165,309,127,29,201,223,130,133,308,50,172,43,142}

    Returns: 662

  23. 611

    76

    {153,128,129,308,472,404,523,304,578,352,150,424,165,401,492,581,258,314,122,101,591,243,335,318,0,253,334,223,98,216,419,48,308,370,68,519,464,306,586,586,123,376,499,178,474,143,282,473,50}

    {55,29,35,75,17,49,26,34,44,9,9,59,55,35,46,42,6,47,55,18,54,69,29,39,70,46,21,35,5,73,38,36,14,75,65,28,62,60,20,65,11,58,45,6,43,71,0,31,68}

    Returns: 343

  24. 917

    470

    {495,427,587,236}

    {398,215,383,150}

    Returns: 693

  25. 79

    194

    {70,34,63,29,10,59,25,3,63,3,47,19,21,69,49,31,24,21,32}

    {29,145,98,189,93,162,85,85,99,143,91,82,80,115,148,115,28,42,178}

    Returns: 136

  26. 755

    126

    {620,6,503,590,201,169,555,49,293,189,750,569,477,50,326,427,277,261,33,167,423,363,382,748,255,7,181,422,254,237,142,126,451,400,220,487,278,691,496,700,378,21,312,519,741,137,634,3,186,748}

    {113,70,117,4,26,100,83,33,69,17,56,81,120,87,59,46,104,4,93,120,93,19,17,79,96,75,36,53,104,70,99,8,84,35,80,47,26,74,86,97,61,37,51,69,25,78,103,105,9,96}

    Returns: 440

  27. 37

    588

    {22,15,12,35,3,35,0,15,18,21,0,8,0,31,20,0,34,13,28,26,26,35,4,15,21,10,35,22,5,16,2,22,28,21,16,4,35,3,29}

    {554,461,491,585,542,460,102,553,239,199,67,148,125,203,342,499,440,299,407,25,281,123,69,128,186,12,104,22,563,371,72,119,80,461,479,14,222,551,62}

    Returns: 312

  28. 817

    986

    {223,321,418,674,402,680,80}

    {33,781,723,972,368,743,329}

    Returns: 901

  29. 497

    610

    {16,26,73,33,50,209,260,451,61,305,236,186,481,350,393,147,139,354,405,107,418,22,38,62,363,415,50,496,450,339,482,40,402,228,391,96,104,314,395,312,29,154,300,384,117}

    {356,511,433,267,8,372,529,257,279,400,160,450,6,566,113,562,299,390,379,522,558,70,336,261,569,34,158,326,453,583,215,244,81,202,568,547,391,125,163,543,42,100,168,222,330}

    Returns: 553

  30. 661

    926

    {184,108,280,568,634,550,280,230,381,417,242,29,108,652,494,400,433,525,384,461,166,205,376,90,285,477,636,553,411,198,638,132,273,148,571,195,333,621,451,363,98,160,349,87,226}

    {564,32,244,489,912,630,502,907,413,879,11,854,873,474,913,867,387,148,27,427,854,761,580,444,513,671,778,492,630,476,585,411,421,437,757,256,236,227,572,864,164,607,790,219,337}

    Returns: 793

  31. 128

    477

    {62,36,31,31,1,14,85,20,104,112,17,127,100,37,126,84,41,5,25,29,47,120,32,92,61,108,27,39,90,88,88,23,97,54,112,75,105,17,69,113,86,115,122,54,84,112,2,91,89,45}

    {179,174,91,337,50,18,423,444,239,42,371,59,474,189,390,23,372,46,89,359,390,58,275,311,213,277,440,122,432,39,293,309,307,94,410,57,473,78,124,344,178,460,450,337,440,153,371,440,120,157}

    Returns: 302

  32. 838

    335

    {591,274,745,480,248,130,644,435,554,309,666,113,401,698,561,316,503,542,742,205,689,140,777,572,375}

    {19,135,28,64,213,232,104,191,182,156,62,184,209,55,186,167,110,177,63,178,138,124,328,19,230}

    Returns: 586

  33. 370

    461

    {290,315}

    {185,455}

    Returns: 415

  34. 616

    507

    {583,186,214,88,74,143,208,550,209,424,26,123,12,338,226,15,484,383,387,63,481,233,339}

    {45,321,367,249,95,27,374,211,128,255,292,271,269,149,370,134,12,330,7,291,236,43,68}

    Returns: 561

  35. 522

    51

    {133,466,489,498,472,316,110,306,84,391,199,302,506,427,402,105,282,206,15,332,73,114,247,299,433,42,74,379,444,451}

    {29,3,32,40,11,46,43,34,18,27,36,27,31,42,44,28,10,43,48,43,9,47,50,31,13,6,48,24,24,17}

    Returns: 286

  36. 998

    833

    {754,946,713,740,758,771,508,291,788,387,646,94,829,555,803,234,801,118,502,692,857,852,311,619,596,277,947,949,954,638,72,829,986,863,514,916,791,464,211,720,434,288,467,388,12,569,572,384,155,29}

    {262,616,495,101,810,261,153,785,802,360,604,756,116,161,715,4,212,406,457,262,332,447,144,360,718,218,153,685,308,422,57,551,815,96,626,729,136,74,134,703,541,145,459,668,657,68,240,224,806,353}

    Returns: 915

  37. 896

    903

    {173,887,85,485,79,545,115,351,137,880,690,364,494,882,521,604,25,634,371,457,424,39,505,655,585,598,164,472,43,313,782,660}

    {211,236,529,5,137,843,219,796,64,853,107,901,399,196,751,895,55,126,267,442,743,800,777,142,192,525,775,379,744,126,327,44}

    Returns: 899

  38. 418

    999

    {79,200,108,29,387,254,117,107,357,46,151,401,197,89,141,368,359,414,177,362,274,11,21,33,326,306,329,359,327,26,99,130,403,39}

    {328,278,440,399,424,15,514,285,445,30,356,547,620,782,83,684,795,63,363,726,22,660,834,742,708,497,622,501,543,719,268,112,124,305}

    Returns: 708

  39. 474

    767

    {144,109,189,11}

    {25,600,498,682}

    Returns: 620

  40. 148

    81

    {20,31,128,135,140,45,0,43,114,2,62,16,74,118,32,86,2,117,61,62,115,147,39,111,107,120,17,140,97,114,26,140,81,65,50,32,93}

    {52,60,48,38,13,27,18,24,3,79,35,31,11,56,55,0,26,17,79,51,23,3,21,56,55,42,61,11,42,1,5,54,2,38,63,36,23}

    Returns: 114

  41. 307

    81

    {188,51,187,302,127,172,83,98,147,139,121,52,197,279,236,30,34,194,305,76,149,70,163,52,133,205,148,212,76,132,185,164,216,45,299,35,214,107,262,55,16,88,211,250,246,104,237,15,15,243}

    {7,14,9,29,38,11,29,19,59,68,15,47,15,43,75,55,55,79,67,11,39,57,13,27,9,25,19,1,79,31,47,35,57,26,58,45,67,79,65,36,37,69,38,49,29,75,60,30,69,53}

    Returns: 193

  42. 565

    703

    {79,253,69,136,365,35,327,307,421,21,237,407,183,226,79,245,170,459,424,156,513,271}

    {14,121,581,373,547,149,463,3,611,116,53,63,118,103,273,68,371,409,365,159,525,170}

    Returns: 633

  43. 235

    689

    {167,91,228,177,232,207}

    {39,247,101,570,667,262}

    Returns: 461

  44. 409

    857

    {289,1,210,157,379,115,84,116,288,0,396,245,256,52,352,255}

    {665,279,165,106,278,131,353,611,71,729,565,234,675,677,627,272}

    Returns: 632

  45. 227

    901

    {20,146,202,31,170,141,121,152,182,149,225,21}

    {361,31,167,595,505,861,208,131,855,351,529,264}

    Returns: 563

  46. 299

    727

    {127,183,60,251,125,269,109,235,289,131,19,18,45,298,200,67,83,46,139,94,38,15,279,232,46,7,133,51,24,13,25,163,252,266,17,139,276,188,37,7,267,177,250,62,176,265,149,231,119,53}

    {500,148,279,95,0,361,75,515,676,11,534,607,210,601,185,459,681,183,705,27,301,361,135,267,605,375,255,334,561,131,163,561,431,369,391,13,561,329,288,73,704,540,203,1,39,179,137,145,499,248}

    Returns: 512

  47. 367

    953

    {343,246,5,269,345,321,143,74,297,60,294,347,273,151,285,79,356,321,148,157,14,202,47,119,33,201,35,212,5,181,366,58,286,183,230,109,266,346}

    {101,695,294,942,663,91,141,445,843,9,765,642,793,705,38,397,549,665,295,730,841,91,294,430,487,76,773,885,652,780,145,875,761,131,577,796,167,869}

    Returns: 659

  48. 945

    959

    {549,752,790,67,674,815,470,8,776,289,833,714,427,285,525,168,887,345,772,367,770,934,537,559,664,838,879,158,556,206,695,635,386,843,272,626,7,241,737,421,594,594,780,203}

    {839,57,735,895,265,256,91,683,553,33,540,347,275,762,747,483,417,725,749,258,591,101,564,922,5,957,257,507,83,295,368,343,45,514,529,77,115,804,147,798,299,903,467,570}

    Returns: 951

  49. 811

    631

    {144,154,243,642,543,452,43,188,169}

    {575,49,438,609,559,275,29,547,169}

    Returns: 720

  50. 363

    723

    {73,281,47,104,224,17,154,128,307,58}

    {133,374,224,59,109,625,17,455,166,525}

    Returns: 542

  51. 463

    49

    {21,422,261,371,269,265,245,341,239,409,215,59,113,125,21,19,230,73,323,255,323,83,457,223,260,333,299,375,387,113,276,66,141,415,234,423,202,28,35,97,137,255,99,87,124,141,166,161,27,345}

    {23,37,19,13,31,47,43,22,22,37,18,38,28,16,16,30,47,0,34,8,2,22,34,47,43,12,1,16,27,38,15,25,22,46,5,48,41,17,37,23,47,24,9,25,3,38,9,2,19,11}

    Returns: 255

  52. 495

    957

    {137,83,441,340,9,153,460,14,151,434,227,455,494,12,22,28,293,127,147,351,24,345,153,319,75,49,449,101,154,436,283,377,461,347,255,32,429,133,401,481,336,375,471,117,295,129}

    {585,617,832,555,767,28,173,305,845,535,783,641,47,845,545,127,6,345,420,835,305,546,40,338,760,110,684,37,11,517,526,549,465,734,389,639,526,278,797,730,249,302,622,956,490,385}

    Returns: 725

  53. 949

    17

    {169,835,191,514,443,669,61,16,116,787,309,407}

    {14,7,9,3,4,4,9,11,13,11,4,9}

    Returns: 482

  54. 167

    741

    {165,61,55}

    {493,117,384}

    Returns: 453

  55. 525

    697

    {26,264,357,306}

    {157,555,256,245}

    Returns: 610

  56. 499

    429

    {104,303,120,466,301,213,141,13,21,388,359,251,123,437,177,225,119,405,51,478,453,79,229,95,355,89,65,358,143,287,420,173,393,235,326,449,439,311,117,449,451,268,163,335,91,351,386,287,379,363}

    {91,18,213,83,67,158,168,409,159,327,144,102,256,33,286,400,135,181,346,43,179,25,406,176,391,9,78,321,45,225,11,395,424,154,35,268,265,226,62,16,16,137,93,218,174,202,421,258,300,86}

    Returns: 463

  57. 723

    127

    {305,422,649,147,426,636,203,715,695,442,165,657,371,631,4,210,120,336,601,58,537,186}

    {75,15,55,59,39,89,14,60,39,27,68,25,41,111,103,125,49,95,48,7,104,89}

    Returns: 424

  58. 401

    43

    {393,6,211,324,253,387,60,105,203,303,91,269,246,331,12,140,263,13,73,181,371,103,224,350,107,73,153,275,269,80,221,248,177,335,371}

    {31,41,3,25,31,20,19,19,9,40,23,17,21,15,33,27,35,12,33,24,41,31,9,9,28,21,10,2,36,35,33,25,36,29,30}

    Returns: 221

  59. 147

    287

    {17,146,51,129,38,90,35,34,141,88,114,140,43,45,26,102,56,105,60,137,59,119,51,3,65}

    {98,89,237,268,93,275,13,147,173,137,89,121,20,174,37,137,161,224,177,210,195,261,37,270,119}

    Returns: 216

  60. 811

    659

    {655,467,165,370,715,449,706,615,487,113}

    {503,567,247,139,102,256,11,574,128,469}

    Returns: 734

  61. 999

    999

    {998}

    {404}

    Returns: 999

  62. 951

    329

    {187,646,512,92,383,653,257,724,759,310,270,592,596,357,818,868,193,574,420,147,944,133,894,190,249,15,111,750,311,629,593,266,816,580,417,859,599,184,706,791,443,845,892,709,206,909,74,585,221,817}

    {19,141,44,136,307,125,86,4,324,210,98,81,29,281,131,125,239,240,286,51,65,93,91,57,190,155,304,76,58,267,320,107,269,296,267,19,12,84,247,164,314,171,250,121,303,232,225,157,288,106}

    Returns: 640

  63. 493

    13

    {104,491,266,282,276,39,59,155,62,377,285,224,16,486,173,112,201,136,70,139,363,80,129,465}

    {10,10,3,12,11,11,0,8,10,11,12,5,9,10,11,12,6,12,7,1,11,3,6,0}

    Returns: 253

  64. 471

    935

    {49,83,67,219,281,157,376,213,294,79,424,418,187,390,297,30,307,207,203,143,209,335,269,315,175,53,284,408,238,186,441,284,11,437,213}

    {217,534,366,480,327,830,221,220,132,44,807,850,631,31,677,139,232,410,752,52,654,230,609,92,579,601,92,773,195,541,677,151,57,522,256}

    Returns: 703

  65. 767

    721

    {741,414,147,459,442,132,314,628,716,136}

    {52,309,213,399,533,312,380,484,174,666}

    Returns: 744

  66. 343

    109

    {179,321,147,148,35,321}

    {70,79,24,71,83,107}

    Returns: 225

  67. 573

    135

    {499,239,196,571,60,266,394,110,51,397,264,159,172,125,464,196,554,317,281,387,382,553,131,365,519,124,206,536,77,23,44,133,74,115,231,154,42,216,58,189,315,247,465,109,469,402,273,192,352,260}

    {96,77,15,22,134,46,79,119,118,125,101,82,70,99,17,124,20,19,41,33,85,91,120,129,22,122,31,124,95,90,66,10,3,29,9,76,104,35,76,57,110,100,113,54,113,34,6,15,129,65}

    Returns: 354

  68. 615

    691

    {34,29,426,197,352,42,88,442,62,146,418,588}

    {325,407,229,624,256,290,317,146,660,68,460,273}

    Returns: 653

  69. 93

    19

    {2,47,77,84,66,24,43,89,71}

    {14,4,16,15,10,6,5,7,18}

    Returns: 56

  70. 679

    795

    {269,414,367,277,250,26,119,484,498,392,664,90,646,353,311,669,403,534,278,150,179,412,483,23,594,66,150,636,77,610,457,516,358,113,80,228,474,611,437,379,591,94,248,237,298,66,144}

    {790,437,528,417,600,769,436,559,558,589,687,31,543,229,679,181,371,363,425,112,298,69,479,645,695,221,778,125,281,501,422,534,407,236,61,584,27,581,33,593,125,150,30,485,629,317,783}

    Returns: 737

  71. 213

    817

    {75,88,47,149,148,103,87,197,22,137,132,38,95,149,181,179,90,114,86,176,207,187,34,125,5,128,211,143,146,182,90,171,0,34,120,160,127,33,39,26,169,41,145,110,209,100,72}

    {26,671,11,333,504,306,577,637,460,228,461,770,792,496,737,82,621,555,519,750,639,555,471,611,389,712,27,625,340,755,616,785,791,30,344,518,562,214,227,577,677,176,628,753,558,751,660}

    Returns: 515

  72. 79

    311

    {0,20,67,20,26,60,39,69,44,63,69,53,74,7,31,2,75,8,52,6,32,65,63,2,71,65,71,26,62,52,2,48,1,67,50,15,46,6,59,14,69,33,75,47,66,31,4,25,18,38}

    {67,284,283,260,297,78,48,208,221,227,184,57,300,237,81,57,31,62,253,162,30,265,167,231,170,110,74,25,257,200,125,119,219,65,224,126,46,176,291,263,117,267,54,124,302,264,176,86,211,131}

    Returns: 195

  73. 459

    181

    {453,387,166,290,410,155,216,237,386,2,216,451,239,388,171,301,6,120,208,88,226,388,434,173,376,189,396,124,349,82,95,447,264,451,433,284,226,443,353,68,43,157,197,77}

    {35,94,175,95,166,139,164,30,24,76,91,27,99,114,26,107,161,16,2,33,52,140,50,139,130,165,141,118,103,9,10,7,79,126,139,155,90,70,28,13,31,116,28,121}

    Returns: 320

  74. 869

    735

    {45,251,660,178,730,766,807,525,277,38,355}

    {537,304,492,266,174,478,608,423,366,82,41}

    Returns: 802

  75. 777

    771

    {320,458,604,414,217,424,44,44,494,639,71,385,94,90,109,77,454,40,523,547,318,70,643,79,110,468,373,447,417,434,158,221}

    {278,202,703,51,149,618,15,376,37,330,701,467,318,339,708,276,757,670,550,268,226,517,331,489,451,415,34,15,673,227,49,577}

    Returns: 774

  76. 465

    873

    {302,456,405,147,233,103,162,164,132,349}

    {846,381,457,475,64,398,498,495,89,119}

    Returns: 669

  77. 419

    313

    {92}

    {38}

    Returns: 366

  78. 801

    575

    {172,698}

    {226,204}

    Returns: 688

  79. 621

    823

    {192,474,522}

    {208,48,476}

    Returns: 722

  80. 859

    95

    {744}

    {42}

    Returns: 477

  81. 243

    29

    {142,208}

    {26,2}

    Returns: 136

  82. 323

    145

    {296,144,82}

    {2,130,64}

    Returns: 234

  83. 1000

    1

    {}

    {}

    Returns: 500

  84. 1

    1000

    {}

    {}

    Returns: 500

  85. 1000

    1

    {252,697,69,604,128,574,741,44,389,663,355,306,611,144,478,1,393,178,344,803,350,363,319,392,475,565,671,653,263,456,863,288,70,956,990,473,892,638,342,924,281,563,597,686,847,169,193,826,670,38}

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    Returns: 500

  86. 1000

    1

    {571,262,723,530,841,928,495,825,315,418,501,947,417,243,453,514,89,542,362,160,858,566,518,624,553,885,117,109,877,349,956,244,942,646,944,270,436,165,942,296,103,577,171,767,351,662,292,952,990,110}

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    Returns: 500

  87. 1000

    1

    {249,37,465,378,774,360,87,140,794,232,251,89,772,406,406,510,354,219,517,265,238,640,294,442,965,405,359,700,812,787,950,49,130,682,401,921,497,627,86,977,996,591,642,529,111,473,134,467,789,427}

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    Returns: 500

  88. 999

    1

    {114,981,479,397,419,784,766,72,704,572,626,960,445,734,1,629,122,421,575,975,852,19,539,25,946,243,252,174,168,631,86,97,710,321,274,819,200,569,283,787,216,796,368,641,647,531,128,673,22,903}

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    Returns: 500

  89. 999

    1

    {784,937,648,387,965,185,112,318,688,515,294,832,762,114,46,54,296,769,971,836,715,63,835,52,408,136,944,968,9,310,883,728,851,196,927,138,344,937,830,157,317,217,550,42,914,463,592,790,0,729}

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    Returns: 500

  90. 999

    1

    {804,562,115,972,935,38,76,949,111,265,13,391,176,118,464,473,372,637,471,309,887,989,636,856,184,33,427,850,554,816,459,333,769,808,815,165,523,637,496,153,365,707,763,347,673,893,486,328,831,952}

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    Returns: 500

  91. 999

    1

    {}

    {}

    Returns: 499

  92. 1

    999

    {}

    {}

    Returns: 499

  93. 999

    1

    {531,817,687,311,879,863,399,361,243,789,35,379,33,263,311,989,945,247,339,899,527,9,51,981,381,579,533,575,109,1,559,425,703,23,1,863,71,843,543,641,687,627,983,19,177,837,311,605,557,885}

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    Returns: 499

  94. 999

    1

    {625,643,943,783,899,501,937,953,107,175,533,393,577,169,701,309,287,767,33,499,969,19,445,409,39,205,27,789,971,751,219,87,207,525,475,815,311,959,57,387,329,401,713,353,701,13,939,615,439,107}

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    Returns: 499

  95. 999

    1

    {325,621,141,509,709,859,343,71,223,983,63,27,317,9,791,289,111,281,651,901,241,869,91,663,845,917,145,697,781,977,897,481,627,927,523,51,143,615,121,589,901,363,981,193,799,613,619,455,199,365}

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    Returns: 499

  96. 1

    999

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    {660,915,256,503,741,812,661,748,931,870,59,62,357,665,506,825,779,486,361,416,480,625,638,274,141,298,135,283,237,244,57,286,401,99,616,442,261,140,688,258,670,46,498,261,158,288,662,798,814,191}

    Returns: 500

  97. 1

    999

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    {34,535,497,817,404,355,296,691,647,849,254,791,391,535,397,755,330,938,646,518,447,835,692,872,524,717,737,195,159,455,732,617,644,438,956,236,314,962,113,423,331,640,922,88,551,847,508,431,958,949}

    Returns: 500

  98. 1

    999

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    {954,594,54,659,620,37,792,294,333,791,727,177,68,340,705,953,1,384,876,149,457,10,88,157,665,278,119,874,510,93,12,703,833,302,489,502,534,506,182,715,874,84,872,533,232,50,169,598,952,343}

    Returns: 500

  99. 1

    1000

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    {637,757,675,845,98,238,394,62,364,214,853,119,312,71,155,478,192,809,328,698,203,38,526,629,38,277,214,68,941,344,364,542,153,832,464,252,421,330,925,919,491,196,986,654,445,998,639,672,618,456}

    Returns: 500

  100. 1

    1000

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    {34,78,241,320,188,320,25,150,387,195,780,852,973,991,470,255,407,436,536,355,785,431,979,637,636,451,304,375,319,365,719,852,829,268,456,324,998,529,342,605,785,75,272,149,225,638,94,244,743,438}

    Returns: 500

  101. 1

    1000

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    {637,99,831,810,654,790,281,734,185,554,847,429,371,617,563,84,340,458,344,64,703,909,41,788,613,36,750,331,224,279,123,730,884,102,471,152,194,619,644,663,131,272,313,220,963,881,498,461,665,164}

    Returns: 500

  102. 1

    999

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    {399,661,501,203,531,743,475,815,683,473,301,509,89,531,287,553,777,831,183,213,329,833,767,699,565,169,519,187,489,321,139,785,131,109,347,263,377,43,595,743,833,945,773,369,727,799,191,923,567,953}

    Returns: 499

  103. 1

    999

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    {73,891,383,335,353,947,501,867,625,177,111,263,245,907,547,381,205,885,175,137,805,849,297,691,319,65,303,687,145,653,7,323,683,913,17,29,11,959,477,357,907,953,465,831,863,903,973,481,593,317}

    Returns: 499

  104. 1

    999

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    {737,345,241,693,547,513,243,905,779,655,471,497,521,25,855,11,43,47,215,709,913,403,353,505,955,401,837,693,199,335,575,943,373,883,111,27,375,239,431,211,15,873,501,409,957,679,37,693,991,721}

    Returns: 499

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: