Team Formation

  • + 0 comments

    For this problem, I think I got the right output. Test 0 seems to pass. But the test is invalidated. Any reasons why ?

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    char* readline(); char** split_string(char*);

    define MAX_TEAMS 10

    int *teams[MAX_TEAMS];

    /* * Return number in num and number of positions shifted * in the string is returned. */ int get_num(int *num, char *s) { char *s1 = s; int pos = 0;

    *num = 0;
    int neg = 0;
    
    while ((*s1 != ' ') && (*s1 != '\n') && (*s1 != 0)) {
        if (*s1 == '-') {
            neg = 1;
        } else {
            *num = *num * 10 + *s1 - '0';
        }
        s1++;
        pos++;
    }
    if (neg)
        *num = -1 * *num;
    pos++;
    
    return pos;
    

    }

    void insert(int *ar, int rightIndex, int value) { int index = rightIndex;

    for (; index >= 0 && ar[index] > value; index--) {
        ar[index + 1] = ar[index];
    }
    ar[index + 1] = value;
    

    } void insertionSort(int cnt, int *ar) { for (int i = 1; i < cnt; i++) { if (ar[i - 1] > ar[i]) { insert(ar, i - 1, ar[i]); } } } int *sort_numbers(int *cnt, char *s) { char **ar_temp = split_string(s); char *ar_temp_str = *ar_temp; int *array;

    ar_temp_str += get_num(cnt, ar_temp_str);
    array = malloc(sizeof(int)* *cnt);
    if (array == NULL) {
        return NULL;
    }
    bzero(array, sizeof(int)* *cnt);
    for (int i = 0; i < *cnt; i++) {
        ar_temp_str += get_num(&array[i], ar_temp_str);
    }
    insertionSort(*cnt, array);
    return array;
    

    }

    int print_largest_smaller_team_size(char *s) { int cnt; int team_num = 0; int *sorted_array = sort_numbers(&cnt, s);

    teams[team_num++] = &sorted_array[0];
    for (int i = 1; i < cnt; i++) {
        if ((sorted_array[i] - sorted_array[i - 1]) == 1) {
            continue;
        }
        teams[team_num++] = &sorted_array[i];
    }
    if (team_num == 1) {
        return cnt;
    }
    if (team_num == 2) {
        int ret;
        int team1_sz = teams[1] - teams[0];
        if (team1_sz < (cnt - team1_sz)) {
            ret = team1_sz;
        } else {
            ret = (cnt - team1_sz);
        }
        return ret;
    }
    int max = INT_MIN, sec_max = INT_MIN;
    
    for (int i = 1; i < team_num; i++) {
        int c = &teams[i] - &teams[i - 1];
    
        if (c > max) {
            max = c;
        }
    }
    
    for (int i = 1; i < team_num; i++) {
        int c = &teams[i] - &teams[i - 1];
    
        if ((c > sec_max) && (sec_max != max)) {
            sec_max = c;
        }
    }
    return sec_max;
    

    }

    int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
    
    char* ar_count_endptr;
    char* ar_count_str = readline();
    int ar_count = strtol(ar_count_str, &ar_count_endptr, 10);
    
    if (ar_count_endptr == ar_count_str || *ar_count_endptr != '\0') { exit(EXIT_FAILURE); }
    
    int *array = malloc (sizeof(int)*ar_count);
    if (array == NULL) {
        return -1;
    }
    for (int i = 0; i < ar_count; i++) {
        array[i] = print_largest_smaller_team_size(readline());
    }
    for (int i = 0; i < ar_count; i++) {
        printf("%d\n", array[i]);
    }
    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; }
    
        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);
    
        if (!data) { break; }
    
        alloc_length = new_length;
    }
    
    if (data[data_length - 1] == '\n') {
        data[data_length - 1] = '\0';
    }
    
    data = realloc(data, data_length);
    
    return data;
    

    }

    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;
    

    }