HackerRank Extremum Permutations Problem Solution

HackerRank Extremum Permutations Solution

Posted on By Yashwant Parihar No Comments on 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
HackerRank Extremum Permutations Problem Solution
HackerRank Extremum Permutations Problem Solution

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)
c, C#, C++, HackerRank Solutions, java, javascript, python Tags:, , , , , ,

Related Posts

HackerRank The Grid Search Problem Solution HackerRank The Grid Search Problem Solution c
HackerRank Angry Professor Problem Solution HackerRank Angry Professor Problem Solution c
HackerRank Palindrome Index Problem Solution HackerRank Palindrome Index Problem Solution c
HackerRank Kingdom Division Problem Solution HackerRank Kingdom Division Problem Solution c
HackerRank Beautiful Quadruples Problem Solution HackerRank Beautiful Quadruples Problem Solution c
HackerRank Animal Transport Problem Solution HackerRank Animal Transport Problem Solution C++

Leave a Reply

Your email address will not be published. Required fields are marked *