TopCoder problem "Wardrobe" used in SRM 308 (Division I Level Three)



Problem Statement

    

You are attempting to assemble a wardrobe, but you have misplaced the instructions. The wardrobe has several holes, each of which is designed to accommodate a bolt of a specific size. A hole with size D should be matched with a bolt of size D. However, bolts with sizes D-1 and D+1 will also fit. Since you don't have the instructions, you decide to do the following: For each bolt, you will randomly choose an available hole in which the bolt will fit, and screw the bolt into that hole. If the bolt cannot fit into any of the available holes, you will skip it and move on to the next one.

You are given a int[] bolts containing the sizes of the bolts. For each element in bolts, there is a corresponding hole with the same size. Return the maximum number of unused holes that can remain at the end of this process.

 

Definition

    
Class:Wardrobe
Method:countUnscrewedHoles
Parameters:int[]
Returns:int
Method signature:int countUnscrewedHoles(int[] bolts)
(be sure your method is public)
    
 

Constraints

-bolts will contain between 1 and 50 elements, inclusive
-Each element of bolts will be between 1 and 100, inclusive.
 

Examples

0)
    
{1, 2, 3}
Returns: 1
You can screw the bolt with size 2 into the hole with size 1, and the bolt with size 3 into the hole with size 2. The bolt with size 1 cannot fit into the remaining hole with size 3, so one hole will remain unused in this case.
1)
    
{1, 2, 3, 2, 4}
Returns: 1
2)
    
{1, 2, 3, 3, 4, 2, 5, 4}
Returns: 2
3)
    
{12, 14, 12, 25, 15, 22, 19, 13, 26, 19, 24, 18, 14}
Returns: 2
4)
    
{26, 26, 26, 14, 13, 28, 27, 15, 27, 28, 28, 26}
Returns: 3

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9988&pm=6181

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , lbackstrom , brett1479 , radeye , vorthys , Olexiy

Problem categories:

Brute Force, Greedy