TopCoder problem "Sheep" used in SRM 483 (Division I Level Three)



Problem Statement

    After a long bout of sleeplessness, Elleonara has finally fallen asleep. To accomplish this, she had to count sheep until the number overflowed and became negative. She is now in the middle of a strange dream. She is on the bank of a river with a flock of numSheep sheep, and across the river are endless grass fields. She wants to take all her sheep across the river to the fields using a single boat. Elly wonders what the minimum weight capacity of the boat must be for her to accomplish this by making at most maxRuns runs. Crossing the river to the fields and then coming back again counts as a single run.



Her sheep are of varying weights. She decides to use the following greedy strategy to determine the order in which to take them. In each run, she first chooses the heaviest remaining sheep that can fit in the boat. Then, after putting that sheep in the boat, she again chooses the heaviest remaining sheep that can fit in the boat along with the previously chosen sheep. She repeats this process until no other sheep can fit in the boat. She then takes the boat to the other side, drops off the sheep, and comes back. For example, if the boat's capacity is 42 and the sheep have weights of 30, 15, 13, 8, 5, 3, 2 and 2, she would pick the sheep with weights 30, 8 and 3. If after maxRuns runs, there are still sheep remaining on the bank, this means the capacity of the boat is not high enough.



You are given String[]s part1, part2, part3 and part4. Concatenate the elements in each String[] in the same order as they are given without any delimiters between its elements to get four long strings. Then, concatenate those strings to get a space separated list of integers. Each integer is the weight of one sheep in her flock. Return the minimum weight capacity of a boat that will accomplish Elly's goal.
 

Definition

    
Class:Sheep
Method:minCapacity
Parameters:int, int, String[], String[], String[], String[]
Returns:int
Method signature:int minCapacity(int numSheep, int maxRuns, String[] part1, String[] part2, String[] part3, String[] part4)
(be sure your method is public)
    
 

Notes

-Elly's weight is a constant and can be ignored.
-Although her strategy of matching sheep into the boat is not always optimal, she will use it anyway.
-The capacity of the boat should be at least as much as the largest sheep (otherwise it couldn't be moved on any run) and no more than the sum of the weights of all sheep (which guarantees that they can be moved on the first run).
 

Constraints

-numSheep will be between 1 and 2,000, inclusive.
-maxRuns will be between 1 and 2,000, inclusive.
-part1, part2, part3 and part4 will each contain between 0 and 50 elements, inclusive.
-Each element of part1, part2, part3 and part4 will contain between 1 and 50 characters, inclusive.
-After concatenating the elements of part1-part4, and then concatening those strings, the final string will be a single space separated list of integers.
-There will be exactly numSheep integers in the list.
-Each integer in the list will be between 1 and 2,000, inclusive.
-Integers in the list will have no leading zeros.
 

Examples

0)
    
6
2
{ "26 7 10 30 5 4" }
{ }
{ }
{ }
Returns: 42
The capacity of the boat should be at least 30, but this is not enough for all sheep to be taken with only 2 runs. Indeed, in this case Elleonora would need three runs - first, she would transfer the sheep with weight 30, then the sheep with weights 26 and 4 and finally the sheep with weights 10, 7 and 5. The smallest capacity that satisfies Elleonora is 42 - the first run will be (30, 10) and the second will be (26, 7, 5, 4). Note that there exists a strategy where the boat of size 41 is enough - the runs are (30, 7, 4) and (26, 10, 5), but Elly will not use it.
1)
    
6
2
{ "4 8 15 16 23 42" }
{ }
{ }
{ }
Returns: 54
With capacity 54 the runs are (42, 8, 4) and (23, 16, 15). Since in both of them the boat is completely filled, this guarantees that the answer is optimal.
2)
    
15
4
{ "666 42 7 13 400 511 600 200 202 111 313 94 280", " 72 42" }
{ }
{ }
{ }
Returns: 896
We can have equal numbers in the input.
3)
    
7
6
{ "200 2", "01 202 203" }
{ " 204 " }
{ }
{ "205", " ", "206" }
Returns: 401
Don't forget to concatenate the elements correctly.
4)
    
200
20
{ "42 468 335 501 1170 1725 1479 1359 963 465 1706",
  " 146 1282 828 1962 492 996 1943 828 1437 392 605",
  " 1903 154 293 383 1422 717 1719 1896 1448 1727",
  " 772 1539 1870 1913 1668 300 1036 1895 704 1812",
  " 1323 334 1674 665 1142 1712 254 869 1548 1645",
  " 663 758 38 860 724 1742 1530 779 317 1036 191",
  " 1843 289 107 1041 943 1265 649 1447 1806 1891",
  " 730 371 1351 1007 1102 394 1549 1630 624 85 1955",
  " 757 1841 967 1377 1932 309 945 440 627 1324 1538",
  " 1539 119 83 930 542 834 1116 640 1659 705 1931",
  " 1978 307 1674 387 1022 746 925 1073 271 1830 778",
  " 1574 1098 513 1987 1291 1162 637 356 768 1656",
  " 1575 32 53 1351 1151 942 1725 1967 1431 1108 192",
  " 8 1338 1458 288 1754 384 946 910 210 1759 222",
  " 589 423 947 1507 1031 414 1169 901 592 763 1656",
  " 1411 360 1625 538 1549 484 1596 42 1603 351 292",
  " 837 1375 1021 597 22 1349 1200 1669 485 282 735",
  " 54 2000 419 1939 901 1789 128 468 1729 894 649",
  " 484 1808 422 311 618 814 1515" }
{ }
{ }
{ }
Returns: 9986

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10920

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14236&pm=10920

Writer:

espr1t

Testers:

PabloGilberto , ivan_metelsky , gojira_tc , StevieT , keshav_57

Problem categories:

Greedy, Search, Simulation