We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Extremum Permutations
  5. Discussions

Extremum Permutations

Sort by

recency

|

16 Discussions

|

  • 23A91A1244
     + 0 comments

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    char* readline(); char* ltrim(char*); char* rtrim(char*); char** split_string(char*);

    int parse_int(char*);

    /* * 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 */

    int extremumPermutations(int n, int a_count, int* a, int b_count, int* b) {

    }

    int main() { FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char** first_multiple_input = split_string(rtrim(readline()));

int n = parse_int(*(first_multiple_input + 0));

int k = parse_int(*(first_multiple_input + 1));

int l = parse_int(*(first_multiple_input + 2));

char** a_temp = split_string(rtrim(readline()));

int* a = malloc(k * sizeof(int));

for (int i = 0; i < k; i++) {
    int a_item = parse_int(*(a_temp + i));

    *(a + i) = a_item;
}

char** b_temp = split_string(rtrim(readline()));

int* b = malloc(l * sizeof(int));

for (int i = 0; i < l; i++) {
    int b_item = parse_int(*(b_temp + i));

    *(b + i) = b_item;
}

int result = extremumPermutations(n, k, a, l, b);

fprintf(fptr, "%d\n", result);

fclose(fptr);

return 0;

    }

    char* readline() { size_t alloc_length = 1024; size_t data_length = 0;

    char* data = malloc(alloc_length);

while (true) {
    char* cursor = data + data_length;
    char* line = fgets(cursor, alloc_length - data_length, stdin);

    if (!line) {
        break;
    }

    data_length += strlen(cursor);

    if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') {
        break;
    }

    alloc_length <<= 1;

    data = realloc(data, alloc_length);

    if (!data) {
        data = '\0';

        break;
    }
}

if (data[data_length - 1] == '\n') {
    data[data_length - 1] = '\0';

    data = realloc(data, data_length);

    if (!data) {
        data = '\0';
    }
} else {
    data = realloc(data, data_length + 1);

    if (!data) {
        data = '\0';
    } else {
        data[data_length] = '\0';
    }
}

return data;

    }

    char* ltrim(char* str) { if (!str) { return '\0'; }

    if (!*str) {
    return str;
}

while (*str != '\0' && isspace(*str)) {
    str++;
}

return str;

    }

    char* rtrim(char* str) { if (!str) { return '\0'; }

    if (!*str) {
    return str;
}

char* end = str + strlen(str) - 1;

while (end >= str && isspace(*end)) {
    end--;
}

*(end + 1) = '\0';

return str;

    }

    char** split_string(char* str) { char** splits = NULL; char* token = strtok(str, " ");

    int spaces = 0;

while (token) {
    splits = realloc(splits, sizeof(char*) * ++spaces);

    if (!splits) {
        return splits;
    }

    splits[spaces - 1] = token;

    token = strtok(NULL, " ");
}

return splits;

    }

    int parse_int(char* str) { char* endptr; int value = strtol(str, &endptr, 10);

    if (endptr == str || *endptr != '\0') {
    exit(EXIT_FAILURE);
}

return value;

    }

  • yashparihar729
     + 0 comments

    Here is my solution in java, javascript, python, C, C++, Csharp HackerRank Extremum Permutations Solution

  • thecodingsoluti2
     + 0 comments

    Here is Extremum Permutations problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-extremum-permutations-problem-solution.html

  • TChalla
     + 0 comments
    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)

  • auxijanos
     + 0 comments

    My code generates permutations in a recursive way. While a new element is being added to the current permutation, my code checks whether it complients or not to the rules. As far 4 testcases are green, the others got timeout. I don't know how could I fast up my solution. As I see I cannot share my solution here anymore. There is some regulation here.