Hello everyone,Today, I was working on the CSES Stick Lengths problem, where the solution involves using the median as the optimal value for each element. This got me thinking: what if instead of the median, I used one of the following three values? Which type of deviation or cost would be minimized?
- Ceiling value of the mean
- Floor value of the mean
- Rounded value of the mean
I initially asked ChatGPT about it, but the explanation left me a bit confused. I’m curious to hear your insights on this. Thanks in advance!
Choosing the mean of a set of values minimises the squared differences. The proof is already shown here, so I won't rewrite it. I think if the mean isn't a whole number and you have to choose an integer value, the rounded value would be optimal since it's closer to the local minimum and the curve is symmetric.
Thanks bro, this was very helpful :)