Connection Status:
Competition Arena > AlienAndPermutation

AlienAndPermutation

SRM 605 · 2013-12-22 · by Witaliy

SRM 605 · 2013-12-22 · by Witaliy · Dynamic Programming
Class Name: AlienAndPermutation
Return Type: int
Method Name: getNumber
Arg Types: (vector<int>, int)
Problem Statement

Problem Statement

Note that in this problem you are given a int[] that can contain up to 200 elements. You should also be able to submit test cases of this size during the Challenge phase of this SRM.

Alien Fred wants to destroy the Earth. But before he does that, he wants to play with a permutation.

Fred has a permutation of all the integers between 1 and N, inclusive. You are given a int[] P of size N. For each i, the i-th element (0-based index) of P represents the i-th element (again, 0-based index) of Fred's permutation.

Fred will now make a sequence of changes to P. Each change will look as follows: Fred will select a contiguous non-empty segment of P, and change all of its elements to the largest one among them. (Note that after such a change P will most likely stop being a permutation. This is allowed.)

You are also given an int K. Fred is allowed to make at most K consecutive changes to P. He is allowed to make fewer than K changes if he wants to, including the possibility to make no changes at all.

Let X be the total number of different sequences he can produce at the end of the above process. Return the value (X modulo 1,000,000,007).

Constraints

  • P will contain between 1 and 200 elements, inclusive.
  • P will represent a permutation of integers between 1 and N, inclusive, where N is the number of elements in P.
  • K will be between 0 and 200, inclusive.
Examples
0)
{1, 2}
1
Returns: 2

The following two sequences are possible in this case: (1, 2) and (2, 2).

1)
{3, 1, 2}
2
Returns: 4

Four sequences are possible in this case: (3, 1, 2) (3, 2, 2) (3, 3, 2) (3, 3, 3)

2)
{4, 3, 2, 1}
2
Returns: 13
3)
{1, 7, 2, 3, 6, 4, 5}
3
Returns: 77
4)
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
12
Returns: 379796836

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

Coding Area

Language: C++17 · define a public class AlienAndPermutation with a public method int getNumber(vector<int> P, int K) · 77 test cases · 2 s / 256 MB per case

Submitting as anonymous