TopCoder problem "TheHomework" used in SRM 381 (Division I Level Two)



Problem Statement

    

John has a list of integers first, and his task is to transform it so that it contains exactly the same elements as another list second (but not necessarily in the same order).

To achieve this goal, John will perform a number of operations in sequence. These are the three operations that can be performed on a list:

  • Add some arbitrary integers to the list. The number of elements added must not be more than the size of the list before the operation.
  • Delete some elements from the list. The number of elements deleted must not be more than half of the size of the list before the operation.
  • Arbitrarily change some elements in the list. The number of elements changed must not be more than half of the size of the list.

You are given int[]s first and second. Return the minimum number of operations required to achieve John's goal.

 

Definition

    
Class:TheHomework
Method:transform
Parameters:int[], int[]
Returns:int
Method signature:int transform(int[] first, int[] second)
(be sure your method is public)
    
 

Notes

-A list may contain repeated elements. When determining if two lists contain the same elements, all occurrences of each integer must exist in both lists.
 

Constraints

-first will contain between 1 and 50 elements, inclusive.
-second will contain between 1 and 50 elements, inclusive.
-Each element of first will be between 0 and 1000, inclusive.
-Each element of second will be between 0 and 1000, inclusive.
 

Examples

0)
    
{1,2,3}
{2,3,4}
Returns: 1
It is enough just to change the 1 to a 4.
1)
    
{0}
{1}
Returns: 2
We can add 1 and then delete 0.
2)
    
{5,2,7,999,7}
{7,7,2,999,5}
Returns: 0
These lists already contain the same elements.
3)
    
{12,13}
{1,1,1,1,1,1,1,1,1}
Returns: 4
Three additions and one deletion can be applied.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10804&pm=8415

Writer:

Vasyl[alphacom]

Testers:

PabloGilberto , Olexiy , ivan_metelsky , ged

Problem categories:

Greedy