Statistics

Problem Statement for "Containers"

Problem Statement

There are several empty containers lined up in a row, and you want to put packages into them. You start with the first container and the first package. Do the following until all the packages are inside containers:

  1. If the current package cannot fit into the current container, skip to step 3. Otherwise, go to the next step.
  2. Put the current package into the current container. Grab the next package, and go back to step 1.
  3. Put the current container aside (you will not put any more packages into that container). Move on to the next container in line, and go back to step 1.
You are given a int[] containers, the i-th element of which is the capacity of the i-th container in line, and a int[] packages, the i-th element of which is the size of the i-th package. The constraints will guarantee that you will be able to put all the packages into containers using the above procedure. Return the sum of the wasted space in all the containers. The wasted space in a container is its capacity minus the total size of its contents.

Definition

Class:
Containers
Method:
wastedSpace
Parameters:
int[], int[]
Returns:
int
Method signature:
int wastedSpace(int[] containers, int[] packages)
(be sure your method is public)

Notes

  • A set of packages fits into a container if the total size of all the packages in the set does not exceed the capacity of the container.
  • You must use the containers and the packages in the order that they are given. You may not reorder them.

Constraints

  • containers will contain between 1 and 50 elements, inclusive.
  • Each element of containers will be between 1 and 1000, inclusive.
  • packages will contain between 1 and 50 elements, inclusive.
  • Each element of packages will be between 1 and 1000, inclusive.
  • It will be possible to put all the packages inside containers using the method described in the statement.

Examples

  1. { 5, 5, 5 }

    { 5, 5, 5 }

    Returns: 0

    Here, we've got 3 packages of size 5 and 3 containers of size 5, so no space will be wasted.

  2. { 5, 6, 7 }

    { 5, 5, 5 }

    Returns: 3

    All the packages are of size 5. We will put the first package into the container of size 5, the second package into the container of size 6 and the third into the container of size 7. The overall wasted space will be equal to (5 - 5) + (6 - 5) + (7 - 5) = 3.

  3. { 2, 3, 5 }

    { 3 }

    Returns: 7

    Here, we've got only one package of size 3. First, we'll try to put it into the container of size 2, but it won't fit, so we'll put it into the second container, leaving the third untouched. The overall wasted space will be 2 + (3 - 3) + 5 = 7.

  4. { 3, 4, 5, 6 }

    { 3, 3, 3, 3, 3 }

    Returns: 3

  5. { 1000 }

    { 1000 }

    Returns: 0

  6. {549,636,576,813,552,842,733,761,840,781}

    {357,260,294,60,164,217,286,293,302,212}

    Returns: 4638

  7. {948,950,934,699,574,673,822,990,718,813}

    {322,475,26,442,491,215,392,450,484,474}

    Returns: 4350

  8. {840,818,930,665,944,752,561,773,860,827}

    {100,129,479,426,327,178,178,472,489,392}

    Returns: 4800

  9. {632,837,795,574,665,620,816,834,926,817}

    {173,43,352,110,221,102,210,264,490,103}

    Returns: 5448

  10. {811,555,929,833,699,680,929,516,1000,514}

    {287,465,321,356,426,276,416,102,475,424}

    Returns: 3918

  11. {832,932,890,713,943,814,784,959,544,875}

    {272,466,201,206,255,419,115,74,315,198}

    Returns: 5765

  12. {624,682,814,721,521,513,730,727,527,572}

    {499,6,153,169,322,260,59,92,428,212}

    Returns: 4231

  13. {723,724,947,899,981,628,519,663,738,657}

    {420,441,292,434,345,100,373,377,175,117}

    Returns: 4405

  14. {877,684,798,873,671,862,811,972,710,708}

    {463,89,476,491,343,232,126,16,454,334}

    Returns: 4942

  15. {754,913,729,586,818,558,693,983,609,773}

    {499,230,443,473,116,135,121,262,238,211}

    Returns: 4688

  16. {817,812,541,681,701,517,778,537,789,865,957,742,785,719,742,785,447,588,779,464,714,425,521,490,710,730,553,911,964,898,494,780,646,635,997,947,688,710,484,476,574,977,818,959,696,495,679,743,619,994}

    {201,157,161,262,201,291,21,16,130,288,41,56,107,290,75,16,104,140,255,216,144,12,17,49,119,128,124,203,111,134,147,64,290,60,77,242,50,149,257,179,137,297,286,243,38,60,11,194,199,17}

    Returns: 28307

  17. {854,832,573,925,788,629,691,775,964,737,982,627,525,521,846,778,556,793,496,640,851,973,669,513,594,827,679,556,522,908,568,912,675,742,837,462,907,463,774,870,736,755,432,861,813,815,574,905,607,671}

    {57,156,75,298,281,163,276,218,65,147,52,232,230,32,178,138,204,22,154,93,18,35,184,64,198,217,220,221,133,287,150,242,142,225,291,174,139,266,91,256,164,195,187,93,278,116,283,181,189,136}

    Returns: 27557

  18. {833,438,685,801,428,799,581,770,487,930,718,445,695,596,519,810,517,903,436,762,550,961,636,767,967,952,630,954,506,710,922,939,748,542,675,712,942,856,481,428,722,735,409,416,867,465,763,985,968,799}

    {14,239,6,199,239,74,61,54,124,103,109,61,223,69,167,2,101,92,10,178,108,130,232,13,55,210,134,76,36,62,106,101,52,111,299,290,236,59,95,59,213,203,171,135,271,89,189,123,181,250}

    Returns: 28746

  19. {841,564,487,884,693,677,729,823,566,494,856,790,605,878,709,633,655,890,401,417,621,680,410,424,681,918,978,678,451,422,591,892,587,678,711,816,891,976,575,993,469,967,718,610,845,426,779,499,916,780}

    {234,144,107,175,38,197,139,73,175,225,39,102,114,293,211,287,103,204,207,201,262,107,48,136,189,100,42,153,46,109,107,279,5,265,205,94,161,43,166,35,19,205,136,133,249,98,171,103,54,77}

    Returns: 27509

  20. {682,711,772,603,478,943,968,873,892,768,519,556,557,838,818,947,588,691,524,886,455,607,551,836,421,908,848,815,572,444,562,854,691,871,993,769,749,961,578,576,664,633,732,758,470,549,640,594,841,764}

    {182,105,165,256,89,43,31,171,39,260,6,164,191,207,223,225,62,157,160,159,118,145,111,264,107,222,261,2,285,20,173,219,176,89,174,264,132,256,187,222,215,192,137,106,151,59,30,264,215,241}

    Returns: 27388

  21. {767,995,666,603,834,548,445,758,605,481,458,490,405,590,883,560,861,538,660,518,535,406,871,910,660,407,866,878,506,754,419,873,748,685,475,581,769,520,875,975,537,933,400,543,458,819,639,856,957,835}

    {83,132,132,285,30,99,89,286,95,156,209,31,148,216,104,123,21,119,158,186,79,238,232,156,280,36,189,210,160,11,283,242,194,167,279,223,265,67,208,60,275,169,142,122,84,297,245,156,116,154}

    Returns: 25314

  22. {699,843,934,464,612,854,824,737,412,438,882,406,562,991,777,466,500,583,822,949,840,405,890,966,890,799,644,486,602,718,451,901,561,921,965,709,775,724,445,723,698,863,729,861,853,441,863,889,561,684}

    {150,198,233,247,46,89,180,243,240,268,6,245,148,15,145,105,125,114,120,27,165,106,281,282,55,282,277,245,202,168,196,103,66,180,49,163,268,228,105,260,247,163,256,95,177,100,251,53,265,70}

    Returns: 27310

  23. {508,936,491,430,615,911,805,1000,529,404,882,968,978,700,430,550,419,481,720,758,605,490,832,725,961,738,891,704,723,747,836,831,618,928,861,833,774,601,769,839,542,650,806,519,950,773,605,905,790,926}

    {4,117,67,60,206,87,45,95,57,30,1,96,146,35,114,73,284,165,144,71,244,261,268,248,278,40,55,242,149,37,134,205,205,200,16,110,286,60,257,42,141,257,190,38,43,55,110,26,219,6}

    Returns: 29968

  24. {851,653,883,620,994,870,875,506,462,971,945,515,728,649,648,514,672,627,605,777,822,785,646,466,758,498,496,919,829,751,806,616,403,689,836,997,494,647,438,492,617,919,608,881,567,792,931,839,418,535}

    {268,275,225,52,16,240,179,112,116,84,178,298,136,158,145,2,299,38,126,159,116,4,22,263,192,144,131,54,86,57,52,53,84,276,105,99,215,283,210,83,66,139,80,253,48,276,7,46,13,132}

    Returns: 28165

  25. {532,945,783,648,710,518,995,867,849,516,442,651,789,994,845,732,722,589,507,990,938,478,945,496,863,464,690,831,871,949,629,403,894,948,587,539,466,582,406,851,698,985,437,422,914,883,691,571,407,798}

    {210,239,8,76,29,226,289,94,150,299,171,258,265,128,252,208,227,25,22,101,282,289,55,121,17,276,223,211,210,202,253,172,192,261,247,220,186,287,13,88,285,236,97,2,63,100,209,289,177,230}

    Returns: 26490

  26. {508,691,645,489,670,456,920,468,559,986,809,931,547,494,578,686,755,436,930,554,999,484,503,502,554,968,759,662,952,443,990,459,734,570,485,404,563,404,408,658,926,753,588,408,847,767,630,538,803,559}

    {196,80,74,212,217,149,42,153,133,161,266,149,121,235,135,275,234,210,102,185,37,113,290,64,125,139,4,242,5,146,292,252,277,117,215,245,266,257,98,150,117,115,50,237,49,184,263,35,145,117}

    Returns: 24457

  27. {543,636,775,563,609,787,430,948,429,434,489,768,731,839,749,693,964,400,826,493,584,608,736,690,506,761,823,671,573,547,978,653,719,688,816,928,474,782,876,504,817,901,808,547,675,556,776,574,493,602}

    {153,239,19,38,164,204,272,273,104,291,278,120,229,267,64,179,201,113,278,238,259,284,172,194,200,135,86,241,269,201,62,121,140,80,159,3,35,182,27,191,172,56,10,153,23,74,31,275,238,60}

    Returns: 25915

  28. {937,682,692,703,799,786,616,471,592,768,774,536,587,753,762,881,634,776,874,842,848,611,793,891,410,872,529,623,405,501,904,878,719,595,580,517,917,733,525,445,500,835,517,623,587,880,503,757,655,913}

    {80,188,224,90,300,251,173,238,9,283,164,126,55,38,90,14,155,48,293,250,293,12,27,38,141,277,209,288,103,241,140,182,180,115,23,179,65,196,168,73,230,32,198,36,69,287,101,223,87,145}

    Returns: 27104

  29. {952,512,711,714,791,437,600,885,803,907,569,481,683,892,820,988,543,565,426,788,603,742,464,711,611,555,545,816,578,432,959,465,545,669,715,936,642,915,757,982,757,926,999,977,818,819,964,897,920,926}

    {13,43,78,89,170,234,36,36,139,206,287,293,300,69,2,201,71,8,132,148,101,197,44,120,132,187,180,104,207,45,216,272,140,45,112,9,278,147,44,169,53,83,161,52,203,162,4,273,221,136}

    Returns: 30060

  30. {558,980,712,676,867,437,610,507,662,914,668,812,837,951,564,981,465,666,900,431,998,645,944,789,409,883,974,851,722,400,813,816,981,524,491,847,561,638,890,759,487,557,570,924,507,670,840,509,937,675}

    {86,4,151,135,142,99,86,193,50,62,216,189,262,260,58,128,300,194,148,216,98,84,103,39,51,154,7,16,24,85,22,161,89,172,47,282,270,132,174,71,246,89,259,207,101,69,34,152,14,234}

    Returns: 29344

  31. {546,941,872,997,492,867,954,851,700,419,544,745,497,644,774,594,402,604,464,865,687,430,832,898,780,819,634,404,672,593,741,819,470,548,815,562,951,704,412,651,659,493,932,756,737,642,950,740,846,413}

    {21,98,251,251,31,196,33,31,175,267,45,87,71,221,120,148,297,271,103,85,9,207,216,255,72,282,31,96,213,258,58,234,108,60,184,138,256,217,168,130,235,212,269,57,132,140,256,181,110,58}

    Returns: 26718

  32. {405,406,514,945,536,871,492,972,576,981,524,831,408,810,466,407,461,934,733,786,500,456,839,708,532,564,977,775,787,657,824,792,599,874,672,735,744,764,642,920,744,766,751,688,576,753,632,573,686,965}

    {128,138,12,67,97,67,241,194,78,243,101,197,13,230,280,66,131,148,83,290,198,226,261,290,282,254,132,32,54,83,44,234,220,107,52,68,173,292,262,2,286,114,199,298,44,230,63,226,77,197}

    Returns: 26749

  33. {837,663,725,785,647,612,845,447,730,477,405,749,669,814,725,594,523,727,416,840,592,995,692,618,447,814,742,655,403,644,782,776,843,506,560,490,654,404,473,985,418,479,733,687,829,995,818,952,721,770}

    {252,171,240,149,187,38,89,79,251,6,152,60,139,251,290,250,168,128,294,282,204,75,180,209,178,29,54,3,1,263,245,4,134,236,152,72,273,292,150,223,49,54,282,239,4,24,189,223,203,182}

    Returns: 25805

  34. {661,719,536,607,989,962,917,589,541,578,445,426,567,815,676,511,651,673,824,833,546,909,402,675,476,940,503,825,734,949,822,995,667,894,537,592,856,454,717,933,632,762,959,736,513,634,847,764,843,607}

    {218,76,269,14,227,172,217,152,264,42,32,288,71,16,72,38,170,40,169,247,247,268,210,141,285,243,205,175,117,111,230,87,187,250,152,165,174,69,16,189,110,47,228,232,115,299,22,36,38,190}

    Returns: 27611

  35. {602,877,747,535,570,515,517,497,603,927,804,897,805,434,706,882,865,514,968,934,875,796,655,817,899,703,964,812,733,977,589,935,854,937,405,960,988,522,457,526,986,861,423,790,831,729,607,695,779,574}

    {15,284,58,277,178,66,53,19,95,217,2,65,114,20,244,7,265,68,84,42,10,19,165,53,146,220,198,15,123,18,48,138,53,157,166,231,222,219,1,68,187,2,132,300,21,128,58,286,195,194}

    Returns: 30932

  36. {831,676,641,551,907,929,696,755,668,565,945,727,917,573,776,423,568,804,489,473,929,788,622,921,519,775,509,860,572,804,895,402,480,471,489,987,1000,721,678,604,822,622,931,738,731,707,697,900,446,723}

    {233,355,307,344,263,243,337,375,269,329,242,169,59,233,193,171,38,215,215,166,175,289,7,168,185,5,124,12,116,349,321}

    Returns: 28750

  37. {657,533,925,723,965,490,628,841,451,642,456,844,594,753,771,571,435,633,870,868,636,991,986,505,785,770,681,876,454,903,690,647,972,550,970,936,576,534,712,627,712,769,406,842,521,777,412,492,947,819}

    {88,393,97,269,207,176,54,144,170,307,381,133,108,74,275,105,235,390,233,88,299,21,177,169,327,383,146,25,199,43,178}

    Returns: 29254

  38. {646,903,462,526,461,591,712,901,596,953,642,826,839,892,670,567,477,625,966,911,744,475,512,934,426,771,772,863,457,492,516,703,995,579,829,992,770,540,892,902,428,469,728,804,962,934,971,975,558,937}

    {155,4,254,49,397,117,325,87,356,351,219,372,166,337,214,86,247,361,164,44,181,164,12,256,288,321,364,144,309,47,13}

    Returns: 29692

  39. {744,805,461,676,576,972,915,655,744,610,826,632,608,863,636,971,955,946,810,874,556,677,862,431,884,748,903,460,607,805,510,952,609,507,563,721,478,478,912,758,624,673,926,833,535,497,739,489,442,548}

    {284,221,110,326,99,318,192,292,222,366,84,138,107,324,224,311,66,148,5,290,313,339,368,194,279,234,54,214,88,203,354}

    Returns: 28239

  40. {920,765,893,616,995,472,660,1000,713,848,809,1000,986,763,857,623,438,728,939,626,957,815,486,984,586,417,571,569,438,801,701,959,502,529,574,496,537,771,431,787,618,776,786,539,539,643,763,577,971,637}

    {339,19,272,87,289,322,69,164,184,137,289,352,176,341,183,15,18,251,292,362,72,77,306,135,324,76,216,48,233,110,101}

    Returns: 29552

  41. {559,703,872,920,485,445,698,438,725,451,728,640,826,520,685,647,945,867,903,800,771,648,968,524,597,674,994,844,494,833,664,653,535,536,508,556,517,807,594,778,858,922,418,619,978,703,803,922,505,705}

    {290,115,217,340,92,119,18,285,68,328,187,118,361,168,43,155,116,164,179,146,218,169,147,155,253,10,110,44,106,333,185}

    Returns: 29546

  42. {532,478,978,757,413,463,656,943,930,649,639,996,831,471,533,521,995,724,617,512,693,443,487,616,488,439,778,936,850,981,423,982,458,401,739,472,400,931,951,930,580,589,861,410,596,930,531,591,654,685}

    {280,254,1,119,94,352,319,90,298,177,371,76,28,249,159,69,169,313,317,63,156,394,22,159,116,260,362,39,46,82,340}

    Returns: 27689

  43. {488,977,816,814,475,567,515,952,854,666,745,499,734,597,747,477,520,931,751,931,980,540,930,890,876,524,730,743,911,759,831,935,735,646,685,746,813,736,698,602,938,979,702,607,511,448,620,632,915,907}

    {314,364,111,262,323,33,117,243,40,370,244,291,148,85,32,224,305,368,117,147,394,51,381,139,357,358,113,209,248,228,17}

    Returns: 29992

  44. {750,531,414,777,851,873,865,836,473,862,579,978,730,594,528,883,892,427,643,886,464,404,795,868,910,816,590,434,403,892,465,754,422,479,466,873,952,931,708,962,793,823,875,522,954,402,942,845,966,584}

    {252,326,372,22,353,332,101,92,52,379,11,188,322,121,52,239,248,378,197,282,7,119,19,381,152,390,26,70,4,367,37}

    Returns: 29775

  45. {683,551,475,744,921,445,556,880,449,973,731,455,541,539,476,713,821,985,816,681,855,710,965,535,663,537,754,493,554,875,444,774,962,455,517,882,501,610,762,550,582,428,541,659,567,617,973,924,602,788}

    {83,196,192,7,148,132,273,77,140,189,325,137,312,15,94,263,205,293,93,185,337,229,366,63,48,20,224,285,100,399,240}

    Returns: 27844

  46. {10,10}

    {7,3,7,3}

    Returns: 0

  47. {5, 6, 7 }

    {5, 5, 5 }

    Returns: 3

  48. {3, 4, 5, 6 }

    {3, 3, 3, 3, 3 }

    Returns: 3

  49. {10, 10, 10 }

    {1, 1, 1 }

    Returns: 27

  50. {2, 3, 5 }

    {3 }

    Returns: 7

  51. {100, 200, 300, 400 }

    {1, 200, 251 }

    Returns: 548

  52. {12, 13, 12, 111, 111 }

    {34, 34 }

    Returns: 191

  53. {1, 1, 1, 10 }

    {4, 4 }

    Returns: 5

  54. {3, 3 }

    {2 }

    Returns: 4

  55. {5, 3, 2 }

    {2, 3, 3 }

    Returns: 2

  56. {10, 10, 2 }

    {1, 1, 8, 9 }

    Returns: 3

  57. {100, 100, 100 }

    {1 }

    Returns: 299

  58. {1000, 1000, 1000, 1000, 1000, 1000, 1000 }

    {999, 999, 999, 999, 999, 999, 999 }

    Returns: 7

  59. {5, 5, 5 }

    {5, 5, 5 }

    Returns: 0

  60. {10 }

    {5, 5 }

    Returns: 0

  61. {5 }

    {2, 3 }

    Returns: 0

  62. {10, 10 }

    {1, 1 }

    Returns: 18

  63. {20, 10, 10 }

    {10, 10, 10 }

    Returns: 10

  64. {2 }

    {1 }

    Returns: 1

  65. {4, 5 }

    {4, 2, 3 }

    Returns: 0

  66. {100, 100, 100, 100, 100, 199 }

    {1, 1 }

    Returns: 697

  67. {4, 4, 4 }

    {1 }

    Returns: 11

  68. {2, 2 }

    {1 }

    Returns: 3

  69. {1, 1, 5, 5, 10 }

    {5, 5 }

    Returns: 12

  70. {2, 3, 5 }

    {1 }

    Returns: 9

  71. {10 }

    {2, 3, 5 }

    Returns: 0

  72. {2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

    {1 }

    Returns: 19

  73. {50, 100 }

    {10, 10, 10, 10, 10, 10 }

    Returns: 90

  74. {3, 4, 5 }

    {4, 5 }

    Returns: 3

  75. {10 }

    {1, 1, 1 }

    Returns: 7

  76. {1, 1, 1, 15 }

    {5, 5, 5 }

    Returns: 3

  77. {2, 2, 2, 2, 3 }

    {3 }

    Returns: 8

  78. {2, 3 }

    {1, 1, 3 }

    Returns: 0

  79. {3, 3, 3, 3 }

    {2, 2 }

    Returns: 8

  80. {3, 5, 5 }

    {5, 3 }

    Returns: 5

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: