Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

give cpp 17 solution : Maximize Mex time limit per test1 second memory limit per test256…

  1. User

    give cpp 17 solution : Maximize Mex time limit per test1 second memory limit per test256 megabytes You are given an array a of n positive integers and an integer x . You can do the following two-step operation any (possibly zero) number of times:

    Choose an index i (1≤i≤n ). Increase ai by x , in other words ai:=ai+x . Find the maximum value of the MEX of a if you perform the operations optimally.

    The MEX (minimum excluded value) of an array is the smallest non-negative integer that is not in the array. For example:

    The MEX of [2,2,1] is 0 because 0 is not in the array. The MEX of [3,1,0,1] is 2 because 0 and 1 are in the array but 2 is not. The MEX of [0,3,1,2] is 4 because 0 , 1 , 2 and 3 are in the array but 4 is not. Input Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤5000 ). The description of the test cases follows.

    The first line of each test case contains two integers n and x (1≤n≤2⋅105 ; 1≤x≤109 ) — the length of the array and the integer to be used in the operation.

    The second line of each test case contains n integers a1,a2,…,an (0≤ai≤109 ) — the given array.

    It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 .

    Output For each test case, output a single integer: the maximum MEX of a if you perform the operations optimally.

    Example InputCopy 3 6 3 0 3 2 1 5 2 6 2 1 3 4 1 0 2 4 5 2 5 10 3 OutputCopy 4 6 0 Note In the first test case, the MEX of a is 4 without performing any operations, which is the maximum.

    In the second test case, the MEX of a is 5 without performing any operations. If we perform two operations both with i=1 , we will have the array a=[5,3,4,1,0,2] . Then, the MEX of a will become 6 , which is the maximum.

    In the third test case, the MEX of a is 0 without performing any operations, which is the maximum.

  2. Assistant

    Sure! Below is a C++17 solution to the problem "Maximize Mex". The approach uses binary search to determine the maximum possible MEX value by ensuring that for each residue modulo x, there are enough elements in the array to cover all necessary values up to the current MEX being tested.

    Explanation:

    1. Grouping by Remainder:

      • For each test case, we first group the array elements by their remainder when divided by x. This allows us to efficiently check how many elements are available to cover each required residue.
    2. Sorting:

      • Within each group, the elements are sorted. This sorting allows us to use binary search (upper_bound) to quickly determine how many elements can cover a particular MEX value.
    3. Binary Search for MEX:

      • We perform a binary search on the possible MEX values. For each midpoint M in the binary search, we check if it is possible to achieve a MEX of at least M.
      • For each residue r, we calculate how many elements are needed to cover all values with that residue up to M-1. We then check if the group for that residue has enough elements to meet this requirement.
    4. Edge Cases:

      • If no elements can cover a particular residue that’s needed, the binary search will correctly identify the failure and adjust the search range accordingly.
    5. Efficiency:

      • The solution efficiently handles large inputs by limiting operations to relevant residues only and using binary search to minimize the number of checks.

    C++17 Code:

    #include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        int t;
        cin >> t;
        while(t--){
            ll n, x;
            cin >> n >> x;
            vector<ll> a(n);
            for(auto &num: a) cin >> num;
            // Sort a by r = a_i %x, then by a_i
            sort(a.begin(), a.end(), [&](const ll &u, const ll &v) -> bool{
                ll ru = u % x;
                ll rv = v % x;
                if(ru != rv) return ru < rv;
                return u < v;
            });
            // Group by r
            vector<pair<ll, vector<ll>>> groups;
            if(n >0){
                ll current_r = a[0]%x;
                vector<ll> current_list;
                current_list.push_back(a[0]);
                for(int i=1;i<n;i++){
                    ll r = a[i]%x;
                    if(r == current_r){
                        current_list.push_back(a[i]);
                    }
                    else{
                        groups.emplace_back(make_pair(current_r, current_list));
                        current_r = r;
                        current_list = vector<ll>();
                        current_list.push_back(a[i]);
                    }
                }
                groups.emplace_back(make_pair(current_r, current_list));
            }
            // Binary search for MEX
            ll left =0, right = 2e14;
            auto check = [&](ll M) -> bool{
                for(auto &[r, vec] : groups){
                    if(r >= M) continue;
                    // need floor((M-1 -r)/x) +1
                    // if M-1 >=r
                    if(M-1 >= r){
                        ll need = (M-1 - r)/x +1;
                        // number of a_i <= M-1
                        ll available = upper_bound(vec.begin(), vec.end(), M-1) - vec.begin();
                        if(available < need) return false;
                    }
                }
                // Also need to check residues not present in groups
                // For r from 0 to min(M-1, x-1) not in groups, need to have need= floor((M-1 -r)/x)+1
                // Since they are not present, need=0 only if M-1 <r
                // Otherwise, need >=1 and available=0
                // So we need to ensure that for r not in groups, if M-1 >=r, need <=0, which is not possible since need >=1
                // Thus, for all r from 0 to min(M-1, x-1),
                // if r is not in groups and M-1 >=r, it's impossible
                // Implement this
                if(M >0){
                    // Collect all existing r's
                    // Iterate from 0 to min(M-1, x-1), check if r is in groups
                    // Use binary search on groups since groups sorted by r
                    for(ll r =0; r < min(M, x); r++){
                        // Check if r is in groups
                        // Binary search on groups
                        int idx = lower_bound(groups.begin(), groups.end(), make_pair(r, vector<ll>()), [&](const pair<ll, vector<ll>> &p, const pair<ll, vector<ll>> &q) -> bool{
                            return p.first < q.first;
                        }) - groups.begin();
                        if(idx >= groups.size() || groups[idx].first != r){
                            // r not present
                            if(M-1 >=r){
                                return false;
                            }
                        }
                    }
                }
                return true;
            };
            while(left < right){
                ll mid = left + (right - left)/2;
                if(check(mid)){
                    left = mid +1;
                }
                else{
                    right = mid;
                }
            }
            // left is the first M that fails, so MEX is left
            cout << left << "\n";
        }
    }