Участник:Easik/make-array-strictly-increasing

Материал из DISCOPAL
Перейти к: навигация, поиск

Сначала написал на на Python3, но решение не прошло по времени. Через пару дней перезапустил и с runtime под 10000мс оно прошло, поэтому прикладываю и его снизу сразу за решением на Си.

C \ gcc

#define INF (int)1e9
 
 
int cmpfun(const void *a, const void *b) {
 
    return *(int *)a - *(int *)b;
 
}
 
 
int makeArrayIncreasing(int* arr1, int arr1Size, int* arr2, int arr2Size){
 
    int i, j, k;
    int tmp, res;
    int min_keep, min_swap;
    int arr2_sorted_set[arr2Size];
    int arr2_set_size;
 
    /* Sort arr2 */
    qsort(arr2, arr2Size, sizeof(int), cmpfun);
 
    /* Keep only unique items in arr2 */
    arr2_set_size = 0;
    for (i = 0; i < arr2Size; i++) {
 
        /* First item */
        if (i == 0) {
 
            arr2_sorted_set[arr2_set_size++] = arr2[i];
 
        /* Other items */
        } else {
 
            /* Add unique item */
            if (arr2[i] != arr2[i - 1]) {
 
                arr2_sorted_set[arr2_set_size++] = arr2[i];
 
            }
        }
 
    }
 
    int keep_arr[arr1Size];         /* Min num of replacements to make arr1 ascending by keeping arr1[i] */
    int swap_arr[arr2_set_size];    /* Min num of replacements to make arr1 ascending by swapping arr1[j] into arr2_sorted_set[i] */
    int tmp_arr[arr2_set_size];
 
    /* Init keep array */
    for (i = 1; i < arr1Size; i++)  keep_arr[i] = INF;
    keep_arr[0] = 0;
 
    /* Init swap array */
    for (i = 0; i < arr2_set_size; i++)  swap_arr[i] = 1;
 
    /* Loop through items of arr1 to count replacements */
    for (i = 1; i < arr1Size; i++) {
 
        /* Reset variables to track min values */
        min_keep = INF;
        min_swap = INF;
 
        /* Reset tmp array */
        for (k = 0; k < arr2_set_size; k++)  tmp_arr[k] = INF;
 
        for (j = 0; j < arr2_set_size; j++) {
 
            if (j > 0) {
 
                min_swap = (min_swap <= swap_arr[j - 1] + 1) ? min_swap : (swap_arr[j - 1] + 1);
 
            }
 
            if (arr1[i] > arr2_sorted_set[j]) {
 
                min_keep = (min_keep <= swap_arr[j]) ? min_keep : swap_arr[j];
 
            }
 
            /* Ascending order [OK]: set the same num of replacements */
            if (arr1[i] > arr1[i - 1]) {
 
                keep_arr[i] = keep_arr[i - 1];
 
            }
 
            /* Increment number of changes necessary */
            if (arr2_sorted_set[j] > arr1[i - 1]) {
 
                tmp_arr[j] = keep_arr[i - 1] + 1;
 
            }
 
            tmp_arr[j] = (tmp_arr[j] <= min_swap) ? tmp_arr[j] : min_swap;
            keep_arr[i] = (keep_arr[i] <= min_keep) ? keep_arr[i] : min_keep;
 
        }
 
        /* Swap arrays */
        for (j = 0; j < arr2_set_size; j++) {
 
            tmp = tmp_arr[j];
            tmp_arr[j] = swap_arr[j];
            swap_arr[j] = tmp;
 
        }
 
    }
 
    /* Calc min swap_arr value */
    tmp = INF;
    for (j = 0; j < arr2_set_size; j++) {
 
        tmp = (tmp <= swap_arr[j]) ? tmp : swap_arr[j];
 
    }
 
    res = (tmp <= keep_arr[arr1Size - 1]) ? tmp : keep_arr[arr1Size - 1];
 
    if (res < INF) {
 
        return res;
 
    } else {
 
        return -1;
 
    }
 
}



Python3

import numpy as np
import math
 
class Solution:
 
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        """
        :type arr1: List[int]
        :type arr2: List[int]
        :rtype: int
        """
 
        # Sort & leave unique values of arr2
        arr2 = sorted(list(set(arr2)))
 
        size1 = len(arr1)
        size2 = len(arr2)
 
        # Store min steps to make arr1 ascending with arr[i] in place
        keep = np.ones(size1) * math.inf
        keep[0] = 0
 
        # Store min steps to make arr1 ascending with arr[i] = b[j], swap indexed w/ j
        swap = np.ones(size2)
 
        # Declare tmp array
        tmp = np.ones(size2)
        tmp_swap = np.zeros(size2)
 
        for i in range(1, size1):
 
            init_keep = math.inf
            init_swap = math.inf
 
            # Init tmp array
            tmp = np.ones(size2) * math.inf
 
            for j in range(size2):
 
                if j > 0:
                    init_swap = min(init_swap, swap[j - 1] + 1)
 
                if arr1[i] > arr2[j]:
                    init_keep = min(init_keep, swap[j])
 
                if arr1[i] > arr1[i - 1]:
                    keep[i] = keep[i - 1]
 
                if arr2[j] > arr1[i - 1]:
                    tmp[j] = keep[i - 1] + 1
 
                tmp[j] = min(tmp[j], init_swap)
                keep[i] = min(keep[i], init_keep)
 
            tmp_swap = swap.copy()
            swap = tmp.copy()
            tmp = tmp_swap.copy()
 
        ret = min(swap.min(), keep[-1])
        if ret >= math.inf:
            return -1
        else:
            return int(ret)

StasFomin 15:04, 15 декабря 2020 (MSK): Ага, хорошо, дополнительные баллы за мультиязыковое решение. Питон у меня тоже чудом прошел с Nой попытки в упор, возможно там можно его оптимизировать — квест для тех, кто захочет улучшить питон-решение.