[problem statement here]
This was a problem in my country's informatics olympiad, and I was able to reverse-engineer a solution — although I have no idea how one could make this observation in a contest. The algorithm is as follows:
- Input an array a and b
- Construct an array of the differences between a_i and b_i for each i
- Create a prefix sum array of the difference array
- Sort the prefix sum array
- Get the median of the prefSum array
- For each element p_i in the prefSum array, add the absolute difference between p_i and median to a total
- Output the total
Is this an already-defined type of problem, or could someone walk me through how you would arrive upon a solution? Thank you so much!