Reemplazos mínimos con cualquier número entero positivo para hacer que la array aumente K

Dada una array arr[] de N enteros positivos y un entero K , la tarea es reemplazar el número mínimo de elementos con cualquier entero positivo para hacer que la array aumente K. Una array es K-creciente si para cada índice i en el rango [K, N) , arr[i] ≥ arr[iK] 

Ejemplos:

Entrada: arr[] = {4, 1, 5, 2, 6, 2}, k = 2
Salida: 0
Explicación: Aquí, para cada índice i donde 2 <= i <= 5, arr[i-2] < = arr[i]
Dado que la array dada ya aumenta K, no es necesario realizar ninguna operación.

Entrada: arr[] = {4, 1, 5, 2, 6, 2}, k = 3
Salida: 2
Explicación: Los índices 3 y 5 son los únicos que no satisfacen arr[i-3] <= arr[i] para 3 <= i <= 5.
Una de las formas en que podemos hacer que la array aumente K es cambiando arr[3] a 4 y arr[5] a 5.
La array ahora será [4,1,5, 4,6,5].

Enfoque: esta solución se basa en encontrar la subsecuencia creciente más larga . Dado que la pregunta anterior requiere que arr[iK] ≤ arr[i]  se cumpla para cada índice i , donde K ≤ i ≤ N-1, aquí se da importancia a comparar los elementos que están a K lugares de distancia entre sí.
Entonces, la tarea es confirmar que las secuencias formadas por los elementos que K coloca son todas de naturaleza no decreciente. Si no lo son, realice los reemplazos para que no disminuyan.
Siga los pasos que se mencionan a continuación:

• Atraviese la array y forme una secuencia ( seq[] ) seleccionando elementos K lugares separados entre sí en la array dada.
• Compruebe si todos los elementos en seq[] no son decrecientes o no.
• De lo contrario, encuentre la longitud de la subsecuencia no decreciente más larga de seq[].
• Reemplace los elementos restantes para minimizar el número total de operaciones.
• La suma de las operaciones de reemplazo para todas esas secuencias es la respuesta final.

Siga la siguiente ilustración para una mejor comprensión.

• Por ejemplo: arr[] = {4, 1, 5, 2, 6, 0, 1} , K = 2

Índices: 0 1 2 3 4 5 6
valores: 4 1 5 2 6 0 1

Así que el trabajo es asegurar que las siguientes secuencias

1. arr[0], arr[2], arr[4], arr[6] => {4, 5, 6, 1}
2. array[1], array[3], array[5] => {1, 2, 0}

Obedecer arr[ik] <= arr[i]
Entonces, para la primera secuencia, se puede ver que {4, 5, 6} son K crecientes y es la subsecuencia no decreciente más larga, mientras que 1 no lo es, por lo que se necesita una operación para ello.
De manera similar, para el segundo {1, 2} son los más largos y no decrecientes, mientras que 0 no lo es, por lo que se necesita una operación para ello.

Por lo tanto, se requieren un total de 2 operaciones mínimas.  

A continuación se muestra la implementación del enfoque anterior. 

// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
 
// Functions finds the
// longest non decreasing subsequence.
int utility(vector<int>& arr, int& n)
{
    vector<int> tail;
    int len = 1;
    tail.push_back(arr[0]);
    for (int i = 1; i < n; i++) {
        if (tail[len - 1] <= arr[i]) {
            len++;
            tail.push_back(arr[i]);
        }
        else {
            auto it = upper_bound(tail.begin(),
                                  tail.end(),
                                  arr[i]);
            *it = arr[i];
        }
    }
    return len;
}
 
// Function to find the minimum operations
// to make array K-increasing
int kIncreasing(vector<int>& a, int K)
{
    int ans = 0;
     
    // Size of array
    int N = a.size();
    for (int i = 0; i < K; i++)
    {
        // Consider all elements K-places away
        // as a sequence
        vector<int> v;
       
        for (int j = i; j < N; j += K)
        {
            v.push_back(a[j]);
        }
         
        // Size of each sequence
        int k = v.size();
        
        // Store least operations
        // for this sequence
        ans += k - utility(v, k);
    }
    return ans;
}
 
// Driver code
int main()
{
    vector<int> arr{ 4, 1, 5, 2, 6, 0, 1 };
    int K = 2;
    cout << kIncreasing(arr, K);
    return 0;
}

# Python code for the above approach
 
def lowerBound(a, low, high, element):
    while (low < high):
        middle = low + (high - low) // 2;
        if (element > a[middle]):
            low = middle + 1;
        else:
            high = middle;
    return low;
 
def utility(v):
    if (len(v) == 0): # boundary case
        return 0;
 
    tail = [0] * len(v)
    length = 1; # always points empty slot in tail
    tail[0] = v[0];
 
    for i in range(1, len(v)):
 
        if (v[i] > tail[length - 1]):
 
            # v[i] extends the largest subsequence
            length += 1
            tail[length] = v[i];
     
        else:
 
            # v[i] will extend a subsequence and
            # discard older subsequence
 
            # find the largest value just smaller than
            # v[i] in tail
 
            # to find that value do binary search for
            # the v[i] in the range from begin to 0 +
            # length
            idx = lowerBound(v, 1, len(v), v[i]);
 
            # binarySearch in C# returns negative
            # value if searched element is not found in
            # array
 
            # this negative value stores the
            # appropriate place where the element is
            # supposed to be stored
            if (idx < 0):
                idx = -1 * idx - 1;
 
            # replacing the existing subsequence with
            # new end value
            tail[idx] = v[i];
    return length;
 
 
 
# Function to find the minimum operations
# to make array K-increasing
def kIncreasing(a, K):
    ans = 0;
 
    # Size of array
    N = len(a)
    for i in range(K):
        # Consider all elements K-places away
        # as a sequence
        v = [];
 
        for j in range(i, N, K):
            v.append(a[j]);
 
        # Size of each sequence
        k = len(v);
 
        # Store least operations
        # for this sequence
        ans += k - utility(v);
    return ans;
 
# Driver code
arr = [4, 1, 5, 2, 6, 0, 1];
K = 2;
print(kIncreasing(arr, K));
 
# This code is contributed by gfgking

// C# code for the above approach
using System;
using System.Collections.Generic;
class GFG {
  static int lowerBound(List<int> a, int low, int high,
                        int element)
  {
    while (low < high) {
      int middle = low + (high - low) / 2;
      if (element > a[middle])
        low = middle + 1;
      else
        high = middle;
    }
    return low;
  }
  static int utility(List<int> v, int n)
  {
    if (v.Count == 0) // boundary case
      return 0;
 
    int[] tail = new int[v.Count];
    int length = 1; // always points empty slot in tail
    tail[0] = v[0];
 
    for (int i = 1; i < v.Count; i++) {
 
      if (v[i] > tail[length - 1]) {
 
        // v[i] extends the largest subsequence
        tail[length++] = v[i];
      }
      else {
 
        // v[i] will extend a subsequence and
        // discard older subsequence
 
        // find the largest value just smaller than
        // v[i] in tail
 
        // to find that value do binary search for
        // the v[i] in the range from begin to 0 +
        // length
        var idx = lowerBound(v, 1, v.Count, v[i]);
 
        // binarySearch in C# returns negative
        // value if searched element is not found in
        // array
 
        // this negative value stores the
        // appropriate place where the element is
        // supposed to be stored
        if (idx < 0)
          idx = -1 * idx - 1;
 
        // replacing the existing subsequence with
        // new end value
        tail[idx] = v[i];
      }
    }
    return length;
  }
 
  // Function to find the minimum operations
  // to make array K-increasing
  static int kIncreasing(int[] a, int K)
  {
    int ans = 0;
 
    // Size of array
    int N = a.Length;
    for (int i = 0; i < K; i++)
    {
       
      // Consider all elements K-places away
      // as a sequence
      List<int> v = new List<int>();
 
      for (int j = i; j < N; j += K) {
        v.Add(a[j]);
      }
 
      // Size of each sequence
      int k = v.Count;
 
      // Store least operations
      // for this sequence
      ans += k - utility(v, k);
    }
    return ans;
  }
 
  // Driver code
  public static void Main()
  {
    int[] arr = { 4, 1, 5, 2, 6, 0, 1 };
    int K = 2;
    Console.Write(kIncreasing(arr, K));
  }
}
 
// This code is contributed by ukasp.

<script>
        // JavaScript code for the above approach
        function lowerBound(a, low, high, element)
        {
            while (low < high) {
                var middle = low + (high - low) / 2;
                if (element > a[middle])
                    low = middle + 1;
                else
                    high = middle;
            }
            return low;
        }
        function utility(v) {
            if (v.length == 0) // boundary case
                return 0;
 
            var tail = Array(v.length).fill(0);
            var length = 1; // always points empty slot in tail
            tail[0] = v[0];
 
            for (i = 1; i < v.length; i++) {
 
                if (v[i] > tail[length - 1]) {
 
                    // v[i] extends the largest subsequence
                    tail[length++] = v[i];
                }
                else {
 
                    // v[i] will extend a subsequence and
                    // discard older subsequence
 
                    // find the largest value just smaller than
                    // v[i] in tail
 
                    // to find that value do binary search for
                    // the v[i] in the range from begin to 0 +
                    // length
                    var idx = lowerBound(v, 1, v.length, v[i]);
 
                    // binarySearch in C# returns negative
                    // value if searched element is not found in
                    // array
 
                    // this negative value stores the
                    // appropriate place where the element is
                    // supposed to be stored
                    if (idx < 0)
                        idx = -1 * idx - 1;
 
                    // replacing the existing subsequence with
                    // new end value
                    tail[idx] = v[i];
                }
            }
            return length;
        }
 
 
        // Function to find the minimum operations
        // to make array K-increasing
        function kIncreasing(a, K) {
            let ans = 0;
 
            // Size of array
            let N = a.length;
            for (let i = 0; i < K; i++) {
                // Consider all elements K-places away
                // as a sequence
                let v = [];
 
                for (let j = i; j < N; j += K) {
                    v.push(a[j]);
                }
 
                // Size of each sequence
                let k = v.length;
 
                // Store least operations
                // for this sequence
                ans += k - utility(v, k);
            }
            return ans;
        }
 
        // Driver code
        let arr = [4, 1, 5, 2, 6, 0, 1];
        let K = 2;
        document.write(kIncreasing(arr, K));
 
  // This code is contributed by Potta Lokesh
    </script>

2

Complejidad de Tiempo: O(K * N * logN)
Espacio Auxiliar: O(N)