SpecialCells
SRM 612 · 2013-12-22 · by ltaravilse
SRM 612 · 2013-12-22 · by ltaravilse · Graph Theory
Problem Statement
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 twoint[] 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.
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
Constraints
- 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.
Examples
0)
{1,2}
{1,2}
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.
1)
{1,1,2}
{1,2,1}
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.
2)
{1,2,1,2,1,2}
{1,2,3,1,2,3}
Returns: 6
3)
{1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9}
{1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3}
Returns: 9
4)
{1,100000}
{1,100000}
Returns: 0
Submissions are judged against all 59 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SpecialCells with a public method int guess(vector<int> x, vector<int> y) · 59 test cases · 2 s / 256 MB per case