Editorial for Market Movers

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: oree

In this problem, we need to repeatedly alternate between taking some amount of the cheapest contract, and some amount of the most expensive contracts, for some amount of turns. Following this, we need to sum up and output the total remaining value of all the contracts. When taking contracts, if we take all of a contract and still have to buy more, we move to the next cheapest or most expensive.

One way to do this efficiently is using a std::map in C++ to store the contract value as the key and the volume as the value. These maps are stored as binary search trees in order of the key, so we can get and modify the cheapest or most expensive in $O(\log n)$ ~O(\log n)~ time using map.begin() and --map.end(). Another way we can do this is sorting a list of pairs by the contract price, and maintaining a pointer at the front and the back that moves towards the middle as contracts are bought.

The map approach gives a time complexity of $O((n+m)\log n)$ ~O((n+m)\log n)~ while the sorting approach gives a time complexity of $O(n\log n + m)$ ~O(n\log n + m)~, though both are more than fast enough to pass. Both have a space complexity of $O(n)$ ~O(n)~ due to storing the given contracts.

C++ solution:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> futures_inp(n);
    for (auto& [_, amount] : futures_inp)
        cin >> amount;
    for (auto& [val, _] : futures_inp)
        cin >> val;

    map<int, long long> futures;
    for (auto [val, amount] : futures_inp)
        futures[val] += amount;

    vector<int> rounds(m);
    for (auto& x : rounds)
        cin >> x;

    for (int i = 0; i < m; i++) {
        int need = rounds[i];

        while (need > 0 && !futures.empty()) {
            auto it = (i % 2 == 0) ? futures.begin() : prev(futures.end());

            if (it->second > need) {
                it->second -= need;
                need = 0;
            } else {
                need -= it->second;
                futures.erase(it);
            }
        }
    }

    long long res = 0;
    for (auto [k, v] : futures)
        res += 1LL * k * v;

    cout << res << '\n';
}

Python solution:

n, m = map(int, input().split())

amounts = list(map(int, input().split()))
values = list(map(int, input().split()))
turns = list(map(int, input().split()))

# Pair up (amount, value), and sort by value ascending
futures = sorted(zip(amounts, values), key=lambda x: x[1])

# Retail investor takes from left, trader takes from right
l, r = 0, n - 1

# Keep taking from either left or right until turn is empty
# The direction depends on parity of i
for i, turn in enumerate(turns):
    while turn:
        idx = l if i % 2 == 0 else r
        amt, val = futures[idx]
        take = min(amt, turn)
        amt -= take
        turn -= take
        futures[idx] = (amt, val)
        if amt == 0:
            if i % 2 == 0:
                l += 1
            else:
                r -= 1

# Compute total remaining value
print(sum(amt * val for amt, val in futures))

Comments

There are no comments at the moment.