Comment utiliser un algorithme gourmand pour trouver la séquence non décroissante la plus proche de celle donnée?

On vous donne n entiers tous compris entre et . Sous chaque entier vous devez écrire un entier entre 0 et l avec la condition que les b i forment une séquence non décroissante. Définissez la déviation d'une telle séquence comme étant . Concevez un algorithme qui trouve les b_i avec l'écart minimum dans le runtime O (n \ sqrt [4] {l}) .$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})$

Honnêtement, je n'ai aucune idée de comment commencer à résoudre cette question. Cela ressemble à une question de programmation dynamique pour moi, mais le professeur a dit que cela devrait être résolu en utilisant un algorithme gourmand. Il serait très apprécié que quelqu'un puisse m'orienter dans la bonne direction en donnant un petit indice.

Commençons par l'observation suivante:

Soit le maximum de la séquence , et désigne son minimum. Si , choisir est optimal.$max$$a_1,...,a_n$$min$$a_1=max$$b_1=b_2=...=b_n=\lfloor(max+min)/2\rfloor$

pourquoi est-ce le cas? Eh bien, puisque la séquence commence par le maximum, soit nous choisissons grand, et nous subissons une grande déviation par rapport au minimum de la séquence (puisque tout ultérieur doit être supérieur ou égal à b_1 ), soit nous choisissons b_1 petit et souffrons de la écart à max . La moyenne minimise l'écart maximal.b i b 1 b 1 m a $b_1$$b_i$$b_1$$b_1$$max$

On peut maintenant essayer de généraliser cette observation pour l'utiliser sur les séquences générales $a_1,...,a_n$ . Par exemple, nous pouvons partitionner n'importe quelle séquence en sous-séquences, de telle sorte que chacune commence par le maximum de la sous-séquence respective.

Exemple: est divisé en , et .( 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)$

Compte tenu de ce partitionnement, nous pouvons maintenant résoudre chacune de ces sous-séquences séparément, et obtenir une affectation des , ce qui pourrait cependant violer la condition non décroissante. Cela peut être corrigé sans perdre l'optimalité.$b_i$

Observez que la dernière sous-séquence contient toujours le maximum de la séquence entière (sinon, il y aurait une autre sous-séquence après). Soit les valeurs que nous avons attribuées aux séquences. Maintenant, pour atteindre la non-diminution dans , nous partons de l'arrière à et nous nous dirigeons vers l'avant. Si est plus grand que , nous mettons simplement . S'il est plus petit, nous le conservons. Ensuite, nous procédons à la comparaison de avec et ainsi de suite. Notez que l'abaissement de tout à la valeur de$max$$w_1,w_2,...,w_k$$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}$n'augmente jamais l'écart, car la valeur maximale dans la sous-séquence affectée avec est toujours inférieure au maximum dans la sous-séquence affectée avec .$w_i$$w_{i+1}$

Cet algorithme devrait être correct, je pense. Concernant le temps d'exécution, l'étape clé est le calcul des maxima croissants pour les sous-séquences, ce qui est possible dans ? Je ne sais pas où contribue.$O(n)$$l$

Je vais penser à haute voix ici en travaillant simplement sur les conseils que vous avez donnés. Allons à l'indication originale de dire que est ce que vous devez essayer en premier. Je peux penser à un algorithme gourmand qui a ce temps.$O(nl)$

La partie de la complexité temporelle signifie que vous pouvez garder une liste du nombre de chaque occurrence de chaque valeur 0 .. l . Pour cela, il suffit de créer un ensemble Count = C 0 , … , C l qui suit le nombre de chaque l dans l'ensemble. Vous pouvez créer la liste d'initialisation en scannant une fois la séquence d'entrée.$l$$0..l$$\text{Count} = { C_0, \ldots, C_l}$$l$

Vous pouvez parcourir cette liste dans pour obtenir la valeur maximale et minimale. Si vous deviez remplir la liste entière de b avec ce point médian, votre variance serait simplement la différence entre cette valeur et le max / min. C'est fondamentalement votre pire scénario, appelons-le b w .$O(l)$$b$$b_w$

Travaillez donc votre chemin vers depuis la gauche. Vous pouvez à la fois supprimer cet élément de Count et obtenir le min / max de b [ i + 1 ] … b [ n ] dans O ( l ) . Maintenant, nous pouvons être gourmands. Nous ne choisissons pas b i > b w car cela force la liste entière restante (pour répondre à l'exigence non décroissante) et augmente ainsi la variance. La valeur minimale que nous pouvons choisir est b [ i - 1 ] . Si un $b_i$$\text{Count}$$b[i+1] \ldots b[n]$$O(l)$$b_i > b_w$$b[i-1]$$a_i$est dans la plage acceptable, nous le sélectionnons, s'il est inférieur à la plage, utilisez le minimum. Cela minimise la variance à compte tenu des contraintes connues.$b_i$

Ce n'est qu'une idée, j'ai peut-être de la chance et cela vous indique la bonne direction. Cet algorithme peut ne pas fonctionner (il le fait pour mes quelques tests simples), mais il correspond aux conseils donnés, alors peut-être qu'il est utile. S'il est correct, il est facile de voir que la partie peut à coup sûr être déposée sur , encore plus loin, je ne suis pas sûr.$O(l)$$O(\log l)$

Voici la solution du professeur, qu'il appelle «réduction»: Pour chaque de 0 à l , essayez de construire une solution si nous savons que l'écart est inférieur ou égal à i . Le premier i pour lequel une solution peut être trouvée est l'écart minimum. Nous pouvons trouver une solution étant donné l'écart en temps O ( n ) . Le temps de course est donc O ( n l ) . Ensuite, au lieu d'utiliser la recherche linéaire, nous pouvons utiliser la recherche binaire pour déterminer la plus petite déviation pour laquelle une solution est possible. Cela réduit le temps d'exécution à O ( n log $i$$0$$l$$i$$i$$O(n)$$O(nl)$ , qui satisfait à l'exigence de O ( n 4 $O(n\log l)$.$O(n\sqrt[4]{l})$

Je pense que cela devrait être faisable en O (n).

Prenons le problème similaire: étant donné , 1 ≤ i ≤ n et d ≥ 0, trouver b i dans un ordre non décroissant tel que | a i - b i | ≤ d pour tout i, ou montrer que ce n'est pas possible. Cela peut être fait dans O (n), et en utilisant la recherche binaire, le problème d'origine est résolu dans O (n log l).$a_i$$b_i$$|a_i - b_i| ≤ d$

Maintenant, s'il y a i ≤ j tel que a_i - a_j> 2d, alors il n'y a pas de solution (car ).$b_i ≥ a_i - d, b_j ≤ a_j + d < a_i - 2d + d = a_i - d ≤ b_i$

Mais si a_i - a_j ≤ 2d pour tout i ≤ j, je pense qu'une solution sera toujours trouvée. Il nous suffit donc de trouver m = max (a_i - a_j) pour tout i ≤ j, et de choisir d = étage ((m + 1) / 2). Ce maximum peut être trouvé dans O (n).