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
    

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

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

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++){
                    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]);
        }

        System.out.println(ans);

    }

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

}

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

void read() {
  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();

  read();

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

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