Bonjour ! Je n'arrive pas à un exercice de France.ioi, mon programme passe 12 tests sur 22, il ne réussi pas les autres car il est trop lent. Merci de votre aide ! 

ÉNONCÉ : 

Limites de temps et de mémoire (Python)

• Temps : 2 s sur une machine à 1 GHz.
• Mémoire : 64 000 ko.

Contraintes

Entrée

Sortie

Exemples

Exemple 1

entrée :

6 7
1 0 0 1 0 0 1
0 0 0 0 0 0 0
1 0 0 0 0 0 0
0 0 0 0 0 0 0
0 1 0 0 0 0 1
1 0 0 0 1 0 1

sortie :

4

Mon Programme :

def mini_carre(pos_depart,tableau,cote):
    try:
        for i in range(pos_depart[0],cote+pos_depart[0]):
            for j in range(pos_depart[1],cote+pos_depart[1]):
                if tableau[i][j]==1:
                    return False,cote
        return True,cote
    except:
        return False,cote

def trouve_carre_possibles(tableau, ligne):
    possible = []
    for i in range(len(tableau[ligne])):
        c = 0
        if tableau[ligne][i]==0:
            try:
                while tableau[ligne][i+c]==0:
                    if c>0:
                        possible.append(((ligne,i),c+1))
                    c+=1
            except:
                pass
    return possible

nbLignes, nbColonnes = list(map(int,input().split()))
l = []
for i in range(nbLignes):
    l.append(list(map(int,input().split())))

maxi = 1
for i in range(len(l)):
    for reponses in trouve_carre_possibles(l,i):
        if reponses[1]>maxi:
            rep = mini_carre(reponses[0],l,reponses[1])
            if rep[0]:
                score = rep[1]
                if score>maxi:
                    maxi=score
print(maxi)

-
Edité par Ethannnn__ 16 septembre 2021 à 1:00:14

Je ne connais pas le meilleur algorithme pour ce jeu.
Voici tout de même un truc:
            for j in range(pos_depart[1],cote+pos_depart[1]):
                if tableau[i][j]==1:
Essaies de remplacer par:
    if any(t for t in tableau[i][pos_depart[1] : cote+pos_depart[1]]):
        return False

-
Allons un peu plus loin ...
p0, p1 = position_depart
if any(t for tab in tableau[p0:p0+cote] for t in tab[p1:p1+cote]):
    return False

Ou plus simple:
    p0, p1 = position_depart
    return all(not t for tab in tableau[p0:p0+cote] for t in tab[p1:p1+cote])

-
Edité par PierrotLeFou 16 septembre 2021 à 3:36:06

Merci beaucoup !  Je ne connaissais pas les fonctions any() et all(), cependant même avec les changements que vous m'avez dit de faire mon programme reste trop lent et en plus fait des erreurs qu'il ne faisait pas avant...

Bonjour,

Le problème c'est pas tant ton programme que l'algo que tu utilises. Il faut utiliser une autre approche que la force brute pour améliorer les performances, en l'occurrence tu peux essayer la programmation dynamique.

Ce que l'on peut faire ici c'est qu'en plus de ta matrice que l'on te donne et que tu nommes L, tu va initialiser une autre matrice S (comme solutions) de mêmes dimensions que L avec des 0 partout. S[i,j] contiendra la longueur du côté du plang grand carré de 0 que tu peux construire à partir de [i,j] dans L, [i,j] étant le coin inférieur droit.

Il est relativement évident que si L[i,j]==1 alors S[i,j]=0. Si L[i,j]==0 alors la longueur du côté du plus grand carré constructible sera 1 + la longueur du côté du carré intersection des carrés constructibles à partir de [i-1,j],[i,j-1] et [i-1,j-1] … soit S[i,j]=1+min( S[i-1,j], S[i,j-1], S[i-1,j-1] ).

Il faudra faire attention aux calculs aux bords haut et gauche de la matrice … mais l'idée est là. L'algorithme sera en O( nlig × ncol ) en temps et en espace.

Tu peux optimiser un peu plus en remarquant qu'à chaque étape tu n'as besoin de connaître que la ligne de S précédant celle que tu construis ce qui réduit la complexité spatiale à du O( max(nlig, ncol) ) … qu'on peut à nouveau réduire en O( min(nlig, ncol) ) en transposant la matrix L s'il faut, par exemple …

La programmation dynamique est une technique qu'il faut connaître quand on se frotte aux challenges info.

Si on garde l'idée que la matrice S est de même dimension que L, on peut accélérer encore.
On fait la première ligne et la première colonne à part
Pour la première ligne, on considère l'élément précédent de la ligne seulement.
Pour la première colonne, on considère seulement l'élément correspondant de la ligne précédante.

On met d'office S[0][0] = 1 - L[0][0]
Ensuite, on n'a plus à tester si on est hors bornes (sauf la fin).
En fait, S pourrait se résumer à une matrice [2 x colonnes] (je pense ...)
On garde le plus grand nombre trouvé, donc on n'a pas besoin de parcourir S une autre fois.

@White Crow: a-t-on vraiment besoin de S[i-1][j-1] car les deux autres ont été évalués en tenant compte de celui-ci?

-
Edité par PierrotLeFou 16 septembre 2021 à 18:12:01

PierrotLeFou a écrit:

[...]

@White Crow: a-t-on vraiment besoin de S[i-1][j-1] car les deux autres ont été évalués en tenant compte de celui-ci?

-
Edité par PierrotLeFou hier à 18:12

Je m'en suis rendu compte. C'est pourquoi je l'ai rajouté dans mon code. Je ne sais pas s'il passerait tous les tests.
Il est sûrement rapide avec l'aspect de la programmation dynamique que tu proposes.
J'ai réussi facilement à ramener ma matrice S à du ]2, colonnes]
La demande de France IOI n'est pas trop contraignante au niveau de la mémoire.
Puisqqu'on parcours la matrice L une seule fois de haut en bas, on aurait pu lire une seule ligne à la fois et faire le traitement sur cette ligne.
La complexité mémoire aurait été O(3 * colonnes. On n'aurait sans doute rien gagné en vitesse, seulement en mémoire.
Bien que doublement indexer une liste de liste est sans doute plus lent que d'indexer une simple listte ...

On pourrait remplacer le tuple par un if, car le tuple est évalué au complet, quelle que soit la valeur de la case (0 ou 1)

-
Edité par PierrotLeFou 18 septembre 2021 à 3:08:11

PierrotLeFou a écrit:

Je m'en suis rendu compte. C'est pourquoi je l'ai rajouté dans mon code. Je ne sais pas s'il passerait tous les tests.

Ton code plus haut passe tous les tests sauf un, donnant une mauvaise réponse pour un rectangle tel que 

1 0
1 1

Il est légèrement plus rapide que le code de correction sur le test le plus exigeant (0,53s vs 0,59s).

PierrotLeFou a écrit:

Bien que doublement indexer une liste de liste est sans doute plus lent que d'indexer une simple listte ...

Cette fois, ton code passe tous les tests. Le temps est quasiment identique sur le test 20 : 0.45. 

Note que ta ligne cote = max(*S[l1], cote) plante sur france-ioi, je l'ai changée en cote = max(cote, *S[l1]) d'où le code suivant :

lignes, colonnes = map(int, input().split())
L = list(map(int, input().split()))
S0, S1= [[1 - L[c] for c in range(colonnes)], [0]*colonnes]
l0, l1 = 0, 1
cote = max(S0)
for l in range(1, lignes):
    L = list(map(int, input().split()))
    S1[0] = 1 - L[0]
    for c in range(1, colonnes):
        # Je suppose arbitrairement que les 0 sont plus fréquents.
        if not L[c]: S1[c] = min(S0[c-1], S0[c], S1[c-1])+1
        else: S1[c] = 0
    # Plus rapide que de tester à chaque résultat.
    cote = max(cote, *S1)
    S0, S1 = S1, S0
print(cote)

pour info, l'exercice est ICI.

Personnellement, je trouve qu'il est peu lisible de concentrer le code surtout si le bénéfice en temps est limité voire inexistant. J'aurais scindé capture des entrées et l'algorithme (ton input dans la boucle en l, note au passage que la pep-8 ne recommande pas, et à juste titre selon moi, l'usage de variable nommé l). Je n'aurais pas optimisé la table dynamique sur deux lignes ce qui oblige à faire des choses peu lisibles (tes échanges de lignes). Pareil j'aurais initialisé dès le départ, je trouve ça plus clair.

Une fois l'algo de programmation dynamique implémenté (ce qui est le progrès le plus important, et de loin), tu peux optimiser facilement certaines choses bas niveau :

• Les accès L[i][j] ont un coût (2 getitem) s'ils sont répétés donc si i ne change pas, on peut poser t=L[i] ce qui économise un getitem. Dans ton cas (avec ton S) et en utilisant l0 et l1 directement, ton code passe de 0.45s à 0.43s.
• J'allais te dire de faire cette petite optimisation mais en l'ayant appliqué à ton code, je vois que c'est une optimisation très rentable (ton temps passe de 0.43s à 0.34s). Dans ton code, tu convertis ligne 7 tes entrées en utilisant la fonction int. Or, la fonction int est une fonction très complexe capable de faire de multiples choses et son exécution est donc peut-être relativement lente surtout si on l'appelle 100000 fois (c'est le cas pour un rectangle 350x350). Or que veux-tu faire ? juste convertir "0" en 0 et "1" en 1, pas besoin d'utiliser la fonction int pour ça ! il suffit de changer ta ligne de capture ligne 7 en 

  L = [0 if z =='0' else 1 for z in input().split()]

• Il y a une optimisation également très appréciable, inutile en fait ici vue la remarque précédente. Ne pas convertir du tout les données "0" et "1" en entier (pas besoin), les laisser sous forme de caractère, plus précisément stocker des lignes de caractères 0 ou 1, le code est quasiment inchangé et on évite d'utiliser int et le parcours de ligne est peut-être plus rapide que pour des listes.
• Ne pas utiliser la fonction min (comme pour int, c'est une fonction complexe) et j'ai calculé la taille approprié du côté ce qui me fait gagner 0.08s.

n, p= map(int, input().split())
b = [''.join(input().split()) for _ in range(n)]
c=[[0]*p for _ in range(n)]
# init
cpt=0
for j in range(p):
    if b[0][j]=='0':
        c[0][j]=1
        cpt+=1
for i in range(n):
    if b[i][0]=='0':
        c[i][0]=1
        cpt+=1
    
side=1*bool(cpt)
for i in range(1,n):
    ci=c[i]
    ci1=c[i-1]
    for j in range(1,p):
        if b[i][j]=='0':
            ci[j]=1+(ci[j-1] if ci[j-1]<ci1[j] else ci1[j] if ci1[j]<ci[j-1] else ci[j-1] if ci[j-1] <= ci1[j-1] else ci1[j-1])
            if ci[j]>side:
                side=ci[j]
print(side)

 Au passage, cette question avait déjà été abordée en novembre dernier : ICI , discussion à laquelle tu avais participé  et où l'algo de programmation dynamique avait été évoqué. 

-
Edité par PascalOrtiz 18 septembre 2021 à 19:19:19

> note au passage que la pep-8 ne recommande pas, et à juste titre selon moi, l'usage de variable nommé l)

Que veux-tu dire? Est-ce que 'l' ressemble à '1' (un)?

 Oui, je pense que c'est la raison, c'est parfois visuellement indistinguible. De même pour la lettre O.

> Même si le plus gros de l'optimisation réside dans l'algo de programmation dynamique, je voulais faire les autres pour ma culture personnelle ...

Oui, j'ai mesuré et en comparaison, les entrées et l'initialisation, c'est epsilon, inutile d'optimiser, il n'y a rien à gagner.

> Quel est le coût pour échanger deux listes comme S0, S1 = S1, S0 ?

epsilon au carré, c'est juste un échange de pointeurs. Je t'ai parlé de ça car je trouve que ça nuit à l'intelligibilité du code et le gain en espace me semble peu intéressant, on a déjà un tableau de même taille.

> Est-ce que les np.array auraient apporté quelque chose en vitesse?

Effectivement je n'avais pas pensé à l'utiliser mais de toute façon, sur france-ioi, Numpy n'est pas accessible. Numpy n'apporte aucun bénéficie si tu ne vectorises rien et au contraire, dans ce cas, le code sera plus lent, cf. ICI où tu as un exemple de l'usage de Numpy qui multiple par 3 le temps d'exécution d'un code Python.  Pour la question de la vectorisation de ce code, j'ai le sentiment que c'est faisable mais ça ne me semble pas si évident. 

-
Edité par PascalOrtiz 18 septembre 2021 à 21:01:45

Je suis retourné sur le lien cité. Il faut croire que je n'ai pas saisi à l'époque ...
Mes petits tests me laissent croire que parcourir une liste ou une chaîne donnent des temps comparables (714ms vs 740ms).
Par contre, la conversion:
L = input().replace(' ', '')
est plus rapide que:
L = ''.join(input().split())
On gagnerait 400 ms pour 10 millions, donc 4 ms pour 100 mille
Je vais sans doute retester la différence avec les améliorations suggérées comme deux listes S0 et S1
Je garde mon idée de ne lire qu'une ligne à la fois, même si le gain en temps est négligeable.
Dans la mesure où ce n'est pas pire, j'ai la satisfaction d'optimiser également en mémoire.

edit: que veux-tu dire par "vectorisation"? Faire en sorte qu'une matrice soit représentée par un simple vecteur, et où on calcule soi-même l'indice?

Si c'est ça, je saurais le faire.

-
Edité par PierrotLeFou 19 septembre 2021 à 8:15:49

PierrotLeFou a écrit:

L = input().replace(' ', '')
est plus rapide que:
L = ''.join(input().split())
On gagnerait 400 ms pour 10 millions, donc 4 ms pour 100 mille 

Ce n'est peut-être que du bruit ces 4 ms. Au demeurant, je l'avais envisagé mais les entrées comptent tellement peu dans ce problème que je n'avais pas essayé. Je viens de regarder et ça semble plutôt donner un temps moins bon ...

PierrotLeFou a écrit:

edit: que veux-tu dire par "vectorisation"? Faire en sorte qu'une matrice soit représentée par un simple vecteur, et où on calcule soi-même l'indice?

Ah non, ce n'est pas du tout cela. Je te donne ce qui est écrit dans le Guide de l'utilisateur de Numpy :

Vectorization describes the absence of any explicit looping, indexing, etc., in the code - these things are taking place, of course, just “behind the scenes” in optimized, pre-compiled C code.

Tu dois donc utiliser des fonctions ou des opérations built-in Numpy, sans utiliser aucune boucle for Python ou apparentée, pour réaliser la transformation du tableau. Le problème est qu'ici on souhaite faire une opération locale où on doit prendre le minimum de trois coefficients en diagonale et que le nouveau tableau dépend du précédent, donc ça ne me paraît pas du tout simple à faire en Numpy. Au passage, il y a une fonction Numpy qui s'appelle vectorize et qui ne vectorise rien (elle boucle en Python).

Certains algorithmes de programmation dynamique (par exemple Floyd-Warshall) peuvent être vectorisés avec Numpy comme on peut le voir dans le code source de la lib de graphes NetworkX. Mais ici, la situation me semble peu s'y prêter.

Je donne un exemple  ICI non évident de situation de vectorisation (et qui vient d'ailleurs d'une question postée sur ce forum).

-
Edité par PascalOrtiz 19 septembre 2021 à 10:09:27

On peut encore améliorer un peu en testant le maximum une seule fois tout à la fin plutôt que de brancher à chaque case, ce qui fait passer sous la barre des 0.30s pour le test n°20. Le code devient :

import sys
n, p= map(int, input().split())
b=[''.join(L.split()) for L in sys.stdin.read().strip().split('\n')]
c=[[0]*p for _ in range(n)]
# init
cpt=0
for j in range(p):
    if b[0][j]=='0':
        c[0][j]=1
        cpt+=1
for i in range(n):
    if b[i][0]=='0':
        c[i][0]=1
        cpt+=1
    
# Dynamic algo
for i in range(1,n):
    ci=c[i]
    ci1=c[i-1]
    for j in range(1,p):
        if b[i][j]=='0':
            ci[j]=1+(ci[j-1] if ci[j-1]<ci1[j] else ci1[j] if ci1[j]<ci[j-1] else ci[j-1] if ci[j-1] <= ci1[j-1] else ci1[j-1])
print(max(z for L in c for z in L))

Noter que l'exercice est corrigé sur Youtube ici.

PierrotLeFou a écrit:

Pour le max, j'avais pensé de le faire à la fin de chaque ligne ... mais pas à la toute fin du traitement.
Je sais qu'on fait des économies de bout de chandelles ...

b = [input().replace(' ', '') for _ in range(n)]

Si j'ai bien compris, tu lis tout le stream de stdin d'un seul coup et tu split en lignes.
À quoi ser cpt?

b = [input().replace(' ', '') for _ in range(n)] ou autre chose est indifférent, si tu prends un fichier avec un plateau 1000x1000 (car 350x350 est trop petit) les entrées mettront au plus 0.001s alors que l'algo avec la double boucle mettra 0.33s.

Oui, pour stdin, c'est en effet ce que je fais mais uniquement après avoir examiné les dimensions du plateau

cpt contient le nombre de cases vides dans la ligne et la colonne d'initialisation. De toute façon, du point de vue du temps d'exécution, cela comptera pour 0.000s quoi qu'on écrive comme code.

PierrotLeFou a écrit:

350 350                                                                                                                 
122500                                                                                                                  
matrice 0.012 secondes                                                                                                  
vecteur 0.014 secondes

Je detere un peu le sujet avec cette approche recursive. 

Auriez-vous des idees de la complexite de cette algorithme et des conseils pour l'arranger?

import sys
Str = input().split()
nbLignes = int(Str[0])
nbColonnes = int(Str[1])

tab=[''.join(L.split()) for L in sys.stdin.read().strip().split('\n')]

maxi = 0

def haut(i,j,m):
    ii = i
    while(ii>=0 and tab[ii][j]=='0'):
        if i-ii==m:
            return 1
        ii = ii-1
    return 0

def gauche(i,j,m):
    ii = j
    while(ii>=0 and tab[i][ii]=='0'):
        if j-ii==m:
            return 1
        ii = ii-1
    return 0


def disco(i,j,m):
    # print(i,j,m)
    if i>=nbLignes or j>=nbColonnes or tab[i][j]=='1':
        return m
    if m!=0:
        mhaut = haut(i,j,m)
        mgauche = gauche(i,j,m)
        if not (mhaut==1 and mgauche==1 ):
            return m
    return disco(i+1,j+1,m+1)
    
   


for i in range(nbLignes):
    for j in range(nbColonnes):
        maxi = max(maxi,disco(i,j,0))

print(maxi)

Merci!

josmiley a écrit:

misère! je l'avais résolu il y a fort longtemps en 7 lignes juste avec des additions ... je suis incapable de dire comment j'avais raisonné à cette époque, mais je vois que je suis beaucoup moins intelligent que dans ma jeunesse.

haaaa! je me souviens ... en inversant les 0 et les 1 j'avais gratté des lignes. Mais sinon c'est le même algo que celui de PierrotLeFou.

(l,c),mx = map(int, input().split()),0
z = [[m=='0' for m in input().split()] for _ in range(l)]

for x in range(1,l):
    for y in range(1,c):
        if z[x][y]:
            z[x][y] = min((z[x][y-1],z[x-1][y-1],z[x-1][y])) + 1
        if z[x][y] > mx:
            mx = z[x][y]

print(mx)

sinon j'ai aussi une version utilisant un dict plutôt qu'une liste de listes, mais j'ai pas testé les perfs.

(l,c),z = map(int, input().split()),{}
for y in range(l):
    for x,m in enumerate(input().split()):
        if m=='0':
            z[(y,x)] = min(z.get((y-1,x),0),z.get((y-1,x-1),0),z.get((y,x-1),0)) + 1
print(max(z.values()))

-
Edité par josmiley 2 mai 2024 à 6:33:33

re,

ma dernière tentative, passe aussi en dessous des 0.30s au test n°20 comme vu précédement, j'en suis plutôt fier:

def foo():
    l,c = map(int, input().split())
    l += 1
    c += 1
    z = [0]*(l)*(c)
    for y in range(c,l*c,c):
        for x,m in enumerate(input().split(),y+1):
            if m=='0':
                z[x] = min(z[x-1],z[x-c],z[x-c-1]) + 1
    print(max(z))

foo()

j'ai aussi une version avec une seule boucle mais c'est un poil plus lent:

import sys
def foo():
    l,c = map(int, input().split())
    l += 1
    z = [0]*(l)*(c+1)
    for x,m in enumerate(sys.stdin.read().split(),c)
        if m=='0':
            z[x] = min(z[x-1],z[x-c-1],z[x-c-2]) + 1
    print(max(z))

foo()

-
Edité par josmiley 10 mai 2024 à 19:38:50

Bonjour, 

Peut-être une mauvaise manip de ma part mais ton premier code renvoie un IndexError : 

Traceback (most recent call last):
  line 12
    foo()
  line 10, in foo
    z[x] = min(z[x-1],z[x-c],z[x-c-1]) + 1
IndexError: list index out of range

Sinon, j'ai repris mon ancien code dans ce fil et je l'ai juste enveloppé dans une fonction et je gagne 25%, le test n°20 passe à 0.22 :

import sys
def solve():
   n, p= map(int, input().split())
   b=[''.join(L.split()) for L in sys.stdin.read().strip().split('\n')]
   c=[[0]*p for _ in range(n)]
   # init
   cpt=0
   for j in range(p):
       if b[0][j]=='0':
           c[0][j]=1
           cpt+=1
   for i in range(n):
       if b[i][0]=='0':
           c[i][0]=1
           cpt+=1
       
   # Dynamic algo
   for i in range(1,n):
       ci=c[i]
       ci1=c[i-1]
       for j in range(1,p):
           if b[i][j]=='0':
               ci[j]=1+(ci[j-1] if ci[j-1]<ci1[j] else ci1[j] if ci1[j]<ci[j-1] else ci[j-1] if ci[j-1] <= ci1[j-1] else ci1[j-1])
   print(max(z for L in c for z in L))
   
solve()

Yoël Cahn : ton code est trop lent sur tous les tests 13 à 20. Sur  le test 12, ton code est 1,55 s au lieu de 0,07 s. Pas regardé la logique de ton code, mais une récursivité mal utilisée peut être lente, typiquement si tu ne mémorises pas certains résultats. La programmation dynamique est souvent une forme de récursivité mais pour qu'elle soit efficace, il faut mémoriser des résultats antérieurs, cf. ce cas typique de récursivité inefficace.

"Peut-être une mauvaise manip de ma part mais ton premier code renvoie un IndexError :"

erreur de recopie, j'ai corrigé

sinon dans ton code, à quoi sert la variable cpt ?

-
Edité par josmiley 10 mai 2024 à 19:39:46

Cette fois, ton code fonctionne, c'est vrai que c'est bien compact.

Le cpt sert uniquement à augmenter la température de la pièce !

Je remarque que changer le générateur emboîté final en liste et changer le b[i] en bi mémorisé me fait passer à 0.20s au test n°20 :

import sys
def solve():
   n, p= map(int, input().split())
   b=[''.join(L.split()) for L in sys.stdin.read().strip().split('\n')]
   c=[[0]*p for _ in range(n)]
   # init
   cpt=0
   for j in range(p):
       if b[0][j]=='0':
           c[0][j]=1

   for i in range(n):
       if b[i][0]=='0':
           c[i][0]=1
        
   # Dynamic algo
   for i in range(1,n):
       ci=c[i]
       ci1=c[i-1]
       bi=b[i]
       for j in range(1,p):
           if bi[j]=='0':
               ci[j]=1+(ci[j-1] if ci[j-1]<ci1[j] else ci1[j] if ci1[j]<ci[j-1] else ci[j-1] if ci[j-1] <= ci1[j-1] else ci1[j-1])
   print(max([z for L in c for z in L]))
    
solve()