Eliminar entradas de la matriz para ordenarlas y maximizar la suma de elementos

13

Este desafío es desde una prueba de admisión hasta un curso de seguridad cibernética de número cerrado. De todos modos, no tiene que ver con la seguridad cibernética, es solo para evaluar las habilidades lógicas y de codificación de los estudiantes.

Tarea

Escriba un programa que elimine entradas de una matriz para que los valores restantes se ordenen en un orden estrictamente decreciente y su suma se maximice entre todas las demás secuencias decrecientes posibles.

Entrada y salida

De entrada será una matriz de valores de número entero estrictamente mayor que 0y todos diferentes unos de otros . Usted es libre de elegir si desea leer la entrada del archivo, línea de comando o stdin.

La salida será un subconjunto ordenado descendente del de entrada, cuya suma es mayor que cualquier otro subconjunto ordenado descendente posible.

Nota: [5, 4, 3, 2] es un subconjunto de [5, 4, 1, 3, 2], incluso si 4y 3no son adyacentes. Solo porque el 1estalló.

Solución de fuerza bruta

La solución más simple, por supuesto, sería iterar entre todas las combinaciones posibles de la matriz dada y buscar una ordenada con la mayor suma, que sería, en Python :

import itertools

def best_sum_desc_subarray(ary):
    best_sum_so_far = 0
    best_subarray_so_far = []
    for k in range(1, len(ary)):
        for comb in itertools.combinations(ary, k):
            if sum(comb) > best_sum_so_far and all(comb[j] > comb[j+1] for j in range(len(comb)-1)):
                best_subarray_so_far = list(comb)
                best_sum_so_far = sum(comb)
    return best_subarray_so_far

Por desgracia, ya comprobar si se ordena la matriz y el cálculo de la suma de sus elementos es y ya que esta operación se hará veces para partir a la complejidad asintótica tiempo será

Desafío

Su objetivo es lograr una mejor complejidad de tiempo que la fuerza bruta anterior. La solución con la menor complejidad asintótica del tiempo es la ganadora del desafío. Si dos soluciones tienen la misma complejidad asintótica del tiempo, el ganador será el que tenga la menor complejidad espacial asintótica.

Nota: puede considerar leer, escribir y comparar atómica incluso en grandes cantidades.

Nota: Si hay dos o más soluciones, devuelva cualquiera de ellas.

Casos de prueba

Input:  [200, 100, 400]
Output: [400]

Input:  [4, 3, 2, 1, 5]
Output: [4, 3, 2, 1]

Input:  [50, 40, 30, 20, 10]
Output: [50, 40, 30, 20, 10]

Input:  [389, 207, 155, 300, 299, 170, 158, 65]
Output: [389, 300, 299, 170, 158, 65]

Input:  [19, 20, 2, 18, 13, 14, 8, 9, 4, 6, 16, 1, 15, 12, 3, 7, 17, 5, 10, 11]
Output: [20, 18, 16, 15, 12, 7, 5]

Input:  [14, 12, 24, 21, 6, 10, 19, 1, 5, 8, 17, 7, 9, 15, 23, 20, 25, 11, 13, 4, 3, 22, 18, 2, 16]
Output: [24, 21, 19, 17, 15, 13, 4, 3, 2]

Input:  [25, 15, 3, 6, 24, 30, 23, 7, 1, 10, 16, 29, 12, 13, 22, 8, 17, 14, 20, 11, 9, 18, 28, 21, 26, 27, 4, 2, 19, 5]
Output: [25, 24, 23, 22, 17, 14, 11, 9, 4, 2]
array-manipulation subsequence fastest-algorithm Marco
fuente
Relacionado. (No puedo verificar en este momento si los dos algoritmos son de hecho equivalentes, pero creo que podrían serlo)
Martin Ender
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Martin Ender

Respuestas:

3

Perl

Esto debería ser O (n ^ 2) en el tiempo y O (n) en el espacio

Dar números separados por espacio en una línea a STDIN

#!/usr/bin/perl -a
use strict;
use warnings;

# use Data::Dumper;
use constant {
    INFINITY => 9**9**9,
    DEBUG    => 0,
};

# Recover sequence from the 'how' linked list
sub how {
    my @z;
    for (my $h = shift->{how}; $h; $h = $h->[1]) {
        push @z, $h->[0];
    }
    pop @z;
    return join " ", reverse @z;
}

use constant MINIMUM => {
    how  => [-INFINITY, [INFINITY]],
    sum  => -INFINITY,
    next => undef,
};

# Candidates is a linked list of subsequences under consideration
# A given final element will only appear once in the list of candidates
# in combination with the best sum that can be achieved with that final element
# The list of candidates is reverse sorted by final element
my $candidates = {
    # 'how' will represent the sequence that adds up to the given sum as a
    # reversed lisp style list.
    # so e.g. "1, 5, 8" will be represented as [8, [5, [1, INFINITY]]]
    # So the final element will be at the front of 'how'
    how  => [INFINITY],
    # The highest sum that can be reached with any subsequence with the same
    # final element
    sum  => 0,
    # 'next' points to the next candidate
    next => MINIMUM,   # Dummy terminator to simplify program logic
};

for my $num (@F) {
    # Among the candidates on which an extension with $num is valid
    # find the highest sum
    my $max_sum = MINIMUM;
    my $c = \$candidates;
    while ($num < $$c->{how}[0]) {
        if ($$c->{sum} > $max_sum->{sum}) {
            $max_sum = $$c;
            $c = \$$c->{next};
        } else {
            # Remove pointless candidate
            $$c = $$c->{next};
        }
    }

    my $new_sum = $max_sum->{sum} + $num;
    if ($$c->{how}[0] != $num) {
        # Insert a new candidate with a never before seen end element
        # Due to the unique element rule this branch will always be taken
        $$c = { next => $$c };
    } elsif ($new_sum <= $$c->{sum}) {
        # An already known end element but the sum is no improvement
        next;
    }
    $$c->{sum} = $new_sum;
    $$c->{how} = [$num, $max_sum->{how}];
    # print(Dumper($candidates));
    if (DEBUG) {
        print "Adding $num\n";
        for (my $c = $candidates; $c; $c = $c->{next}) {
            printf "sum(%s) = %s\n", how($c), $c->{sum};
        }
        print "------\n";
    }
}

# Find the sequence with the highest sum among the candidates
my $max_sum = MINIMUM;
for (my $c = $candidates; $c; $c = $c->{next}) {
    $max_sum = $c if $c->{sum} > $max_sum->{sum};
}

# And finally print the result
print how($max_sum), "\n";
Ton Hospel
fuente
3

O(norteIniciar sesión⁡norte)O(norte)

{-# LANGUAGE MultiParamTypeClasses #-}

import qualified Data.FingerTree as F

data S = S
  { sSum :: Int
  , sArr :: [Int]
  } deriving (Show)

instance Monoid S where
  mempty = S 0 []
  mappend _ s = s

instance F.Measured S S where
  measure = id

bestSubarrays :: [Int] -> F.FingerTree S S
bestSubarrays [] = F.empty
bestSubarrays (x:xs) = left F.>< sNew F.<| right'
  where
    (left, right) = F.split (\s -> sArr s > [x]) (bestSubarrays xs)
    sLeft = F.measure left
    sNew = S (x + sSum sLeft) (x : sArr sLeft)
    right' = F.dropUntil (\s -> sSum s > sSum sNew) right

bestSubarray :: [Int] -> [Int]
bestSubarray = sArr . F.measure . bestSubarrays

Cómo funciona

bestSubarrays xses la secuencia de subconjuntos xsque se encuentran en la frontera eficiente de {suma más grande, primer elemento más pequeño}, ordenados de izquierda a derecha aumentando la suma y aumentando el primer elemento.

Para ir de bestSubarrays xsa bestSubarrays (x:xs), nosotros

  1. dividir la secuencia en un lado izquierdo con primeros elementos menores que x, y un lado derecho con primeros elementos mayores que x,
  2. encuentre una nueva submatriz pretendiendo xla submatriz más a la derecha en el lado izquierdo,
  3. suelte el prefijo de las submatrices desde el lado derecho con una suma menor que la nueva submatriz,
  4. concatenar el lado izquierdo, el nuevo subconjunto y el resto del lado derecho.

O(Iniciar sesión⁡norte)

Anders Kaseorg
fuente
1

Esta respuesta se expande sobre la de Ton Hospel.

El problema se puede resolver con programación dinámica utilizando la recurence

T(yo)=unyo+max[{0 0}∪{T(j)El |0 0≤j<yo∧unyo≤unj}]

(unyo)T(yo)yoT

fn solve(arr: &[usize]) -> Vec<usize> {
    let mut tbl = Vec::new();
    // Compute table with maximum sums of any valid sequence ending
    // with a given index i.
    for i in 0..arr.len() {
        let max = (0..i)
            .filter(|&j| arr[j] >= arr[i])
            .map(|j| tbl[j])
            .max()
            .unwrap_or(0);
        tbl.push(max + arr[i]);
    }
    // Reconstruct an optimal sequence.
    let mut sum = tbl.iter().max().unwrap_or(&0).clone();
    let mut limit = 0;
    let mut result = Vec::new();

    for i in (0..arr.len()).rev() {
        if tbl[i] == sum && arr[i] >= limit {
            limit = arr[i];
            sum -= arr[i];
            result.push(arr[i]);
        }
    }
    assert_eq!(sum, 0);
    result.reverse();
    result
}

fn read_input() -> Vec<usize> {
    use std::io::{Read, stdin};
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    s.split(|c: char| !c.is_numeric())
        .filter(|&s| !s.is_empty())
        .map(|s| s.parse().unwrap())
        .collect()
}

fn main() {
    println!("{:?}", solve(&read_input()));
}

Pruébalo en línea!

politza
fuente