Morphling

SRM 660 · 2015-05-01 · by subscriber

SRM 660 · 2015-05-01 · by subscriber · Brute Force, Dynamic Programming

Show categories

Class Name: Morphling

Return Type: int

Method Name: findsz

Arg Types: (int, int)

Problem Statement

You are given the ints N and K.

Let S be the set of all arrays that have the following properties:

The length of the array is exactly N.
Each element in the array is an integer between 1 and N, inclusive.
Each number occurs in the array at most K times.

Morphing an array A is an operation that consists of three steps:

Choose two distinct integers x and y, each between 1 and N, inclusive.
Change the values of some elements of A: All elements of A that had the value x will now have the value y and vice versa.
Finally, swap two elements of A: the elements with the 1-based indices x and y.

For example, suppose that A = [1,3,3,4]. One possible morphing of this array will look as follows:

We choose x=1 and y=3.
After changing the values in A, we have the array [3,1,1,4].
Then, after the swap we have the final result: the array [1,1,3,4].

Note that if we morph an array that belongs into S, the result will always belong into S as well.

We are interested in a subset T of S with the property that any array in S can be produced from some array in T by a sequence of zero or more morphing operations. Find the smallest possible size of such subset T, and return its size modulo 1,000,000,007.

Constraints

N will be between 1 and 100, inclusive.
K will be between 1 and min(25, N), inclusive.

Examples

1
1
Returns: 1

The only valid array is [1]. The subset T must contain this array.

2
1
Returns: 2

There are two arrays in S: [1,2] and [2,1]. The morphing operation always changes [1,2] into [1,2] and it always changes [2,1] into [2,1]. Therefore we need to include both arrays into T.

2
2
Returns: 3

There are four arrays in S: [1,2], [2,1], [1,1], [2,2]. The morphing operation allows to transform [1,1] to [2,2], so only one of this should be included into T.

3
1
Returns: 3

3
3
Returns: 7

Here the set S contains 27 different arrays. Some of these arrays can be produced from other arrays by morphing. The smallest possible subset T with the required property consists of only 7 of these arrays.

Submissions are judged against all 93 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Morphling with a public method int findsz(int N, int K) · 93 test cases · 2 s / 256 MB per case