思考题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

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