2561: Rearranging-Fruits
Hard

table of contents

For this question, the first important part to realise is that for an equal rearragement of fruit to be possible, the must be an even count of each fruit present in each basket.

Then, if a valid rearragement does exist and a fruit is misplaced on one side, it implies that there also exists a misplaced fruit on the other side. Without loss of generality, we can denote any two misplaced fruits on opposing sides as x and y, and assume that the cost of x < y. That means for each misplaced fruit, we have 2 possible options.

  1. swap x and y, with a total cost of min(x, y) = x
  2. swap x and y using a fruit of minimum cost, a, with a total cost of 2 * a
    • assume that there exists a fruit with minimum cost of a.
    • wlog, let us assume that it lies on the same side of x and opposite y. Then, we can simply undergo 2 operations; 1st swaps a and y, and 2nd swaps a and x

Therefore, our algorithm becomes greedy where, for each misplaced fruit, we simply choose one of 2 possible options to rearrange our fruit.

code

class Solution {
public:
    long long minCost(vector<int>& basket1, vector<int>& basket2) {
        unordered_map<int, int> mp;
        int paritySum = 0;
        int minVal = INT32_MAX;
        for (int& fruit : basket1) {
            ++mp[fruit];
            if (mp[fruit] % 2 == 1) {
                ++paritySum;
            } else {
                --paritySum;
            }
            minVal = min(minVal, fruit);
        }

        for (int& fruit : basket2) {
            --mp[fruit];
            if (abs(mp[fruit]) % 2 == 1) {
                ++paritySum;
            } else {
                --paritySum;
            }
            minVal = min(minVal, fruit);
        }

        if (paritySum != 0) {
            return -1;
        }
        
        int count = 0;
        vector<pair<int, int>> toMove;
        for (auto& [key, value] : mp) {
            if (value != 0) {
                toMove.emplace_back(key, abs(value));
                count += abs(value);
            }
        }
        count /= 4;
        sort(toMove.begin(), toMove.end());

        int index = 0;
        long long ans = 0;
        while(count > 0) {
            ans += (long long)min(2*minVal, toMove[index].first) * (long long)min(count, toMove[index].second/2);
            count -= min(count, toMove[index].second/2);
            ++index;
        }

        return ans;
    }
};

complexity

time taken