EllysPairing
SRM 606 · 2013-12-22 · by espr1t
Problem Statement
Elly is quite excited! She is about to participate in an awesome initiative: several universities from all around the world are collaborating on a pair-programming project. Now the organizers of the initiative want to form the pairs (teams of two people) that will work on the project.
Any two people may be paired, regardless of whether they are from the same university or not. However, it is awkward when the two teammates share the same name. Therefore the organizers would like to maximize the number of pairs such that the two paired participants have different names.
There are M different possible names, M being an exact power of two (e.g., 1, 2, 32, 131072, 1073741824). For simplicity, we will represent each name as a number between 0 and M-1, inclusive. You are given the
Return the maximum number of disjoint pairs in which the two people have different names.
Notes
- In order to make the generation of the names more efficient, it is guaranteed that M will be an exact power of two. Thus, instead of computing modulo M, the next name can be computed from the previous one by using the following formula: next = (previous * mult[i] + add[i]) & (M - 1). In this formula, '&' is the bitwise operator AND.
- Depending on your programming language, you may make the generation of names even faster by using 32-bit integers only. Even though the multiplication may overflow, the & will then only select the bits we are interested in, and those will be correct. (Note that in C++ you should use unsigned 32-bit integers. Even though your code will probably also work with signed ints, signed integer overflow leads to undefined behavior in C++.)
- The bitwise operator AND (the operator '&' in C++, Java, Python, and C#; the operator 'And' in VB) takes the binary representation of two numbers and creates a new number which has 1-bits only in the positions where both initial numbers had 1. For example 5 & 3 = 1, since 101 & 011 = 001.
Constraints
- M will be between 1 and 1,073,741,824, inclusive.
- M will be an exact power of two.
- count, first, mult, and add will contain between 1 and 50 elements, inclusive.
- count, first, mult, and add will contain the same number of elements.
- Each element of count will be between 1 and 1,000,000, inclusive.
- Each element of first, mult, and add will be between 0 and M-1, inclusive.
16
{4, 7}
{5, 3}
{2, 3}
{1, 0}
Returns: 5
The people from university 0 have names {5, 7, 11, 15} and the ones from university 1 have names {1, 3, 3, 9, 9, 11, 11}. Since the number of people is odd, there can be at most 5 pairs altogether. It turns out that each of those pairs can contain two people with different names! One of the possible pairings is: {(5, 15), (7, 3), (11, 9), (1, 3), (9, 11)}.
8
{6, 4, 3}
{0, 3, 2}
{3, 7, 5}
{0, 3, 2}
Returns: 5
In this example the people have names {0, 3, 2, 0, 0, 4, 0, 3, 6, 0, 0, 0, 0}. In the best solution there are 5 pairs such that the two people have different names. Additionally, there is one pair in which both people have the same name and one other person without a partner.
128
{42, 13, 666, 17, 1337, 42, 1}
{18, 76, 3, 122, 0, 11, 11}
{33, 17, 54, 90, 41, 122, 20}
{66, 15, 10, 121, 122, 1, 30}
Returns: 1059
1048576
{4242, 42, 9872, 13, 666, 21983, 17, 1337, 42, 1}
{19, 18, 76, 42, 3, 112, 0, 11, 11, 12}
{27, 33, 10, 8, 17, 9362, 90, 41, 122, 20}
{98, 101, 66, 15, 10, 144, 3, 1, 5, 1}
Returns: 16232
1073741824
{894602, 946569, 887230, 856152, 962583, 949356, 904847, 829100, 842183, 958440,
811081, 864078, 809209, 938727, 949135, 892809, 816528, 961237, 979142, 890922}
{844085078, 898937259, 243490172, 887804102, 187696417, 156820442, 237600210, 618812924, 153000239, 912364033,
254936966, 650298774, 982988140, 649258331, 566444626, 201481721, 492943390, 1061953081, 492672963, 960519711}
{1036482037, 583219072, 819168094, 253755052, 548208982, 401830167, 638626082, 43642932, 123607749, 485521178,
860368129, 30334704, 219771462, 733375600, 130839219, 415503960, 294132484, 1044831462, 256910484, 198852170}
{889169006, 604831366, 967292994, 980686280, 844875791, 1027687492, 357734882, 295879743, 48284748, 421729100,
1049536313, 327207332, 948053446, 271229570, 664579359, 795815285, 842856528, 876662975, 675611938, 634229925}
Returns: 8971965
Don't forget that the memory limit for the problem is only 16 megabytes! We recommend that you test this example in the arena before you submit.
Submissions are judged against all 163 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EllysPairing with a public method int getMax(int M, vector<int> count, vector<int> first, vector<int> mult, vector<int> add) · 163 test cases · 2 s / 256 MB per case