Problem link: https://www.spoj.com/problems/ADASEA/
The implementation was pretty straightforward but I couldn’t understand how the expected value would work in this case.
I found a solution here: https://github.com/tr0j4n034/SPOJ/blob/master/ADASEA.cpp
The idea was to find all separate longest paths containing ‘#’ in them and just squaring them and adding it to the answer and finally dividing it by all the cells. Can someone tell me how does this work? Why does squaring all the paths work in this case?