# HackerRank Extremum Permutations problem solution

In this 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:

1. 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
2. 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?

## Problem solution in Python.

from itertools import islice, accumulate

MOD = 10**9 + 7

def permcount(permlen, a, b):
if any(x+1 == y for c in map(sorted, (a, b)) for x, y in zip(c, c[1:])):
return 0
if set(a) & set(b):
return 0
goingup = [None] * permlen
for c, low in ((a, True), (b, False)):
for elt in c:
elt -= 1
if elt > 0:
goingup[elt] = not low
if elt < permlen - 1:
goingup[elt+1] = low
count = [1]
for i, inc in islice(enumerate(goingup), 1, permlen):
if inc is None:
count = [sum(count)] * (i+1)
elif inc:
count = [0] + list(accumulate(count))
else:
count = list(reversed(list(accumulate(reversed(count))))) + [0]
count = [elt % MOD for elt in count]
return sum(count) % MOD

return [int(f) for f in input().split()]

assert len(a) == alen and len(b) == blen
print(permcount(permlen, a, b))

{"mode":"full","isActive":false}

## Problem solution in Java.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int l = in.nextInt();
int[] a = new int[5005];
int[] b = new int[5005];
long[][] dp = new long[5005][5005];

for (int i = 0; i < k; i++) {
a[in.nextInt()] = 1;
}

for (int i = 0; i < l; i++) {
b[in.nextInt()] = 1;
}

for (int i = 1; i < n; i++) {
if (a[i] == 1 && b[i] == 1){
System.out.println("0");
return;
}
if ((a[i-1] == 1 && a[i] == 1) || (b[i-1]==1 && b[i] == 1)){
System.out.println("0");
return;
}
}

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++){
}
}
if (!(b[i-1] == 1 || a[i] == 1)){
long sum = 0;
for (int j=i; j>=1; j--){
}
}
}

long ans = 0;
for (int i = 1; i <= n; i++){
}

System.out.println(ans);

}

private static long add(long x, long v){
return (x+v) % 1000000007;
}

}

{"mode":"full","isActive":false}

## Problem solution in C++.

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define PB push_back
#define F first
#define S second

#define REP(i, from, to) for (auto i = (from); i <= (to); ++i)
#define PER(i, from, to) for (auto i = (from); i >= (to); --i)
#define REP_IF(i, from, to, assert)                                            \
for (auto i = (from); i <= (to); ++i)                                        \
if (assert)

#define FOR(i, less_than) for (auto i = 0; i < (less_than); ++i)
#define FORI(i, container) for (auto i = 0; i < (container).size(); ++i)
#define FORI_IF(i, container, assert)                                          \
for (auto i = 0; i < (container).size(); ++i)                                \
if (assert)
#define ROFI(i, container) for (auto i = SZ(container) - 1; i >= 0; --i)

#define FOREACH(elem, container) for (auto elem : (container))
#define MEMSET(container, value) memset(container, value, sizeof(container))
#define MEMSET0(container) memset(container, 0, sizeof(container))
#define FILL(container, value) fill(container.begin(), container.end(), value)
#define FILL0(container) fill(container.begin(), container.end(), 0)
#define ALL(container) (container).begin(), (container).end()
#define SZ(container) (int)((container).size())

#define BACK(set_map) *prev((set_map).end(), 1)
#define FRONT(set_map) *(set_map).begin()

#define POP(var, container)                                                    \
auto var = (container.front());                                              \
container.pop();

using PII = std::pair<int, int>;
using LL = long long;
using VI = std::vector<int>;
using CVI = const VI;
using VLL = std::vector<LL>;
using VVI = std::vector<VI>;
using VVLL = std::vector<VLL>;

using namespace std;

const int M = 1e9 + 7;
const int N = 5007;

int tag[N];
LL C[N][N];
int n;
VVI a;
bool boom = false;

void init() {
ios::sync_with_stdio(false);
MEMSET0(tag);
}

cin >> n;
int k, l;
cin >> k >> l;
for (int x, i = 0; i < k; ++i) {
cin >> x;
tag[x] = -1;
}

for (int x, i = 0; i < l; ++i) {
cin >> x;
if (tag[x]==-1) {
boom = true;
break;
}
tag[x] = 1;
}

REP(i, 1, n - 1)
if (tag[i] && tag[i] == tag[i + 1]) {
boom = true;
return;
}

for (int j = 1, i = 1; i <= n; i = j)
if (tag[i] || tag[i + 1]) {
VI seg{0, 1};
j = i + 1;
while (j <= n) {
if (tag[j])
seg.PB(tag[j]);
else if (tag[j - 1])
seg.PB(-tag[j - 1]);
else
break;
++j;
}
a.PB(move(seg));
} else {
j = i + 1;
}
}

int dp(CVI &a) {
int n = SZ(a) - 1;
VVLL f(n + 1, VLL(n + 1));
VLL s(n + 1);
f[1][1] = s[1] = 1;
REP(i, 2, n) {
if (a[i] == 1)
REP(j, 1, i)
f[i][j] = s[j - 1];
else REP(j, 1, i) f[i][j] = (s[i - 1] - s[j - 1] + M) % M;
REP(j, 1, i)
s[j] = (s[j - 1] + f[i][j]) % M;
}
return s[n];
}

void comb() {
C[1][1] = 1;
REP(i, 2, n) {
C[i][1] = i;
REP(j, 2, i)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % M;
}
}

int main() {
init();

comb();

if (boom) {
cout << 0 << endl;
} else {
LL ans = 1;
FOREACH(&seg, a) {
ans = (ans * dp(seg)) % M;
ans = (ans * C[n][SZ(seg) - 1]) % M;
n -= SZ(seg) - 1;
}

REP(x, 2, n)
ans = (ans * x) % M;

cout << ans << endl;
}
return 0;
}

{"mode":"full","isActive":false}

## Problem solution in C.

#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;
}

{"mode":"full","isActive":false}