HackerRank Extremum Permutations Solution
In this post, we will solve HackerRank Extremum Permutations Problem Solution.
Let’s consider a permutation P = {p1, p2, …, pN} of the set of N = {1, 2, 3, …, N} elements .
P is called a magic set if it satisfies both of the following constraints:
- Given a set of K integers, the elements in positions a1, a2, …, aK are less than their adjacent elements, i.e., pai-1 > pai < pai+1
- Given a set of L integers, elements in positions b1, b2, …, bL are greater than their adjacent elements, i.e., pbi-1 < pbi > pbi+1
How many such magic sets are there?
Input Format
The first line of input contains three integers N, K, L separated by a single space.
The second line contains K integers, a1, a2, … aK each separated by single space.
the third line contains L integers, b1, b2, … bL each separated by single space.
Output Format
Output the answer modulo 1000000007 (109+7).
Constraints
3 <= N <= 5000
1 <= K, L <= 5000
2 <= ai, bj <= N-1, where i ∈ [1, K] AND j ∈ [1, L]
Sample Input #00
4 1 1
2
3
Sample Output #00
5
Explanation #00
Here, N = 4 a1 = 2 and b1 = 3. The 5 permutations of {1,2,3,4} that satisfy the condition are
- 2 1 4 3
- 3 2 4 1
- 4 2 3 1
- 3 1 4 2
- 4 1 3 2
Sample Input #01
10 2 2
2 4
3 9
Sample Output #01
161280
Extremum Permutations C Solution
#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
int o[5000]={0};
long long dp[5000][5000]={0};
int main(){
int N,K,L,x,i,j;
long long sum;
scanf("%d%d%d",&N,&K,&L);
for(i=0;i<K;i++){
scanf("%d",&x);
if(o[x-1]==1){
printf("0");
exit(0);
}
o[x-1]=-1;
if(o[x]==-1){
printf("0");
exit(0);
}
o[x]=1;
}
for(i=0;i<L;i++){
scanf("%d",&x);
if(o[x-1]==-1){
printf("0");
exit(0);
}
o[x-1]=1;
if(o[x]==1){
printf("0");
exit(0);
}
o[x]=-1;
}
dp[0][0]=1;
for(i=1;i<N;i++){
sum=0;
switch(o[i]){
case 0:
for(j=0,sum=0;j<i;j++)
sum=(sum+dp[i-1][j])%MOD;
for(j=0;j<=i;j++)
dp[i][j]=sum;
break;
case -1:
for(j=i-1,sum=0;j>=0;j--){
sum=(sum+dp[i-1][j])%MOD;
dp[i][j]=sum;
}
break;
default:
for(j=0,sum=0;j<i;j++){
sum=(sum+dp[i-1][j])%MOD;
dp[i][j+1]=sum;
}
}
}
for(i=0,sum=0;i<N;i++)
sum=(sum+dp[N-1][i])%MOD;
printf("%lld",sum);
return 0;
}
Extremum Permutations C++ Solution
#include <bits/stdc++.h>
using namespace std;
#define ULL unsigned long long
#define LF __float128
#define MOD 1000000007
int main() {
int N, K, L;
cin >> N >> K >> L;
vector<bool> LMin(N + 1, false);
vector<bool> LMax(N + 1, false);
for (int i = 0; i < K; i++) {
int A;
cin >> A;
LMin[A] = true;
LMax[A + 1] = true;
}
for (int i = 0; i < L; i++) {
int A;
cin >> A;
LMax[A] = true;
LMin[A + 1] = true;
}
vector<vector<ULL>> DP(N + 1, vector<ULL>(N + 1, 0));
DP[1][1] = 1;
for (int i = 2; i <= N; i++) {
if (LMin[i] && LMax[i]) {
cout << 0;
return 0;
}
if (LMin[i]) {
ULL S = 0;
for (int j = i; j >= 1; j--) {
DP[i][j] = S;
S = (S + DP[i - 1][j - 1]) % MOD;
}
} else if (LMax[i]) {
ULL S = 0;
for (int j = 1; j <= i; j++) {
DP[i][j] = S;
S = (S + DP[i - 1][j]) % MOD;
}
} else {
ULL S = 0;
for (int j = 1; j <= i; j++) {
S = (S + DP[i - 1][j]) % MOD;
}
for (int j = 1; j <= i; j++) {
DP[i][j] = S;
}
}
}
ULL ans = 0;
for (int i = 1; i <= N; i++) {
ans = (ans + DP[N][i]) % MOD;
}
//
// for (int i = 1; i <= N; i++) {
// cout << LMin[i] << " " << LMax[i] << endl;
// }
// cout << endl;
//
// for (int i = 1; i <= N; i++) {
// for (int j = 1; j <= N; j++) {
// cout << DP[i][j] << " ";
// }
// cout << endl;
// }
cout << ans;
return 0;
}
Extremum Permutations C Sharp Solution
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;
class Result
{
private enum ExtremumType {
Peak,
Valley
}
private class Extremum {
public int Index { get; init; }
public ExtremumType Type { get; init; }
}
private const long m = 1000000007;
/*
* Complete the 'extremumPermutations' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER n
* 2. INTEGER_ARRAY a
* 3. INTEGER_ARRAY b
*/
public static int extremumPermutations(int n, int[] peaks, int[] valleys)
{
checked {
peaks = peaks.Distinct().ToArray();
valleys = valleys.Distinct().ToArray();
if (peaks.Intersect(valleys).Any()) {
return 0;
}
Array.Sort(peaks);
Array.Sort(valleys);
for (var i = 1; i < peaks.Length; ++i) {
if (peaks[i] == peaks[i - 1] + 1) {
return 0;
}
}
for (var i = 1; i < valleys.Length; ++i) {
if (valleys[i] == valleys[i - 1] + 1) {
return 0;
}
}
var peakExtremums =
peaks.Select(p => new Extremum { Index = p, Type = ExtremumType.Peak });
var valleyExtremums =
valleys.Select(v => new Extremum { Index = v, Type = ExtremumType.Valley });
var extremums = peakExtremums.Concat(valleyExtremums).OrderBy(e => e.Index).ToArray();
var ctr = 1L;
var setSize = n;
var dpPrev = new long[n];
var dpCur = new long[n];
if (extremums.Length > 0) {
if (extremums[0].Type == ExtremumType.Peak) {
dpPrev[0] = setSize - 1;
for (var i = 1; i < setSize - 2; ++i) {
dpPrev[i] = dpPrev[i - 1] + (setSize - i - 1);
}
} else {
dpPrev[setSize - 3] = setSize - 1;
for (var i = setSize - 4; i >= 0; --i) {
dpPrev[i] = dpPrev[i + 1] + (i + 2);
}
}
setSize -= 3;
}
for (var i = 1; i < extremums.Length; ++i) {
if (extremums[i].Index == extremums[i - 1].Index + 2) {
if (extremums[i].Type == ExtremumType.Peak) {
dpCur[setSize - 2] = (dpPrev[setSize - 1] + dpPrev[setSize]) % m;
for (var j = setSize - 3; j >= 0; --j) {
dpCur[j] = (dpCur[j + 1] + dpPrev[j + 1]) % m;
}
for (var j = 1; j < setSize - 1; ++j) {
dpCur[j] = (dpCur[j] + dpCur[j - 1]) % m;
}
} else {
dpCur[0] = (dpPrev[0] + dpPrev[1]) % m;
for (var j = 1; j < setSize - 1; ++j) {
dpCur[j] = (dpCur[j - 1] + dpPrev[j + 1]) % m;
}
for (var j = setSize - 3; j >= 0; --j) {
dpCur[j] = (dpCur[j] + dpCur[j + 1]) % m;
}
}
(dpCur, dpPrev) = (dpPrev, dpCur);
setSize -= 2;
} else if (extremums[i].Index == extremums[i - 1].Index + 1) {
if (extremums[i].Type == ExtremumType.Peak) {
dpCur[0] = dpPrev[0];
for (var j = 1; j < setSize; ++j) {
dpCur[j] = (dpCur[j - 1] + dpPrev[j]) % m;
}
} else {
dpCur[setSize - 1] = dpPrev[setSize];
for (var j = setSize - 2; j >= 0; --j) {
dpCur[j] = (dpCur[j + 1] + dpPrev[j + 1]) % m;
}
}
(dpCur, dpPrev) = (dpPrev, dpCur);
--setSize;
} else {
ctr = (ctr * (dpPrev.Take(setSize + 1).Sum() % m)) % m;
if (extremums[i].Type == ExtremumType.Peak) {
dpPrev[0] = setSize - 1;
for (var j = 1; j < setSize - 2; ++j) {
dpPrev[j] = dpPrev[j - 1] + (setSize - j - 1);
}
} else {
dpPrev[setSize - 3] = setSize - 1;
for (var j = setSize - 4; j >= 0; --j) {
dpPrev[j] = dpPrev[j + 1] + (j + 2);
}
}
setSize -= 3;
}
}
ctr = (ctr * (dpPrev.Take(setSize + 1).Sum() % m)) % m;
ctr = (ctr * Factorial(setSize)) % m;
return (int)ctr;
}
}
private static long Factorial(int n) {
checked {
var result = 1L;
for (var i = n; i > 1; --i) {
result = (result * i) % m;
}
return result;
}
}
}
class Solution
{
public static void Main(string[] args)
{
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' ');
int n = Convert.ToInt32(firstMultipleInput[0]);
int k = Convert.ToInt32(firstMultipleInput[1]);
int l = Convert.ToInt32(firstMultipleInput[2]);
var a = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(aTemp => Convert.ToInt32(aTemp) - 1).ToArray();
var b = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(bTemp => Convert.ToInt32(bTemp) - 1).ToArray();
int result = Result.extremumPermutations(n, b, a);
textWriter.WriteLine(result);
textWriter.Flush();
textWriter.Close();
}
}
Extremum Permutations Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'extremumPermutations' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER n
* 2. INTEGER_ARRAY a
* 3. INTEGER_ARRAY b
*/
public static int extremumPermutations(int n, List<Integer> A, List<Integer> B) {
int k = A.size();
int l = B.size();
int[] a = new int[5005];
int[] b = new int[5005];
long[][] dp = new long[5005][5005];
for (int i = 0; i < k; i++) {
a[A.get(i)] = 1;
}
for (int i = 0; i < l; i++) {
b[B.get(i)] = 1;
}
for (int i = 1; i < n; i++) {
if (a[i] == 1 && b[i] == 1){
//System.out.println(0);
return 0;
}
if ((a[i-1] == 1 && a[i] == 1) || (b[i-1]==1 && b[i] == 1)){
//System.out.println(0);
return 0;
}
}
dp[1][1] = 1;
for (int i = 2; i <= n; i++){
if (!(a[i-1] == 1 || b[i] == 1)){
long sum = 0;
for (int j=1; j <= i; j++){
dp[i][j] = add(dp[i][j], sum);
sum = add(sum, dp[i-1][j]);
}
}
if (!(b[i-1] == 1 || a[i] == 1)){
long sum = 0;
for (int j=i; j>=1; j--){
dp[i][j] = add(dp[i][j], sum);
sum = add(sum, dp[i-1][j-1]);
}
}
}
long ans = 0;
for (int i = 1; i <= n; i++){
ans = add(ans, dp[n][i]);
}
return (int) ans;
}
private static long add(long x, long v){
return (x+v) % 1000000007;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
int n = Integer.parseInt(firstMultipleInput[0]);
int k = Integer.parseInt(firstMultipleInput[1]);
int l = Integer.parseInt(firstMultipleInput[2]);
List<Integer> a = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList());
List<Integer> b = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList());
int result = Result.extremumPermutations(n, a, b);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}
Extremum Permutations JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());
main();
});
function readLine() {
return inputString[currentLine++];
}
function extremumPermutations(n, a, b) {
var k = a.length, l = b.length;
var greater = new Array(n).fill(false), less = new Array(n).fill(false);
var i, j;
for (i = 0; i < k; i++) {
less[a[i] - 1] = true;
greater[a[i]] = true;
}
for (i = 0; i < l; i++) {
greater[b[i] - 1] = true;
less[b[i]] = true;
}
var dp = Array.from(Array(n), () => new Array(n).fill(0));
dp[0][0] = 1;
for (i = 1; i < n; i++) {
var suml = 0, sumr = 0;
if (!less[i])
for (j = 1; j <= i; j++) {
suml += dp[i - 1][j - 1];
dp[i][j] += suml % 1000000007;
}
if (!greater[i])
for (j = i - 1; j >= 0; j--) {
sumr += dp[i - 1][j];
dp[i][j] += sumr % 1000000007;
}
}
var result = dp[n - 1].reduce((a, b) => a + b);
return (result % 1000000007);
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const nkl = readLine().split(' ');
var n = parseInt(nkl[0], 10);
var k = parseInt(nkl[1], 10);
var l = parseInt(nkl[2], 10);
const a = readLine().split(' ').map(aTemp => parseInt(aTemp, 10));
const b = readLine().split(' ').map(bTemp => parseInt(bTemp, 10));
let result = extremumPermutations(n, a, b);
ws.write(result + "\n");
ws.end();
}
Extremum Permutations Python Solution
import sys
N, K, L = map(int,input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))
M = int(1e9 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)
for i in mins:
if direction[i - 1] == UP or direction[i] == DOWN:
print("0")
sys.exit(0)
direction[i - 1] = DOWN
direction[i] = UP
for i in maxs:
if direction[i - 1] == DOWN or direction[i] == UP:
print("0")
sys.exit(0)
direction[i - 1] = UP
direction[i] = DOWN
f = []
for i in range(N + 1):
f.append([0] * (N + 1))
def interval(a, b):
if a <= b:
return range(a, b + 1)
else:
return range(a, b - 1, -1)
f[N][0] = 1
i = N - 1
while i > 0:
if direction[i] == UP:
f[i][0] = 0
for n in interval(1, N - i):
f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M
elif direction[i] == DOWN:
f[i][N - i] = 0
for n in interval(N - i - 1, 0):
m = N - i - n
f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M
elif direction[i] == ANY:
s = 0
for k in interval(0, N - (i + 1)):
s += f[i + 1][k]
s %= M
for n in interval(0, N - i):
f[i][n] = s
i -= 1
ret = 0
for k in interval(0, N - 1):
ret += f[1][k]
ret %= M
print(ret)