P8394 [BalticOI 2022] Boarding Passes (Day2)

After successfully following the local customs, you arrive just in time for the ship’s departure. However, you did not expect so many people to be heading to Lübeck! Since you do not want to be late for the award ceremony (you still need some time to store all the stolen artworks in the hotel), you want to speed up the boarding process. There is a row of $n$ seats on the ship, and all seats are booked by $n$ passengers. Each passenger has a boarding pass that shows their assigned seat and one of $g$ boarding groups. During boarding, only one group is called at a time. Within each boarding group, passengers board in a random order, meaning that all possible boarding orders are equally likely. Each passenger may board either in front of the first seat or behind the last seat, and then move to their assigned seat before the next passenger boards. You have identified that the most time-consuming part of this process is when a passenger has to pass by passengers who are already seated (luggage filled with all those ties is quite an obstacle in the aisle). Fortunately, you find a crew uniform in a nearby locker, so you can decide the order in which groups board, and before boarding starts you can tell each passenger whether to board from the front of all seats or from the back. Write a program that, using the boarding pass information, computes the minimum possible expected number of times a passenger has to pass by already seated passengers during boarding, assuming you choose the boarding order of the groups and assign passengers to board from the very front or the very back. ### Note Given a boarding order of the groups and an assignment of passengers to the front and the back, the expected number of times a passenger has to pass by already seated passengers is defined as: $$1\cdot p_1+2\cdot p_2+3\cdot p_3+\ldots$$ where $p_k$ is the probability that, during boarding, the number of times a passenger has to pass by already seated passengers is exactly $k$. In other words, this is the average number of such pass-bys over all possible passenger boarding orders within each boarding group.

The input contains a string $s_1 \dots s_n$ of $n$ characters, where $s_i$ is one of the first $g$ uppercase English letters, indicating the boarding group of the passenger sitting in seat $i$ (the frontmost seat is seat $1$).

Output a real number: the minimum possible expected number of times a passenger has to pass by already seated passengers, after choosing the boarding order of the groups and assigning passengers to board from the very front or the very back. Your output is considered correct if its absolute error is at most $0.001$.

For all testdata, $1\le g\le 15$, $1\le n \le 10^5$. Translated by ChatGPT 5