# The Special Offer Problem

Here is a problem for the unsuspecting programmer. Makes for a great interview question.

# Problem

You are developing an online store with a shopping cart feature. Right before checkout, the system must show the customer a detailed bill. The bill includes one special offer when some special offer applies to the items in the cart. When more than one special offer applies, the system selects the offer that gives the highest discount.

Your task is to determine if a given special offer applies to the
items in the cart. You are given the identification number of each
item in the cart and the combination of items that correspond to the
special offer. For example, consider cart items `3, 1, 4, 2`

.
Special offer combination `2, 3`

applies to the cart items.
Combination `1, 5`

does not apply to the cart items because item `5`

is not included in the cart.

# Input

The input consists of a number $@1 \le i \le 10000@$ followed by $@i@$ cases. Each case consists of a list of items and a special offer combination. The list of items consists of a sequence of integers separated by spaces and ended by a newline. The list of items is preceded by the count of items $@0 \le n \le 100000@$. The special offer combination has the same format and is preceded by its corresponding count $@0 \le m \le 100000@$. Consider the following example.

# Output

For each case in the input, you must output the word `yes`

on a line
by itself when the special offer applies to the cart, otherwise you
should ouput `no`

. The following output corresponds to the example input.

# Solution

The problem asks that we check multiset inclusion for each case. Consider the following case.

For the case, the special offer applies to the cart. The reason is
that multiset `{1, 1, 2, 4}`

is included in `{1, 1, 2, 3, 4}`

as
illustrated in the following diagram.

The following algorithm checks multiset inclusion on given sorted
sequences for cart `C`

and special offer `S`

. The algorithm returns
true when `S`

is subset of `C`

and false otherwise.

The input sequences may not be sorted. Sort the input before applying
algorithm `CHECK`

.

The end-to-end solution for a given case consists of the following steps.

- Sort the $@n@$ cart items
`C`

. Sorting by merge sort takes $@O(n \log n)@$ steps. - Sort the $@m@$ special offer items
`S`

. Sorting by merge sort takes $@O(m \log m)@$ steps. - Apply algorithm
`CHECK`

. Algorithm`CHECK`

takes $@O(m)@$ steps.

The worst case execution time of the end-to-end method is $@O(n \log n)@$ because $@n \ge m@$.

# Implementation

The following C program implements the solution.