思考题so late?

Dazzit Again

This is an easy version of OBCYSIO 28)

You are given an integer sequence A of length N and another sequence B of length M. Then imagine a game:

First, you choose exactly M different elements and arrange them, let's call this C. And the enemy will random shuffle B. You all break iff for each .

If you choose optimally, what's the best all break probability you will get?

Example

A={1,2,3,4,5}
B={2,3,5}
Answer= 0.33333333333333
Explain
When you choose 3 4 5:
{3,4,5} vs {2,3,5} all break
{3,4,5} vs {2,5,3} NOT all break because 4<5
{3,4,5} vs {3,2,5} all break
{3,4,5} vs {3,5,2} NOT all break
{3,4,5} vs {5,3,2} NOT all break
{3,4,5} vs {5,2,3} NOT all break

So the answer is 1/3.

Constriants

Solution

It's easy to see that we always choose the maximum M elements from A. Then the problem can be seen as:"How many permutation of B that we will get an all break?"

Let's sort the array C from big to small, then we consider each element in C to be a "slot". An element from B can be placed into a slot if only , and this must be an interval 1~xxx.

We sort the intervals by endpoint. Let's represent sorted invervals as the array X. Then the answer is

For example, if the array C={5,4,3} and B={2,3,5} then X={3,3,1}, after sorted {1,3,3}.

So the answer is