Existe-t-il une solution plus rapide pour le problème de la Grande Muraille de Google Code Jam

Considérez la question 1C de Google Code Jam suivante :

La Grande Muraille de Chine commence comme une ligne infinie, où la hauteur à tous les endroits est de .$0$

Certains nombre de tribus , N ≤ 1000 , va attaquer la paroi de la paroi en fonction des paramètres suivants : - une date de début, D , une résistance de démarrage S , un ouest coordonnée départ, W , et un départ est coordonnée, E . Cette première attaque se produit au jour D , sur la gamme [ W , E ] , à force S . S'il y a une partie de la Grande Muraille dans [ W , E ] qui a une hauteur < $N$$N \le 1000$$D$$S$$W$$E$$D$$[W,E]$$S$$[W,E]$$< S$, l'attaque est réussie, et à la fin de la journée, le mur sera construit de telle sorte que tout segment de celui-ci à l'intérieur de hauteur < S serait alors à la hauteur S (ou plus, si une autre attaque ce jour-là a frappé le même segment avec la force S ′ > S )$[W,E]$$< S$$S$$S' > S$

Chaque tribu effectuera jusqu'à attaques avant de battre en retraite, et chaque attaque sera déterminée de manière itérative par rapport à celle qui la précède. Chaque tribu a des δ D , δ X et δ S qui déterminent leur séquence d'attaques: ils attendront δ D ≥ 1 jours entre les attaques, ils déplaceront leur portée d'attaque de δ X unités pour chaque attaque (négatif = ouest, positif = est), bien que la taille de la portée reste la même et que leur force augmente / diminue également d'une valeur constante après chaque attaque.$1000$$\delta_D$$\delta_X$$\delta_S$$\delta_D \ge 1$$\delta_X$

Le but du problème est, étant donné une description complète des tribus attaquantes, de déterminer combien de leurs attaques réussiront.

J'ai réussi à coder une solution qui fonctionne, en environ 20 secondes: je crois que la solution que j'ai implémentée prend , où A = le nombre total d'attaques dans une simulation (max 1000000 ) et X = le nombre total de points de bord uniques sur les plages d'attaque (max 2000000 ).$O(A\log A + (A+X)\log X)$$A =$$1000000$$X =$$2000000$

À un niveau élevé, ma solution:

• Lit toutes les informations sur la tribu
• Calcule toutes les coordonnées uniques pour les plages d'attaque - O ( A $X$$O(A)$
• Représente le mur comme un arbre binaire mis à jour paresseusement sur les plages qui suit les valeurs de hauteur minimale. Une feuille est l'étendue de deux coordonnées X sans rien entre les deux, et tous les nœuds parents représentent l'intervalle continu couvert par leurs enfants. - O ( X log X $X$$X$$O(X \log X)$
• Génère toutes les attaques que chaque tribu effectuera et les trie par jour - $O(A \log A)$
• Pour chaque attaque, voyez si elle réussira ( heure de requête ). Lorsque le jour change, parcourez toutes les attaques réussies non traitées et mettez à jour le mur en conséquence ( enregistrez l' heure de mise à jour X pour chaque attaque). - O ( A log X $\log X$$\log X$$O(A\log X)$

Ma question est la suivante: existe-t-il un moyen de faire mieux que ? Peut-être existe-t-il un moyen stratégique de tirer parti de la nature linéaire des attaques successives des Tribus? 20 secondes semble trop long pour une solution envisagée (bien que Java puisse être à blâmer pour cela).$O(A\log A + (A+X)\log X)$

La marge d'amélioration évidente est cette étape:

Génère toutes les attaques que chaque tribu effectuera et les trie par jour - $O(A\log A)$

Nous savons que les tribus attaqueront à partir d'un jour particulier, à intervalles réguliers. Cela signifie que nous devrions essentiellement fusionner de nombreuses listes pré-triées. De plus, l'énoncé du problème nous dit qu'il n'y aura jamais plus de 1 000 tribus (c'est-à-dire 1 000 listes à fusionner); un tout petit nombre par rapport aux 1 000 000 d'attaques maximum! Selon le timing relatif de votre implémentation, le basculement pourrait réduire de moitié le temps de traitement.

C'est vraiment tout ce que je peux suggérer pour optimiser la complexité théorique, mais je n'ai aucune preuve que ce serait optimal après ce changement.

J'ai moi-même essayé le puzzle, mais j'ai utilisé une représentation beaucoup plus stupide du mur: un arbre de recherche binaire (C ++ std::mappour être précis) stockant les emplacements où la hauteur du mur change. Avec cela, j'ai pu ajouter et supprimer des nœuds selon les besoins (c'est-à-dire si une section compliquée était soumise à une grande attaque écrasante ou à plusieurs attaques de la même force touchées, le nombre de nœuds diminuerait considérablement). Cela a résolu la grande entrée en 3,9 secondes (sur mon ordinateur portable de développement de milieu de gamme). Je soupçonne qu'il y a plusieurs raisons à cette amélioration:

• Comme vous l'avez souligné, la boxe et le déballage peuvent coûter cher, mais les conteneurs basés sur des modèles de C ++ évitent complètement cela.
• Bien que la représentation du mur que j'ai utilisée soit théoriquement pire, dans la grande majorité des cas, la réduction dynamique du nombre de nœuds l'a rendue très rapide (la plupart des cas de test ont atteint un maximum de moins de 1 000 nœuds et tous sauf 2 étaient inférieurs à 10 000). . En fait, le seul cas qui a pris beaucoup de temps était le n ° 7, qui semble avoir testé de nombreuses plages sans intersection.
• Je n'ai utilisé aucun prétraitement (les étapes sont déterminées en gardant une trace de la prochaine attaque de chaque tribu et en recherchant le joint le plus bas à chaque tour). Encore une fois, cela est théoriquement pire, mais dans la majorité des cas, je soupçonne que les frais généraux inférieurs signifient que c'était plus rapide (je vais tester cela et vous revenir). Mise à jour : j'ai ajouté une file d'attente prioritaire pour les attaques, similaire à la méthode décrite ci-dessus (bien qu'au lieu de créer le grand tableau, je l'ai calculé à la volée) et j'ai vu le temps diminuer à 3,0 secondes pour la grande entrée.

En bref, même si je pense que votre algorithme est presque optimal dans le cas général, il existe plusieurs façons de l'accélérer pour des entrées typiques .

Ce qui suit a été supprimé de la question, car il s'agit d'une réponse.

La recherche d'autres discussions et de solutions réussies semble indiquer que la solution que j'ai décrite est à peu près l'algorithme attendu. Le ralentissement de ma solution est peut-être simplement dû à l'utilisation paresseuse de la boxe automatique et d'une structure arborescente basée sur un pointeur, plutôt que sur une matrice - donc je soupçonne que, si une solution existe, ce n'est probablement pas un tout beaucoup mieux que ce qui est ici.

La solution peut être trouvée ici . C'est très semblable à ce que j'ai publié ici; je suis donc beaucoup plus enclin à croire qu’il n’existe pas de solution plus efficace.