Get Time

   Problem Statement  

 Problem Statement for SpecialCells

Problem Statement

    Guillermo and Gustavo are playing a game. The game is played on a rectangular board with 100,000 rows and 100,000 columns of cells. Both the rows and the columns are numbered 1 through 100,000.

Guillermo has chosen some cells in the grid. We will call those cells special. Guillermo then created two lists of integers. One of the lists contains the x coordinates of all special cells, the other list contains the y coordinates of all special cells. If some coordinate occurs multiple times among the special cells, it gets included multiple times into the corresponding list. Guillermo shuffled each of the lists separately, and then he has shown the two lists to Gustavo. Thus, Gustavo now knows the two lists, but he does not know which x coordinate corresponds to which y coordinate.

Gustavo now has to guess which cells are special. His guess must be consistent with the two lists he saw. That is, he must select the correct number of cells, their list of x coordinates must correspond to the first list he saw, and their list of y coordinates must correspond to the second list he saw.

Gustavo wins the game if and only if at least T of the cells he guessed are actually special.

You are given two int[]s x and y that describe the special cells chosen by Guillermo. For each valid i, (x[i], y[i]) is one of the special cells. Find and return the largest T such that Gustavo will certainly win the game. In other words, find the largest T such that each valid guess will contain at least T special cells.


Parameters:int[], int[]
Method signature:int guess(int[] x, int[] y)
(be sure your method is public)


-x will contain between 1 and 50 elements, inclusive.
-x and y will contain the same number of elements.
-Each element of x will be between 1 and 100,000, inclusive.
-Each element of y will be between 1 and 100,000, inclusive.
-All cells (x[i], y[i]) will be distinct.


Returns: 0
The two special cells are (1,1) and (2,2). If Gustavo guesses (1,2) and (2,1) then he loses unless T is 0, so you must return 0.
Returns: 3
There is only one valid guess: the three special cells. Note that Gustavo's guess must contain three different cells, it cannot contain the cell (1,1) twice.
Returns: 6
Returns: 9
Returns: 0

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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 612 Round 1 - Division I, Level Two