Cerinta completa

Watson gave Sherlock a collection of arrays . Here each is an array of variable length. It is guaranteed that if you merge the arrays into one single array, you’ll get an array, , of distinct integers in the range .

Watson asks Sherlock to merge into a sorted array. Sherlock is new to coding, but he accepts the challenge and writes the following algorithm:

  • (an empty array).

  • number of arrays in the collection .

  • While there is at least one non-empty array in :

    • (an empty array) and .

    • While :

      • If is not empty:
        • Remove the first element of and push it to .
      • .

    • While is not empty:

      • Remove the minimum element of and push it to .

  • Return as the output.

Let’s see an example. Let V be .

image

The image below demonstrates how Sherlock will do the merging according to the algorithm:

image

Sherlock isn’t sure if his algorithm is correct or not. He ran Watson’s input, , through his pseudocode algorithm to produce an output, , that contains an array of integers. However, Watson forgot the contents of and only has Sherlock’s with him! Can you help Watson reverse-engineer to get the original contents of ?

Given , find the number of different ways to create collection such that it produces when given to Sherlock’s algorithm as input. As this number can be quite large, print it modulo .

Notes:

  • Two collections of arrays are different if one of the following is true:

    • Their sizes are different.
    • Their sizes are the same but at least one array is present in one collection but not in the other.

  • Two arrays, and , are different if one of the following is true:

    • Their sizes are different.
    • Their sizes are the same, but there exists an index such that .

Input Format

The first line contains an integer, , denoting the size of array .
The second line contains space-separated integers describing the respective values of .

Constraints

Output Format

Print the number of different ways to create collection , modulo .

Sample Input 0

3
1 2 3

Sample Output 0

4

Explanation 0

There are four distinct possible collections:

  4. .

Thus, we print the result of as our answer.

Sample Input 1

2
2 1

Sample Output 1

1

Explanation 1

The only distinct possible collection is , so we print the result of as our answer.

Limbajul de programare folosit: cpp14

Cod:

#include <bits/stdc++.h>
#define MOD 1000000007

using namespace std;
long long int npkv[1400][1400], dp[1400][1400];
int m[1400], n;

long long int npk(int x, int k) {
	if(k<0 || k>x)
		return 0;
	if(x==0)
		return 1;
	if(npkv[x][k] != -1)
		return npkv[x][k];
	npkv[x][k] = 1;
  for(int i=0; i<k; i++)
    npkv[x][k] = (npkv[x][k] * (x-i))%MOD;
	return npkv[x][k];
}

long long int getdp(int x, int np) {
	if(np == 0)
		return 0;
	if(x == n)
		return 1;
	if(dp[x][np] != -1)
		return dp[x][np];
	dp[x][np] = 0;
   	for(int i=x+1; i-x<=np && i<=n; i++) {
   		dp[x][np] = (dp[x][np]+npk(np, i-x)*getdp(i, i-x))%MOD;
   		if(i<n && m[i] < m[i-1])
   			break;
   	}
   	return dp[x][np];
}

int main(){
    cin >> n;
    for(int m_i = 0; m_i < n; m_i++){
       cin >> m[m_i];
    }
    int mxnp=0;
   	for(mxnp=1; mxnp<=n; mxnp++) {
   		if(mxnp<n && m[mxnp] < m[mxnp-1])
   			break;
   	}
   	for(int i=0; i<=n; i++)
      for(int j=0; j<=n; j++) {
   			dp[i][j] = -1;
   			npkv[i][j] = -1;
   		}
    long long int sum=0;
   	for(int i=1; i<=n; i++) {
   		
   		sum = (sum+getdp(i, i))%MOD;
   		if(i<n && m[i] < m[i-1])
   			break;
   	}
    
   	cout << sum << endl;
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464647522

Link challenge: https://www.hackerrank.com/challenges/sherlocks-array-merging-algorithm/problem

Sherlock’s Array Merging Algorithm