CCC 2020 S5: Josh’s Double Bacon Deluxe

DP problems.

• They choose the coach’s burger. In this case, no further disruptions are caused and Josh gets his burger.

• They choose Josh’s burger. In this case, no further disruptions are caused and Josh doesn't get his burger.

• They choose someone else’s burger and create another disruption.

Optimal subquestion:

The ith person can get his favourite burger. Assume b[] is the list that is each person's favourite burger. b[0] is coach, b[n-1] is Josh.

f(i) = 1 if b[i] = b[0]

f[i] = f[last[i]] if b[i] is in the last list that is the most right side person faourite burger that is same as ith

f[i] = (1+c)/(n-i) , c is the sum of problity of from n-2 to i.

The result is (1+c)/n.

import sys
input = sys.stdin.readline

n = int(input())
b = list(map(int, input().split()))
dp = [0] * n
c = 0
last = {b[-1]: n - 1}
if b[-1] == b[0]:
    dp[-1] = 1
    c += 1
    print("{:.8f}".format(c))
else:
    for i in range(n - 2, -1, -1):
        if b[i] == b[0]:
            dp[i] = 1
        elif b[i] in last:
            dp[i] = dp[last[b[i]]]
        else:
            dp[i] = (1 + c) / (n - i)
        c += dp[i]
        if b[i] not in last:
            last[b[i]] = i

    print("{:.8f}".format(c / n))

This is 15 marks solution.