man istg each year the problem descriptions get more and more elaborate
$10 they'll be asking us to solve tsp in linear time by 2030
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
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?
lmao, i have no idea.
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
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 `HI`s 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
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:
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
man that was really long huh
impl right here: