LeetCode Weekly Contest 280

1. Count Operations to Obtain Zero

Naive.

c++

class Solution
{
public:
    int countOperations(int num1, int num2)
    {
        int ans = 0;
        
        while (num1 != 0 && num2 != 0)
        {
            if (num1 < num2)
            {
                swap(num1, num2);
            }
            
            ans++;
            num1 -= num2;
        }
        
        return ans;
    }
};

2. Minimum Operations to Make the Array Alternating

So basically we need to decide the first two numbers only.
For each number, we may only consider the top-2 frequent numbers within that group.
Or we may consider a totally different number (in case all numbers are same).

c++

class Solution
{
public:
    
    vector<int> common(vector<int> &nums)
    {
        unordered_map<int, int> cnt;
        
        for (auto &x : nums)
        {
            cnt[x]++;
        }
        
        vector<int> ans;
        
        for (auto &pair : cnt)
        {
            if (ans.size() < 2)
            {
                ans.push_back(pair.first);
                continue;
            }
            
            if (pair.second > cnt[ans[0]])
            {
                ans[1] = ans[0];
                ans[0] = pair.first;
            }
            else if (pair.second > cnt[ans[1]])
            {
                ans[1] = pair.first;
            }
        }
        
        ans.push_back(0);
        
        return ans;
    }
    
    int minimumOperations(vector<int>& nums)
    {
        int n = nums.size();
        
        vector<int> a, b;
        
        for (int i = 0; i < n; i++)
        {
            if (i % 2 == 0)
            {
                a.push_back(nums[i]);
            }
            else
            {
                b.push_back(nums[i]);
            }
        }
        
        vector<int> ta = common(a), tb = common(b);
        
        int ans = INT_MAX;
        
        for (auto &pa : ta)
        {
            for (auto &pb : tb)
            {
                if (pa == pb)
                {
                    continue;
                }
                
                int tmp = 0;
                
                for (auto &x : a)
                {
                    if (x != pa)
                    {
                        tmp++;
                    }
                }
                
                for (auto &x : b)
                {
                    if (x != pb)
                    {
                        tmp++;
                    }
                }
                
                ans = min(ans, tmp);
            }
        }
        
        return ans;
    }
};

3. Removing Minimum Number of Magic Beans

Let's say the final equal number is $x$ .
For numbers which are lower than $x$ , we should take all beans from relative bags.
For numbers which are higher or equal than $x$ , reduce the number to $x$ .
Sort and linear-scan.

c++

class Solution
{
public:
    long long minimumRemoval(vector<int>& beans)
    {
        int n = beans.size();
        
        sort(beans.begin(), beans.end());
        
        long long total = 0;
        
        for (auto &x : beans)
        {
            total += x;
        }
        
        long long a = 0, ans = total;
        
        for (long long i = 0; i < n; i++)
        {
            long long tmp = a + (total - a - (n - i) * beans[i]);
            
            ans = min(ans, tmp);
        }
        
        return ans;
    }
};

4. Maximum AND Sum of Array

If you know Hungarian Algorithm.
Split each slot into two nodes (since they can have at most two numbers).

c++

// KM Template

template <typename T>
struct KM
{
    int n;
    vector<int> matchx;
    vector<int> matchy;
    vector<int> pre;
    vector<bool> visx;
    vector<bool> visy;
    vector<T> lx;
    vector<T> ly;
    vector<vector<T> > g;
    vector<T> slack;
    T inf;
    T res;
    queue<int> q;
    int org_n;
    int org_m;

    KM(int _n, int _m)
    {
        org_n = _n;
        org_m = _m;
        n = max(_n, _m);
        inf = numeric_limits<T>::max();
        res = 0;
        g = vector<vector<T> >(n, vector<T>(n));
        matchx = vector<int>(n, -1);
        matchy = vector<int>(n, -1);
        pre = vector<int>(n);
        visx = vector<bool>(n);
        visy = vector<bool>(n);
        lx = vector<T>(n, -inf);
        ly = vector<T>(n);
        slack = vector<T>(n);
    }

    void addEdge(int u, int v, int w)
    {
        g[u][v] = max(w, 0);
    }

    bool check(int v)
    {
        visy[v] = true;
        
        if (matchy[v] != -1)
        {
            q.push(matchy[v]);
            visx[matchy[v]] = true;
            return false;
        }

        while (v != -1)
        {
            matchy[v] = pre[v];
            swap(v, matchx[pre[v]]);
        }

        return true;
    }

    void bfs(int i)
    {
        while (!q.empty())
        {
            q.pop();
        }
        q.push(i);
        visx[i] = true;
        while (true)
        {
            while (!q.empty())
            {
                int u = q.front();
                q.pop();
                for (int v = 0; v < n; v++)
                {
                    if (!visy[v])
                    {
                        T delta = lx[u] + ly[v] - g[u][v];

                        if (slack[v] >= delta)
                        {
                            pre[v] = u;
                            if (delta)
                            {
                                slack[v] = delta;
                            }
                            else if (check(v))
                            {
                                return;
                            }
                        }
                    }
                }
            }

            T a = inf;
            for (int j = 0; j < n; j++)
            {
                if (!visy[j])
                {
                    a = min(a, slack[j]);
                }
            }
            for (int j = 0; j < n; j++)
            {
                if (visx[j])
                {
                    lx[j] -= a;
                }
                if (visy[j])
                {
                    ly[j] += a;
                }
                else
                {
                    slack[j] -= a;
                }
            }
            for (int j = 0; j < n; j++)
            {
                if (!visy[j] && slack[j] == 0 && check(j))
                {
                    return;
                }
            }
        }
    }

    int solve()
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                lx[i] = max(lx[i], g[i][j]);
            }
        }

        for (int i = 0; i < n; i++)
        {
            fill(slack.begin(), slack.end(), inf);
            fill(visx.begin(), visx.end(), false);
            fill(visy.begin(), visy.end(), false);
            bfs(i);
        }

        for (int i = 0; i < n; i++)
        {
            if (g[i][matchx[i]] > 0)
            {
                res += g[i][matchx[i]];
            }
            else
            {
                matchx[i] = -1;
            }
        }

        return res;
    }
};

// End of KM template.

class Solution
{
public:
    
    int maximumANDSum(vector<int>& nums, int numSlots)
    {
        int n = nums.size();
        int m = 2 * numSlots;
        
        KM<int> km(n, m);
        
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                km.addEdge(i, j, nums[i] & ((j % numSlots) + 1));
            }
        }
        
        return km.solve();
    }
};

LeetCode Weekly Contest 280

1. Count Operations to Obtain Zero

2. Minimum Operations to Make the Array Alternating

3. Removing Minimum Number of Magic Beans

4. Maximum AND Sum of Array

COMMAND INTERFACE

:help aguang.xyz