in this blog i will talk about how i came up with this problem.

warning - spoilers ahead! i mention the intended solution multiple times in this blog, so if you want to solve the problem first, i strongly recommend leaving this for later.

this year (around may) i had the pleasure of participating in the EGOI (European Girls Olympiad in Informatics) as a guide with two other great friends!

i enjoyed the whole week spent in Cesenatico, and i also got to know very interesting people from all over the world. one of our main tasks was helping set up the contest hall, of course, and we spent a couple days running around the hotel carrying stuff and coming in and out of the contest hall. on one of the days, three other guys and i were tasked with the wiring: running ethernet cables from the master switch to the smaller switches on each table, which would then be connected directly to the computers.

honestly, this was one of the tasks i had the most fun doing, and i don’t really understand why this was an unpopular opinion. (-_-) but for those who haven’t experienced this level of fun yet, what we had to do was pretty much like this:

the fun part was in the third-to-fourth step: untangling the wires is a bit of a pain because they sprout from the inside in (i guess?) random order, causing them to cross over awkwardly once you position them like in step four.

this led me to think - given this ordering, what is the best arrangement one could achieve, in terms of minimizing the number of crossings?

counting the number of crossings in a linear cable arrangement, like the one in the picture below is easy:

without loss of generality, we can assume that the starting arrangement is the identity permutation. let $t$ be the target permutation. cables $i$ and $j$ ($i < j$) cross iff $t_i > t_j$. hence, counting the number of cable crossings is the same as counting the number of inversions in $t$.

since jackets are circular, modeling the crossings like this surely wouldn’t represent the situation accurately. there is actually a way to do this by “flattening” the initial circular arrangement in some way, but that would have involved some nasty geometry which scared me off, so i dropped that branch of thinking.

later on that day, or maybe the next day (i don’t really remember xD), i was walking to a gelato store nearby with the other guides, and suddenly i had an aha! moment: since the sprouting order is circular, what if we considered cyclic permutations? this would break the inversion counting scheme, but there was one way to fix it: allowing the target permutation to be cyclically shifted arbitrarily, whereas the starting arrangement would remain still. so one of the first drafts of this problem was like that: given a permutation, minimize the number of inversions over all cyclic shifts. i came up with a blurry solution sketch in my mind using segment trees, but i thought it’d be boring since all you had to do was to count inversions and simulate the shifts efficiently, so i dropped the idea for a while…

until now. it was qualifiers season, and in my first year as a non-contestant, i wanted to prepare some problems for our uni qualifiers, since it was our first year featuring our own problems and our own online judge! (thank you JOliva)

i thought we needed a knowledge-check type problem, and i remembered a while ago i had thought about a data structures problem involving cables and stuff. that’s when i thought, the solution was easier than what i had thought three months ago! since sending $a_1$ to the front always changes the number of inversions by $n + 1 - 2a_1$ because we’re dealing with a permutation: all the numbers smaller than $a_1$ are initially to its right. this meant that the initial step of finding the number of inversions was just that with no further thinking involved. maybe as a knowledge check this was good, but this checked whether the contestant knew how to efficiently compute the number of inversions in a permutation instead of knowing how to use a segment tree, so i tried to come up with something else that involved instead computing the minimum difference of inversions, since that was a neater observation, in my opinion.

this was when the second aha! moment happened: the minimum inversion difference among all cyclic shifts was a prefix minimum of the prefix sum array of deltas, i.e. taking prefix sums over $n + 1 - 2a_i$. now, how are you supposed to use segment trees here? add swap queries. they can be processed as a range add on the prefix sum array of deltas.

and that’s it! there’s the whole problem for ya.

maybe one day i will write more about EGOI. it was really fun and i’m sure there’s a lot more things worth writing about (i’m just too lazy to write pls understand). anyway, hope you enjoyed and stay tuned for more blogs talking about more problems i’ve authored >:)