Je suis tombé sur cette question lors d'un concours de programmation:
On nous donne un tableau composé de n éléments. À chaque itération, vous pouvez sélectionner deux éléments quelconques ai et aj et remplacer a < sub> i avec un i et un j . & est l'opérateur AND au niveau du bit. Trouvez le nombre minimum d'opérations AND nécessaires pour rendre tous les éléments du tableau à zéro.
Supposons qu'il existe une solution pour les entrées données. Quelle est la solution optimale à ce problème?
Modifier: J'ai ajouté ma solution DP pour le problème qui prend plus d'une seconde à s'exécuter. Une suggestion pour l'accélérer?
0
D: nombre maximum de chiffres en base 2 (0
OBJECTIF: 2 ^ D - 1
T [i] [X] => nombre minimum d'éléments de {n_0, n_1, ..., n_i} qui rendent X zéro
T [i] [0] = 0
T [0] [X> 0] = INF
T [i] [X] = min (1 + T [i-1] [X & n_i], T [i-1] [X])
T [n] [GOAL] -> nombre minimum d'opérations AND
3 Réponses :
Cela me semble être le problème de couverture de jeu . Nous devons trouver le plus petit sous-ensemble qui couvre les zéros dans chaque position. Une fois ce sous-ensemble trouvé, le zéro "absolu" généré peut être utilisé pour convertir d'autres éléments en zéro. Dans l'exemple ci-dessous, l'un des trois éléments du sous-ensemble peut être utilisé pour devenir le premier zéro.
1001 0101< 0011< 1110< 0111
Belle solution. Qu'en est-il de la preuve d'optimalité?
@AsafRosemarin voulez-vous dire l'optimalité de la couverture d'ensemble pour trouver une réponse, ou l'optimalité du plus petit sous-ensemble couvrant tous les zéros exprimant le nombre minimum de mouvements nécessaires? J'espère que ce dernier est plus ou moins évident.
La deuxième option
@AsafRosemarin semble aller de soi. Si nous n'avons pas toutes les positions nulles couvertes dans un sous-ensemble, comment pouvons-nous faire un zéro "absolu" à partir de ce sous-ensemble?
Je ne voulais pas dire qu'un tel sous-ensemble peut ne pas exister, ce que je voulais dire par preuve d'optimalité est de prouver que cette stratégie (trouver la couverture de sous-ensemble minimal, créer un zéro absolu, l'utiliser pour mettre à zéro le tableau entier) est optimale en quantité de Opérations ET .
Après y avoir réfléchi un moment, il est assez trivial de le prouver. J'aime ta solution :)
En fait, dans le problème de couverture d'ensemble , le n est la taille de l'univers - ici, cela signifie la taille du nombre en bits ou log 2 (le plus grand nombre) < / code> qui est généralement une constante dans les concours de programmation. Vous cherchez donc un autre problème où k - nombre d'ensembles est en fait le n , et n est const. (Probablement la même solution, juste pour info)
@ גלעדברקן Comment trouver le plus petit sous-ensemble qui couvre les zéros dans chaque position ?
@ La couverture de l'ensemble Mbt925 est un problème connu et étudié. Je chercherais de la littérature traitant de la circonstance binaire. Mais peut-être que Gregory a une interprétation correcte de la question? Êtes-vous sûr que nous sommes autorisés à examiner les éléments du tableau?
@ Mbt925 Dans le monde réel, utilisez un solveur de programme entier. Dans un concours, la branche et la reliure seraient peut-être suffisantes. La mise en œuvre du double simplex prendrait certes un certain temps.
@ גלעדברקן J'ai édité ma question. Pouvez-vous y jeter un œil?
@DavidEisentat Pouvez-vous jeter un œil à ma question modifiée?
Si le problème a une solution pour une entrée donnée, vous pouvez effectuer ces opérations:
Choisissez un index i entre [0, n-1] (en supposant que l'indexation des tableaux est basée sur zéro).
Pour chaque j compris entre 0 et n qui n'est pas i, effectuez un i <- a i & a j . À ce stade, vous êtes assuré que a_i est égal à 0, sinon le problème est insoluble car vous avez effectué des opérations au niveau du bit et sur tous les éléments du tableau.
Pour chaque j compris entre 0 et n qui n'est pas i, effectuez un j <- a i & a j . Cela fonctionne et sur tous les éléments du tableau avec 0, ce qui les rend 0 également.
Vous effectuez l'opération et n-1 fois pour la première boucle et n-1 fois pour la deuxième boucle, donc au total 2n-2 et opérations.
Modifier:
Cela suppose que vous ne pouvez pas regarder les valeurs du tableau.
"Trouvez le nombre minimum d'opérations AND nécessaires pour rendre tous les éléments du tableau à zéro." me suggère que la valeur de retour doit être un entier. Votre solution n'est pas minimale (et ne compte pas combien de AND ont même eu un effet). Si vous avez juste besoin de mettre à zéro un tableau, il existe des moyens beaucoup plus simples de combiner des éléments au niveau du bit.
Votre solution donne le nombre maximum d'opérations AND nécessaires.
(J'ai ajouté un espace à votre réponse juste pour pouvoir la voter. J'avais déjà voté contre mais selon la façon dont nous interprétons la question, cela pourrait être une réponse correcte.)
Je suppose que vous pouvez obtenir l'accélération nécessaire en rendant votre table DP clairsemée. Nous pouvons considérer l'algorithme résultant comme faisant une recherche en largeur d'abord de 2 ^ D-1 à 0 sur un graphe où les nœuds sont 0..2 ^ D-1 et les arêtes vont de x à x & y où y est un élément du tableau. En fait, en raison de la commutativité / associativité du ET au niveau du bit, nous pouvons resserrer le jeu d'arêtes en exigeant que x & y efface le plus petit jeu de bits dans x . Dans le code Python ci-dessous, cela est obtenu de manière assez efficace en utilisant une carte zero_index , mais dans CI utiliserait un tableau (et remplacerait les ensembles par des bitmaps ou des tableaux selon le cas).
import collections
import random
def min_and(seq):
lst = list(seq)
zero_index = collections.defaultdict(lambda: set(lst))
for x in lst:
y = x
while y:
zero_index[y & ~(y - 1)].discard(x)
y &= y - 1
visited = set()
fringe = set(lst)
i = 0
while 0 not in fringe:
visited.update(fringe)
fringe = {
x & y
for x in fringe for y in zero_index[x & ~(x - 1)]
if x & y not in visited
}
i += 1
return i + len(lst) - 1
print(min_and(
random.randrange(2**18) | random.randrange(2**18) | random.randrange(2**18)
for i in range(100)))
Merci pour la solution. Ça marche. Pouvez-vous expliquer plus en détail la partie y & ~ (y - 1) et le resserrement du jeu d'arêtes? Pourquoi effacer le bit le plus bas?
@ Mbt925 y & ~ (y - 1) est un idiome qui extrait le bit le plus bas. Nous savons qu'il doit y avoir un nombre avec ce bit clair dans le ET au niveau du bit, donc en le forçant à être la première étape du graphe, nous réduisons le nombre d'états intermédiaires que nous devons considérer.
J'ai donné la prime à un autre utilisateur par erreur. Je suis désolé.
@ Mbt925 Eh, j'ai assez de rep.
J'ai mesuré le temps d'exécution de l'algorithme. Ce n'est toujours pas aussi rapide que je le voulais. Cependant, les structures de données utilisées par votre code sont tout à fait optimales. Une suggestion pour une mise en œuvre plus rapide?
@ Mbt925 En travaillant en C ++, je ferais de zero_index un vecteur de vecteurs et utiliserais un intrinsèque pour trouver l'index du premier zéro (ou trouver le premier dans ~ x ) pour les recherches. Je ferais de visité un bitmap et de frange un vecteur, mais mettre à jour visité avec impatience pour éviter les doublons dans frange .
"Supposons qu'il y ait une solution. Quelle est la solution optimale pour ce problème?" Une solution ne se matérialise pas simplement parce que vous supposez qu'elle existe :) Quoi qu'il en soit, qu'avez-vous essayé?
Quelles sont vos pensées? Des pistes? Vous avez tagué la question avec «programmation dynamique», donc il semble que vous ayez une idée.
Cette partie de la question doit être comprise dans le contexte du problème. Par exemple, pour le tableau
{1,1}il n'y a pas de solution car1 & 1 = 1, donc le tableau ne peut pas être effacé avec les opérations décrites.Il semble y avoir des informations manquantes. Sans connaître les valeurs du tableau, vous ne pouvez pas dire si oui ou non deux éléments donneront zéro.
@ גלעדברקן Oui, je connais cette partie de la question. Je voulais juste dire que je crois que ce commentaire visait à limiter le problème aux instances qui peuvent être résolues. J'avais l'impression que BlackBear comprenait cette déclaration d'une manière informelle, comme "ma question a une réponse".
@BlackBear C'est une question que j'ai vue dans un concours de programmation. L'énoncé du problème indique qu'il existe une solution pour les entrées données. La seule solution m'est venue à l'esprit était BruteForce !!
Ce concours de programmation est-il toujours en cours? Veuillez envoyer un lien vers celui-ci.
@ 500-InternalServerError: vous savez que le et de toutes les valeurs est certainement nul.
@Yonlif Non, ce n'est pas le cas.
Quelle est la contrainte sur D?
@DavidEisentat c'est plus petit que 18