Salut j'ai un code que j'aimerais rendre plus rapide en particulier pour les grands…
- User
Salut j'ai un code que j'aimerais rendre plus rapide en particulier pour les grands nombre peux tu essayer ? : N = int(input()) K = int(input()) bars = list(map(int, input().split())) bars.sort() max_pairs = N // 2
dp = [[float('inf')] * (K + 1) for _ in range(N + 1)] dp[0][0] = 0 dp[1][0] = 0 for i in range(2, N + 1): dp[i][0] = 0
for k in range(1, min(i // 2, K) + 1): dp[i][k] = dp[i - 1][k] new_imbalance = dp[i - 2][k - 1] + abs(bars[i - 1] - bars[i - 2]) if new_imbalance < dp[i][k]: dp[i][k] = new_imbalance print(int(dp[N][K]))ProloginPrologin 2025 Participer Découvrir S'entraîner Archives Forums
rgrvrv Prologin Entraînement Qualification 2025 Le Juste Échafaudage Le Juste Échafaudage – Qualification 2025 Niveau 5 ⋅ Validation weight: 15% ⋅ Vous avez résolu ce problème.
Énoncé Joseph Nageant dispose enfin de toutes les informations dont il a besoin pour s'immiscer dans la forteresse sous-marine ! Pour pouvoir accéder à l'intérieur des remparts, il tente de construire un échafaudage en vitesse pour s'infiltrer par une meurtrière, en se faisant passer pour un ouvrier.
Joseph Nageant dispose de barres de tailles variables pour construire son échafaudage sur étages.
Pour chaque étage de l'échafaudage, Joseph Nageant doit sélectionner deux barres de taille et parmi les barres à sa disposition. Le déséquilibre de son échafaudage est alors augmenté de , où représente la valeur absolue.
Déterminez le déséquilibre minimal que Joseph peut obtenir pour un échafaudage de étages.
Entrée L’entrée contiendra :
Sur la première ligne, un entier : N, le nombre de barres. Sur la ligne suivante, un entier : K, le nombre d'étages à construire. Sur la ligne suivante, une liste de N entiers séparés par des espaces : barres, la taille des barres. Sortie Afficher, sur une ligne, le déséquilibre minimal possible pour construire son échaufadage.
Contraintes
Contraintes de performance Contraintes d'exécution Utilisation mémoire maximum 100000 kilo-octets Temps d'exécution maximum 3000 millisecondes Exemples d'entrée/sortie Exemple d'entrée 7 2 1 4 5 5 6 9 12 Exemple de sortie 2 Commentaire Joseph Nageant peut utiliser une barre de taille 4 et une barre de taille 5 pour construire le premier étage de l'échafaudage, ainsi qu'une barre de taille 5 et une barre de taille 6 pour construire le second étage de l'échafaudage. Le déséquilibre total est alors de .
Il est impossible d'obtenir un déséquilibre plus faible. Cependant, il existe d'autres manières d'obtenir le même déséquilibre (par exemple, en sélectionnant (5, 5) et (4, 6), on obtient également un déséquilibre total de 2)
Exemple d'entrée 5 2 10 6 4 1 3 Exemple de sortie 4 Commentaire Joseph Nageant peut utiliser une barre de taille 1 et une barre de taille 3 pour construire le premier étage de l'échafaudage, ainsi qu'une barre de taille 4 et une barre de taille 6 pour construire le second étage de l'échafaudage. Le déséquilibre total est alors de .
Il est impossible d'obtenir un déséquilibre plus faible.
Proposez votre solution Vous avez déjà résolu ce problème. Vous avez gagné 5192 points, soit 5192 points de base moins 0 points de malus.
Vous pouvez aussi envoyer un fichier : Aucun fichier choisiSélectionnez le langage de programmation :
Message facultatif résumant vos modifications
Historique des soumissions Version en cours (non soumise) Python ⋅ À l'instantPas de résumé Python ⋅ 22 oct. 2024 21:23Pas de résumé Python ⋅ 22 oct. 2024 21:22Pas de résumé Python ⋅ 22 oct. 2024 21:21Pas de résumé 5192 Python ⋅ 22 oct. 2024 21:19Pas de résumé Python ⋅ 22 oct. 2024 21:18Pas de résumé Python ⋅ 22 oct. 2024 21:15Pas de résumé 5192 C ⋅ 22 oct. 2024 21:14Pas de résumé C ⋅ 22 oct. 2024 21:14Pas de résumé Python ⋅ 22 oct. 2024 21:09Pas de résumé Python ⋅ 22 oct. 2024 21:01Pas de résumé 5192 Python ⋅ 22 oct. 2024 20:58 Énoncé Contraintes d'exécution Exemples d'entrée/sortie Proposez votre solution Prologin L'association Contribuer Contactez-nous Règlement Politique de Confidentialité Partenaires Signaler un problème sur le site Retrouvez nos projets libres sur notre GitLab Suivez nous !
Changer la langue
Français Sauvegardez votre langue préférée dans vos paramètres.
- Assistant
Bonjour !
Je comprends que vous souhaitez optimiser votre code Python actuel pour traiter de grandes entrées plus efficacement. Votre approche actuelle utilise une programmation dynamique en deux dimensions, ce qui peut devenir très lent lorsque
NetKsont grands (par exemple,N = 100,000etK = 50,000).Cependant, il est possible d'optimiser cette solution en réduisant l'utilisation de la mémoire et en accélérant les calculs en utilisant des tableaux NumPy pour vectoriser les opérations. Voici comment vous pouvez procéder :
Optimisation avec Programmation Dynamique 1D et NumPy
-
Réduction de l'espace mémoire : Au lieu d'utiliser une matrice 2D, nous utiliserons un tableau 1D qui sera mis à jour à chaque itération. Cela réduit considérablement la consommation de mémoire.
-
Vectorisation avec NumPy : NumPy permet de réaliser des opérations sur des tableaux entiers de manière beaucoup plus rapide que les boucles explicites en Python.
Voici le code optimisé :
import sys import numpy as np def main(): # Lecture de toutes les entrées en une seule fois input = sys.stdin.read().split() idx = 0 N = int(input[idx]); idx += 1 K = int(input[idx]); idx += 1 bars = list(map(int, input[idx:idx+N])) bars.sort() # Calcul des différences entre barres consécutives diffs = np.array([bars[i] - bars[i-1] for i in range(1, N)], dtype=np.int64) # Initialisation du tableau DP avec l'infini dp = np.full(K + 1, np.inf) dp[0] = 0 # Base case : 0 paire a un déséquilibre de 0 # Mise à jour du tableau DP en utilisant la vectorisation for d in diffs: # dp[k] est le minimum entre dp[k] actuel et dp[k-1] + d dp[1:] = np.minimum(dp[1:], dp[:-1] + d) # Affichage du résultat pour K paires print(int(dp[K])) if __name__ == "__main__": main()Explications Détailées :
-
Lecture et Tri :
- Nous lisons toutes les entrées en une seule fois pour optimiser la vitesse.
- Les barres sont triées afin de faciliter le calcul des différences optimales.
-
Calcul des Différences :
- Nous calculons les différences entre chaque paire consécutive de barres et les stockons dans un tableau NumPy
diffs.
- Nous calculons les différences entre chaque paire consécutive de barres et les stockons dans un tableau NumPy
-
Initialisation de DP :
- Nous initialisons un tableau
dpde tailleK+1rempli d'infini, saufdp[0]qui est 0 (car 0 paire a un déséquilibre de 0).
- Nous initialisons un tableau
-
Mise à Jour de DP avec NumPy :
- Pour chaque différence
ddansdiffs, nous mettons à jour le tableaudp. - L'opération
dp[1:] = np.minimum(dp[1:], dp[:-1] + d)compare les valeurs actuelles dedp[k]avecdp[k-1] + det prend le minimum pour chaquek. - Cette approche vectorisée remplace les boucles imbriquées classiques et est beaucoup plus rapide en Python grâce à NumPy.
- Pour chaque différence
-
Affichage du Résultat :
- Enfin, nous affichons la valeur de
dp[K], qui représente le déséquilibre minimal pourKpaires.
- Enfin, nous affichons la valeur de
Avantages de cette Approche :
- Performance : L'utilisation de NumPy pour vectoriser les opérations réduit considérablement le temps d'exécution, surtout pour de grandes entrées.
- Mémoire : En utilisant un tableau 1D au lieu d'une matrice 2D, la consommation mémoire est beaucoup plus faible, respectant ainsi les contraintes de mémoire.
Conclusion
Cette optimisation permet de transformer votre solution de
O(N*K)avec une utilisation inefficace de la mémoire en une solution beaucoup plus rapide et plus mémoriquement efficace en utilisant NumPy. Si vous rencontrez toujours des limitations de temps, envisagez d'utiliser un langage plus performant comme C++ pour les parties critiques de votre algorithme.N'hésitez pas à me faire savoir si vous avez besoin de plus d'assistance ou d'explications supplémentaires !
Bonne chance avec votre optimisation !
-