Bender - Episode 3 – solution CodinGame en Python
On divise chaque temps mesuré t par chaque fonction candidate f(n) (1, log n, n, n log n, n², n² log n, n³, 2ⁿ). Si les données croissent vraiment comme f, les rapports t/f(n) sont presque constants : on affiche donc la candidate dont les rapports ont le plus petit coefficient de variation (variance divisée par le carré de la moyenne). Une passe par candidate suffit, soit O(N) au total.
L'énoncé
On reçoit une série de mesures d'un programme : pour chacune, une taille de données n et le temps d'exécution correspondant. Il faut deviner sa complexité asymptotique et afficher exactement l'une des classes O(1), O(log n), O(n), O(n log n), O(n^2), O(n^2 log n), O(n^3) ou O(2^n).
Les mesures sont bruitées et les tailles varient énormément d'un test à l'autre : les jeux exponentiels s'arrêtent à quelques dizaines, alors que les jeux polynomiaux montent à plusieurs dizaines de milliers. Un jeu de validation est généré à partir de n^2.8 et attend pourtant O(n^3) : la réponse est la classe la plus proche, pas un ajustement exact.
La démarche, étape par étape
- Lire les pointsOn stocke les couples (n, t). Il y a au plus quelques milliers de points, donc les garder tous dans des listes ne pose aucun problème et permet de les reparcourir une fois par candidate.
- Normaliser par chaque candidatePour chaque candidate f, on calcule r = t / f(n) sur chaque point. Si t ≈ c·f(n), tous les r sont proches de la même constante c ; si f croît trop lentement, r ne cesse d'augmenter, et si f croît trop vite, r s'écrase vers zéro.
- Mesurer la platitudeOn évalue à quel point les rapports sont constants avec le coefficient de variation au carré : variance(r) / moyenne(r)². Diviser par le carré de la moyenne rend le score indépendant de la constante inconnue c, ce qui permet de comparer équitablement des candidates d'ordres de grandeur très différents.
- Protéger les points numériquement dangereuxOn ignore n = 1 pour tout ce qui contient log n (log 1 = 0 provoque une division par zéro) et les grands n pour 2ⁿ, car 2.0**n déborde d'un double au-delà de n ≈ 1023. On ne note une candidate que s'il reste au moins une poignée de points.
- Afficher la meilleureOn garde la candidate au score le plus bas et on affiche son nom au format O(...). Les égalités ne posent pas de problème en pratique : les scores de deux classes voisines diffèrent en général de plusieurs ordres de grandeur.
Complexité
O(N)O(N)Chacune des huit candidates est notée en une passe sur les N points, soit 8·N opérations. Les points sont stockés une fois pour que chaque candidate puisse les relire.
Code de la solution
Bender - Episode 3 – Python
import math
# candidate complexities, in the order the answer strings are expected
names = ["1", "log n", "n", "n log n", "n^2", "n^2 log n", "n^3", "2^n"]
funcs = [
lambda n: 1.0,
lambda n: math.log(n),
lambda n: float(n),
lambda n: n * math.log(n),
lambda n: float(n) ** 2,
lambda n: float(n) ** 2 * math.log(n),
lambda n: float(n) ** 3,
lambda n: 2.0 ** n,
]
count = int(input())
points = []
for _ in range(count):
num, t = map(int, input().split())
points.append((num, t))
best, best_score = 0, float("inf")
for i, f in enumerate(funcs):
ratios = []
for num, t in points:
if num < 2: # log(1) = 0 would divide by zero
continue
if i == 7 and num > 1000: # 2.0 ** n overflows a double past ~1023
continue
ratios.append(t / f(num))
if len(ratios) < 5:
continue
mean = sum(ratios) / len(ratios)
if mean <= 0:
continue
# squared coefficient of variation: 0 if t is exactly c * f(n)
score = sum((r - mean) ** 2 for r in ratios) / len(ratios) / mean ** 2
if score < best_score:
best, best_score = i, score
print("O({})".format(names[best]))
Erreurs fréquentes
- Diviser par log(1)Beaucoup de jeux commencent à n = 1, et log(1) = 0. Toute candidate contenant log n divise alors par zéro ; il faut sauter ces points plutôt qu'ajouter un epsilon minuscule, qui créerait un rapport aberrant énorme.
- Débordement sur 2ⁿ2.0**n lève OverflowError en Python (et donne Infinity en Java ou en C) dès que n dépasse environ 1023. Les jeux polynomiaux vont bien au-delà, donc la candidate exponentielle doit ignorer ces points au lieu de planter.
- Utiliser la variance bruteLa variance simple de t/f(n) dépend de l'échelle de t/f(n) : une candidate n³ a des rapports minuscules, donc une variance minuscule, même quand elle est fausse. Il faut normaliser par le carré de la moyenne, ou comparer des logarithmes, avant de confronter les candidates.
- Le test de validation en n^2.8Un jeu généré à partir de n^2.8 se situe entre n² log n et n³. Une règle de score qui surpondère les petits n peut choisir n² log n ; la méthode des rapports sur toute la plage privilégie n³, qui est la réponse attendue.
Pour aller plus loin
La méthode des rapports a une faiblesse bien réelle : le coût fixe. Si les temps mesurés ressemblent à 5000 + c·f(n), les points de petit n sont dominés par le 5000, les rapports ne sont plus plats et la méthode dérive d'une classe vers le bas (n est annoncé comme log n, n log n comme n). Un test rapide sur des données synthétiques le montre très bien. L'alternative robuste est une régression des moindres carrés en log-log : on régresse log t sur log n sur la moitié supérieure des points, où le coût fixe devient négligeable ; la pente donne l'exposant (0, 1, 2, 3), une pente entre deux entiers mais toujours au-dessus de l'entier trahit un facteur log supplémentaire, et une droite dans le plan log t en fonction de n (et non de log n) révèle 2ⁿ. Sur les jeux de CodinGame, le simple test des rapports suffit, mais la régression log-log est ce qu'on utiliserait sur de vrais benchmarks.
Questions fréquentes
Pourquoi comparer t/f(n) plutôt qu'ajuster une courbe ?
Si t = c·f(n), diviser par f supprime la croissance et laisse une constante. Vérifier à quel point le résultat est constant demande une passe par candidate et aucune algèbre linéaire, ce qui suffit à séparer huit classes bien espacées.
Comment distinguer n log n de n ?
Sur une plage comme 1 à 10 000, log n passe de 0 à environ 9, donc t/n augmente encore nettement pour un jeu en n log n. La variance normalisée capte cette dérive, à condition de sauter n = 1.
Une régression des moindres carrés est-elle obligatoire ?
Non. Un ajustement complet sur le modèle n^a·b^n·log n est l'approche la plus générale, mais le test des rapports ou une pente en log-log passe tous les tests et se débogue bien plus facilement.