TwoNumberGroupsEasy
SRM 640 · 2014-08-25 · by dreamoon
Problem Statement
A multiset is the same thing as a set, with the difference that a multiset can contain multiple copies of the same element. For example, {1,1,1,2,3} is a multiset that contains three 1s, one 2, and one 3.
The distance between two multisets is the smallest total number of elements we need to erase from them in order to make them equal. For example, the distance between {1,1,2,2,3} and {1,2,2,4} is 3. Note that we can compute distance as follows: For each value, we count its occurrences in the first multiset, we count its occurrences in the second multiset, and we write down the difference between those two counts. The distance is then equal to the sum of all values we wrote down.
If S is a multiset, then (S modulo M) is the multiset of all values (x modulo M) where x belongs to S. For example, if S = {11,12,13,21,22} and M = 10, then (S modulo M) = {1,2,3,1,2} = {1,1,2,2,3}.
You have two multisets called A and B.
The first multiset is described by the
We are now looking for a positive integer M with the following properties: M must be greater than 1, and the distance between (A modulo M) and (B modulo M) must be as small as possible. Compute and return the smallest possible distance.
Constraints
- A and B will each contain between 1 and 10 elements, inclusive.
- All elements of A will be distinct.
- All elements of B will be distinct.
- The number of elements in numA will be the same as the number of elements in A.
- The number of elements in numB will be the same as the number of elements in B.
- All elements of A and B will be between 1 and 1,000,000,000, inclusive.
- All elements of numA and numB will be between 1 and 100,000, inclusive.
{1,2,3,4}
{2,1,1,1}
{5,6,7,8}
{1,1,1,2}
Returns: 2
This input describes the multisets A = {1,1,2,3,4} and B = {5,6,7,8,8}. For M=2, we have (A modulo M) = {0,0,1,1,1} and (B modulo M) = {0,0,0,1,1}. The distance between these two multisets is 2, and that is the best we can get.
{5,7}
{1,1}
{12,14}
{1,1}
Returns: 0
The optimal solution is obtained for M = 7.
{100}
{2}
{1}
{1}
Returns: 1
{1}
{1}
{1}
{1}
Returns: 0
{5}
{1}
{6}
{1}
Returns: 2
Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TwoNumberGroupsEasy with a public method int solve(vector<int> A, vector<int> numA, vector<int> B, vector<int> numB) · 77 test cases · 2 s / 256 MB per case