Official

E - Takahashi Quest Editorial by en_translator

It seems we can assume that, for every monster, he uses the potion discovered the most recently among those effective for that monster.

Thus, we come up with the following greedy algorithm:

  • He temporarily picks up all the potions.
  • When he encounters a monster,
    • he is defeated if he does not have a potion effective for that monster;
    • otherwise, he uses the one discovered the most recently among such potions.
  • If he still have potions at the end of the adventure, it is regarded not having been picked up.

This greedy algorithm determines whether he will be defeated correctly, as well as the minimum \(K\) if he will not.

Proof of validity

  • That the algorithm determines whether he will be defeated correctly:
    • As he temporarily picks up all the potions, the verdict of defeat means he cannot find \(K\) or more potions of some type before encountering \(K\) monsters of that type. This means that he will be defeated no matter what. Conversely, when such a verdict is not given, the algorithm constructs a specific strategy to avoid defeat.
  • That the algorithm gives the minimum possible \(K\)
    • A strategy can be represented as a sequence of indices of potions used for the monsters. For a strategy \(t\), let potion \(f(t,m)\) be the one used for monster \(m\).
      Take a strategy \(T\) that minimizes \(K\). Suppose that there is a monster that does not coincide with the resulting strategy \(T ^ \prime\) of the greedy algorithm; take the first such monster \(M _ {\operatorname{first}}\) to encounter. By the assumption of the greedy algorithm, he discovers \(f(T,M _ {\operatorname{first}})\) before discovering \(f(T ^ \prime,M _ {\operatorname{first}})\).
      If there is no monster \(\hat M\) such that \(f(T,\hat{M})=f(T ^ \prime,M _ {\operatorname{first}})\), one can simply replace \(f(T,M _ {\operatorname{first}})\) with \(f(T ^ \prime,M _ {\operatorname{first}})\) without increasing \(K\) (because he maintains one less potion since discovering \(f(T,M _ {\operatorname{first}})\) until discovering \(f(T ^ \prime,M _ {\operatorname{first}})\)). When \(\hat M\) exists, one can swap \(f(T,\hat M)\) and \(f(T,M _ {\operatorname{first}})\) without increasing \(K\). (By definition of \(M _ {\operatorname{first}}\), the monster \(\hat M\) emerges after \(M _ {\operatorname{first}}\). Thus, the timeline of encounter and discovery is \(f(T,M _ {\operatorname{first}})\rightarrow f(T,\hat M)\rightarrow M _ {\operatorname{first}}\rightarrow\hat M\), so swapping the usage of the two potions do not change the number of potions maintained at each point).
      Therefore, one can match \(M _ {\operatorname{first}}\) (and all the preceding monsters) with \(T ^ \prime\) without increasing \(K\). Since there are a finite number for monsters, the strategy can be matched with \(T ^ \prime\) with a finite number of repetition of this procedure. By definition of \(T\), the \(K\) given by \(T ^ \prime\) is indeed the minimum.

We have to find fast the potion picked up most recently among those effective to the current monster. This can be achieved fast enough by managing the potions in a stack.

Once we find the number of potions used for each monster, one can use a cumulative sum trick to find \(K\).

The following is sample code.

#include <iostream>
#include <utility>
#include <stack>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>

int main() {
    using namespace std;

    unsigned N;
    cin >> N;

    // Potion type -> {when was it picked up, potion index}
    vector<stack<pair<unsigned, unsigned>>> potion_holder(N);

    // potion_result[i] := true ⇔ potion i is picked up
    basic_string<bool> potion_result;
    // ∑_{j≤i}occupied_imos[j] := the number of potions maintained at i-th event
    vector<unsigned> occupied_imos(N);

    for (unsigned turn = 0; turn < N; ++turn) {
        unsigned event_type;
        cin >> event_type;
        if (event_type == 1) { // If he finds a potion
            unsigned potion_type;
            cin >> potion_type;
            --potion_type;
            potion_holder[potion_type].emplace(turn, size(potion_result)); // pick it up for now
            potion_result += false; // assuming that it will not be used
        } else { // If he encounters a monster
            unsigned monster_type;
            cin >> monster_type;
            --monster_type;
            if (empty(potion_holder[monster_type])) { // if he does not have an effective potion
                cout << "-1" << endl; // he is defeated
                return 0;
            }
            // If he does have one
            const auto&[t, i]{potion_holder[monster_type].top()}; // Use the one picked up the most recently
            ++occupied_imos[t];
            --occupied_imos[turn];
            potion_result[i] = true;
            potion_holder[monster_type].pop();
        }
    }

    // Find the cumulative sum
    inclusive_scan(begin(occupied_imos), end(occupied_imos), begin(occupied_imos));

    // The maximum potions maintained
    cout << ranges::max(occupied_imos) << endl;

    // Print whether each potion is picked up
    for (const auto result : potion_result)
        cout << result << " ";
    cout << endl;
    return 0;
}

posted:
last update: