Como usar um algoritmo ganancioso para encontrar a sequência não decrescente mais próxima da determinada?

$a_1, \ldots, a_n$$0$$l$$a_i$$b_i$$0$$l$$b_i$$\max(|a_1-b_1|, \ldots, |a_n-b_n|)$$b_i$$O(n\sqrt[4]{l})$

Sinceramente, não tenho idéia de como começar a resolver essa questão. Parece uma pergunta de programação dinâmica para mim, mas o professor disse que isso deveria ser resolvido usando um algoritmo ganancioso. Seria muito apreciado se alguém pudesse me apontar na direção certa, dando uma pequena dica.

Vamos começar com a seguinte observação:

Deixe denotar o máximo da sequência e deixe denotar seu mínimo. Se , então escolher é o ideal.um 1 , . . . , a n m i n a 1 = m a x b 1 = b 2 = . . . = b n = ⌊ ( m a x + m i n ) / 2 $max$$a_1,...,a_n$$min$$a_1=max$$b_1=b_2=...=b_n=\lfloor(max+min)/2\rfloor$

Por que esse é o caso? Bem, como a sequência começa com o máximo, escolhemos grande e sofremos um grande desvio do mínimo da sequência (já que qualquer subsequente deve ser maior ou igual a ) ou escolhemos pequeno e sofrem com o desvio para . A média minimiza o desvio máximo.b i b 1 b 1 m um $b_1$$b_i$$b_1$$b_1$$max$

Agora podemos tentar generalizar essa observação para usar nas seqüências gerais . Por exemplo, podemos particionar qualquer sequência em subsequências, de modo que cada uma comece com o máximo da respectiva subsequência.$a_1,...,a_n$

Exemplo: é particionado em , e .( 2 ) ( 6 , 4 , 1 , 5 , 2 ) ( 8 , 7 , 5 , 1 $(2,6,4,1,5,2,8,7,5,1)$$(2)$$(6,4,1,5,2)$$(8,7,5,1)$

Dado esse particionamento, agora podemos resolver cada uma dessas subsequências separadamente e obter uma atribuição dos 's, que, no entanto, podem violar a condição não decrescente. Isso pode ser corrigido sem perder a otimização.$b_i$

Observe que a última subsequência sempre contém o máximo de toda a sequência (caso contrário, haveria outra subsequência depois). Seja os valores que às subseqüências. Agora, para alcançar a não diminuição em , começamos de trás em e trabalhamos o nosso caminho para a frente. Se for maior que , simplesmente configuramos . Se for menor, nós a mantemos. Depois, comparamos com e assim por diante. Observe que abaixando qualquer para o valor dew 1 , w 2 , . . . , W $max$$w_1,w_2,...,w_k$w 1 , . . . , w k w k w k - 1 w k w k - 1 : = w k w k - 2 w k - 1 w i w i + 1 w i w i + $k$$w_1,...,w_k$$w_k$$w_{k-1}$$w_k$$w_{k-1}:=w_k$$w_{k-2}$$w_{k-1}$$w_i$$w_{i+1}$nunca aumenta o desvio, uma vez que o valor máximo na subsequência atribuída com é sempre menor que o máximo na subsequência atribuída com .$w_i$$w_{i+1}$

Esse algoritmo deve estar correto, eu acho. Em relação ao tempo de execução, a etapa principal é calcular os máximos crescentes para as subsequências, o que é possível em ? Não tenho certeza de onde contribui.$O(n)$$l$

Eu vou pensar em voz alta aqui, trabalhando nas dicas que você deu. Vamos para a dica original de dizer que é o que você deve tentar primeiro. Eu posso pensar em um algoritmo ganancioso que tem esse tempo.$O(nl)$

A parte da complexidade do tempo significa que você pode manter uma lista da contagem de cada ocorrência de cada valor . Isso é apenas criar um conjunto que rastreia a contagem de cada no conjunto. Você pode criar a lista de inicialização digitalizando a sequência de entrada uma vez.0 .. l Contagem = C 0 , … , C l$l$$0..l$$\text{Count} = { C_0, \ldots, C_l}$$l$

Você pode digitalizar esta lista em para obter o valor máximo e mínimo. Se você preenchesse toda a lista de com esse ponto médio, sua variação seria simplesmente a diferença desse valor e do máximo / min. Este é basicamente o seu pior cenário, vamos chamá-lo de .b b $O(l)$$b$$b_w$

Então, trabalhe para da esquerda. Você pode remover esse elemento de e obter o mínimo / máximo de em . Agora podemos ser gananciosos. Não escolhemos pois isso força a lista inteira restante (para atender ao requisito não decrescente) e, portanto, aumenta a variação. O valor mínimo que podemos escolher é . Se estiver no intervalo aceitável, nós o selecionamos, se abaixo do intervalo, use o mínimo. Isso minimiza a variação em dadas as restrições conhecidas. Contagem b [ i + 1 ] … b [ n ] O ( l ) b i > b w b [ i - 1 ] a i b $b_i$$\text{Count}$$b[i+1] \ldots b[n]$$O(l)$$b_i > b_w$$b[i-1]$$a_i$$b_i$

Esta é apenas uma ideia, talvez eu tenha sorte e aponte para a direção certa. Esse algoritmo pode não funcionar (funciona nos meus poucos testes simples), mas corresponde às dicas fornecidas, portanto, talvez seja útil. Se correto, é fácil ver que a parte pode com certeza ser solta em , ainda mais, não tenho certeza.O ( log l $O(l)$$O(\log l)$

Aqui está a solução do professor, que ele chama de "redução": para cada de a , tente construir uma solução se soubermos que o desvio é menor ou igual a . O primeiro para o qual uma solução pode ser encontrada é o desvio mínimo. Podemos encontrar uma solução dado o desvio no tempo . Portanto, o tempo de execução é . Então, em vez de usar a pesquisa linear, podemos usar a pesquisa binária para determinar o menor desvio para o qual uma solução é possível. Isso reduz o tempo de execução para , que satisfaz os requisitos de .0 l i i S ( n ) S ( n l ) O ( N log l ) O ( n 4 $i$$0$$l$$i$$i$$O(n)$$O(nl)$$O(n\log l)$$O(n\sqrt[4]{l})$

Eu acho que isso deve ser possível em O (n).

Tome o mesmo problema: dados , 1 ≤ i ≤ n ed ≥ 0, encontre em ordem não descendente, de modo que para todos os i ou mostre que não é possível. Isso pode ser feito em O (n) e, usando a pesquisa binária, o problema original é resolvido em O (n log l).b i | a i - b i | ≤ $a_i$$b_i$$|a_i - b_i| ≤ d$

Agora, se houver i ≤ j tal que a_i - a_j> 2d, então não haverá solução (porque ).$b_i ≥ a_i - d, b_j ≤ a_j + d < a_i - 2d + d = a_i - d ≤ b_i$

Mas se a_i - a_j ≤ 2d para todo i ≤ j, acho que sempre será encontrada uma solução. Portanto, tudo o que precisamos fazer é encontrar m = max (a_i - a_j) para todos os i ≤ j e escolher d = floor ((m + 1) / 2). Esse máximo pode ser encontrado em O (n).