Freaks City

Notation Let \(dp_i\) denote the expected number of attempts to correctly play the prefix \(1 \to i\), with \(dp_1 = n\). The target melody is given by the array \(target_i\). Analysis When playing a melody, the current partially correct sequence falls into one of two cases: The current suffix matches some prefix of the melody. No suffix of ...

A player collects trading cards with n distinct types. Each draw yields card type i with probability pi. Duplicate cards convert to coins, where k coins can be exchanged for one missing card. The process continues until all card types are collected. Compute the expected number of draws required. Input Format First line: n (card types) and k (co ...