Solution for "HILO" (2021 USACO Gold)

hilo.md

hi
december contest ptsd again
this problem again

since the problem explanation is too complicated, i'll just let you read the problem yourself, there's no way i'm going to explain it myself

ok i'll assume you read the thing

anyway just the first thing i did was write a brute force python script to see if there was any pattern once N got like kinda large
lo and behold, there actually was

here's the permutation and relevant values for every x we have to go through
first row is the actual perm
all next rows go like [x] [status] [actual ans]
for the status, HI + LO are self-explanatory- SK means elsie skipped that number

   [13,  1, 16,  4, 11,  9, 15, 19,  2, 17,  3, 12, 14, 20, 18,  8,  7,  5, 10,  6]
00 [HI, HI, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK] 0
01 [HI, LO, SK, HI, SK, SK, SK, SK, HI, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK] 1
02 [HI, LO, SK, HI, SK, SK, SK, SK, LO, SK, HI, SK, SK, SK, SK, SK, SK, SK, SK, SK] 2
03 [HI, LO, SK, HI, SK, SK, SK, SK, LO, SK, LO, SK, SK, SK, SK, SK, SK, SK, SK, SK] 2
04 [HI, LO, SK, LO, HI, HI, SK, SK, SK, SK, SK, SK, SK, SK, SK, HI, HI, HI, SK, SK] 1
05 [HI, LO, SK, LO, HI, HI, SK, SK, SK, SK, SK, SK, SK, SK, SK, HI, HI, LO, SK, HI] 2
06 [HI, LO, SK, LO, HI, HI, SK, SK, SK, SK, SK, SK, SK, SK, SK, HI, HI, LO, SK, LO] 2
07 [HI, LO, SK, LO, HI, HI, SK, SK, SK, SK, SK, SK, SK, SK, SK, HI, LO, SK, SK, SK] 2
08 [HI, LO, SK, LO, HI, HI, SK, SK, SK, SK, SK, SK, SK, SK, SK, LO, SK, SK, SK, SK] 2
09 [HI, LO, SK, LO, HI, LO, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK, HI, SK] 2
10 [HI, LO, SK, LO, HI, LO, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK, LO, SK] 2
11 [HI, LO, SK, LO, LO, SK, SK, SK, SK, SK, SK, HI, SK, SK, SK, SK, SK, SK, SK, SK] 1
12 [HI, LO, SK, LO, LO, SK, SK, SK, SK, SK, SK, LO, SK, SK, SK, SK, SK, SK, SK, SK] 1
13 [LO, SK, HI, SK, SK, SK, HI, SK, SK, SK, SK, SK, HI, SK, SK, SK, SK, SK, SK, SK] 0
14 [LO, SK, HI, SK, SK, SK, HI, SK, SK, SK, SK, SK, LO, SK, SK, SK, SK, SK, SK, SK] 1
15 [LO, SK, HI, SK, SK, SK, LO, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK] 1
16 [LO, SK, LO, SK, SK, SK, SK, HI, SK, HI, SK, SK, SK, SK, SK, SK, SK, SK, SK, SK] 0
17 [LO, SK, LO, SK, SK, SK, SK, HI, SK, LO, SK, SK, SK, SK, HI, SK, SK, SK, SK, SK] 1
18 [LO, SK, LO, SK, SK, SK, SK, HI, SK, LO, SK, SK, SK, SK, LO, SK, SK, SK, SK, SK] 1
19 [LO, SK, LO, SK, SK, SK, SK, LO, SK, SK, SK, SK, SK, HI, SK, SK, SK, SK, SK, SK] 0
20 [LO, SK, LO, SK, SK, SK, SK, LO, SK, SK, SK, SK, SK, LO, SK, SK, SK, SK, SK, SK] 0

if you read the above, you'll see something magical
each value in the permutation has a "lifecycle" of some sort
it starts out as SK, becomes HI, then LO, then goes back to SK
of course the starting + ending SK's are optional as evidenced by 13, 1, 19, etc.

why is this the case? bro idk it just works

so let's try to find the x value for each value in the permutation where said value first becomes a HI
after diving into the giant blob of data above, notice that an element the permutation becomes a HI when there is NO number before it that is both

1. less than said element
2. greater than or equal to the current x value

so we can just use a sorted set and iterate through the permutation in order, finding the largest element that satisfies both of the criteria (code stores this in started_his)
after that, while we're actually going through all the x values, we keep the indices of the HIs in a set

of course, just knowing the HI points isn't enough- we also need to know when they become a LO and a SK (again)
so we'll have to notice a few more neat things about this
so first of all, the element corresponding to x in the permutation will change from HI to LO without fail each time x increments by 1
but that's obvious- the other magical thing is that when we increment- actually lemme just show you here

12 [HI, LO, SK, LO, LO, SK, SK, SK, SK, SK, SK, LO, SK, SK, SK, SK, SK, SK, SK, SK] 1
13 [LO, SK, HI, SK, SK, SK, HI, SK, SK, SK, SK, SK, HI, SK, SK, SK, SK, SK, SK, SK] 0

notice that when the HI changed to a LO (0 ind if you can't see), all the LO's to the right of it just got thanos snapped and got to the end of their lifecycle (the final SK)

so why does this always happen? again, idk lol it just does

now for the LOs, we use a stack instead of the HIs
when we change a HI to a LO with each x increment, we do the following steps:

1. remove that HI from the set of HIs
2. while the top of the stack occurs to the right of the current HI, pop it
3. convert the current HI to a LO and add it on top of the stack (so the stack will always be increasing from bottom to top)

then, now that we have the indices of the HIs and the LOs for each x value, we can just use a sorted set of all the aforementioned HIs and LOs, keeping track of the # of HILOs with each update

enough chattering, code here (really long btw)

#include <iostream>
#include <vector>
#include <set>
#include <map>

using std::cout;
using std::endl;
using std::vector;

/**
 * 2021 dec gold
 * 5
 * 5 1 2 4 3
 * should output 0, 1, 1, 2, 1, and 0, each on a new line
 * no input validation because c++ isn't python
 */
int main() {
    int size;
    std::cin >> size;
    vector<int> perm(size);
    vector<int> ind(size + 1);
    for (int i = 0; i < size; i++) {
        std::cin >> perm[i];
        ind[perm[i]] = i;
    }

    vector<vector<int>> started_his(size + 1);
    std::set<int> added;
    for (int i : perm) {
        auto it = added.lower_bound(i);
        // largest value that occurs before i and is less than i
        int start = it == added.begin() ? 0 : *(--it);
        // that's the value of x which i starts being a HI
        started_his[start].push_back(ind[i]);
        added.insert(i);
    }

    vector<int> hilo_num;
    vector<int> lo;
    std::set<int> hi;
    /*
     * hi = true, lo = false
     * the out of bounds values is so i don't have to check if random
     * iterator values are equal to the beginning or end
     * trust me they don't affect anything at alll
     */
    std::map<int, bool> hilos{{-1, false}, {size + 1, true}};
    int curr_hilo = 0;
    for (int x = 0; x <= size; x++) {
        // add the new values of hi
        for (int h : started_his[x]) {
            hi.insert(h);
            auto it = hilos.lower_bound(h);
            if (!it->second && !(--it)->second) {
                curr_hilo++;
            }
            hilos[h] = true;
        }

        hilo_num.push_back(curr_hilo);

        // start updating for the next value of x
        if (x < size) {
            int changed = ind[x + 1];
            while (!lo.empty() && changed < lo.back()) {
                auto it = hilos.lower_bound(lo.back());
                if ((--it)->second) {
                    curr_hilo--;
                }
                hilos.erase(lo.back());
                lo.pop_back();
            }
            
            bool prev = (--hilos.lower_bound(changed))->second;
            bool next = (++hilos.lower_bound(changed))->second;
            curr_hilo += prev + !next;
            hi.erase(changed);
            lo.push_back(changed);
            hilos[changed] = false;
        }
    }

    for (int i : hilo_num) {
        cout << i << '\n';
    }
}