• + 0 comments

    The editorial has the most inefficient solution to this problem. Three for loops--are you sure? This was my linear python3 solution (I tried to make it as readable as possible and in line with the vars defined in the problem's description):

    def solve(n, y):
        V = 0
        y.sort()
        for i in range(n):
            if i == 0 or (i > 0 and y[i] > y[i-1]): 
                k = n-i
                v_i = (n+1)/(k+1) 
            V += v_i
        return ["%.2f" % V]
    

    This also exercises Linearity of Expectation, but all it's doing is sorting the input array y then walking through it to sum up v_i. If there's a repeating value, it'll use the first instance of v_i for that value (since v_i will continue to decrease as i increases).