When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

drunk_philosopher's blog

By drunk_philosopher, history, 5 years ago, In English

Hello, I am trying to understand the editorial of the following problem

https://www.codechef.com/problems/SETELE

Link to Editorial

https://discuss.codechef.com/t/setele-editorial/13549

I understand the editorial completely except for the reduced formula to calculate the expected value.

It's Cmst — (sum of maximum cost edge across all paths)/T where T is n(n+1)/2.

I don't understand how the editorialist arrived at this. Can anybody provide an intuition behind this? Thanks in advance!