Coding Solution

Bender - Episode 3 – solution CodinGame en Python

Difficilecomplexity analysiscurve fittingstatisticsfloating pointMis à jour le
Réponse courte

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

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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é

TempsO(N)
MémoireO(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

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.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome