Limites de temps et de mémoire (Python)

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

Contraintes

Entrée

Sortie

Exemple

entrée :

10 8
0 1 1 0 0 0 0 0
0 1 1 1 0 0 0 0
0 0 0 0 0 1 0 0
0 1 1 1 1 0 0 0
0 0 1 1 1 0 0 0
0 0 0 1 1 0 0 0
0 1 0 0 1 0 0 0
0 0 0 0 0 0 1 0
0 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
1 1 0 1 1 1 1 0
1 1 0 0 1 1 1 0
1 0 0 0 0 1 1 0
0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0

sortie :

12
1 8
2 4
2 5
2 6
2 7
3 5
3 6
3 7
4 6
4 7
5 4
5 7

Et voici mon code :

def main():

    import sys
    input = sys.stdin.readline
    print = sys.stdout.write
    
    maximum = 0
    swarm = set()
    vectorsA = set()
    vectorsB = set()
    lines, cols = map(int, input().split())
    
    # récupère les coordonnées des points
    def GetVectors(vectors):
        for line in range(lines):
            tmp = list(map(int, input().split()))
            for col in range(cols):
                if tmp[col] == 1:
                    vectors.add((line, col))
    
    # intersecte le set des vecteurs (A + AB) avec B pour obtenir les correspondances         
    def GetSwarm(translation):
        total = 0
        tmp = set()
        for vA in vectorsA:
            tmp.add((vA[0] + translation[0], vA[1] + translation[1]))
        tmp = tmp & vectorsB
        total = len(tmp)
        if total > maximum:
            return total, tmp
        return maximum, swarm
        
    GetVectors(vectorsA)
    GetVectors(vectorsB)
    for vA in vectorsA:
        for vB in vectorsB:
            maximum, swarm = GetSwarm((vB[0] - vA[0], vB[1] - vA[1])) # calcule chaque vecteur AB

    # affiche le résultat  
    print(str(maximum))
    print('\n')
    for coord in swarm:
        print(str(coord[0] + 1))
        print(' ')
        print(str(coord[1] + 1))
        print('\n')
        
main()

Mon algo calcul tous les vecteurs possibles entre les points de l'image a et b puis compte le nombre de correspondance entre les deux images pour chaque vecteur translation. C'est trop lent pour la majorité des tests. Quelqu'un aurait une idée pour le rendre plus rapide ? Merci d'avance

Ce sujet a déjà été discuté ici:

https://openclassrooms.com/forum/sujet/essaim-de-drones#message-94484094

10/20 pour moi

Hey pierrot,

j'ai lu l'autre topic et en partant sur du bit à bit j'ai ça qui trouve le bon nombre mais pas encore les coordonnées.

def main():

    import sys
    input = sys.stdin.readline
    #print = sys.stdout.write

    def GetMax(imageA, imageB):
        tmp = bin(imageA & imageB)
        num = len([one for one in tmp if one == '1'])
        if num > maximum:
            return num 
        return maximum

    imageA = ""
    imageB = ""
    lines, cols = map(int, input().split())
    for loop in range(lines):
       imageA += "".join(input().rstrip().split())
    for loop in range(lines):
       imageB += "".join(input().rstrip().split())

    
    imageA = int(imageA, 2)
    imageB = int(imageB, 2)
    maximum = 0
    size = lines * cols
    for loop in range(size):
        maximum = GetMax(imageA >> loop, imageB)
        maximum = GetMax(imageA << loop, imageB)

    print(maximum)
               
main()

Et qui est encore plus lent ahah !

modif, enlever des lignes

-
Edité par tomleuj 18 décembre 2022 à 15:09:40

tomleuj a écrit:

Hey pierrot,

j'ai lu l'autre topic et en partant sur du bit à bit j'ai ça qui trouve le bon nombre mais pas encore les coordonnées

Et qui est encore plus lent ahah !

Tiens, j'avais commencé par du bit à bit aussi et, c'était plus lent aussi pour moi.

sur 20 tests j'ai 10 réussis, 7 limites de temps dépassé, 3 erreurs de résultat.

mon code: (qui ressemble beaucoup à celui de PierrotLeFou, les grands esprits se rencontrent) 

import sys
_,nbcol,*l = sys.stdin.read().split()
nbcol  = int(nbcol)
image1 = frozenset(point1 for point1,c in enumerate(l[:len(l)//2]) if c=='1')
image2 = frozenset(point2 for point2,c in enumerate(l[len(l)//2:]) if c=='1')
shifts = frozenset(point2-point1 for point1 in image1 for point2 in image2)-{0}
finale = image1&image2

for shift in shifts:
    compare = frozenset(point1+shift for point1 in image1)&image2
    if len(compare)>len(finale):
        finale = compare

print(len(finale))
for point in finale: print(point//nbcol+1,point%nbcol+1)

Mais je vais rebucher sur du bit à bit... 

-
Edité par josmiley 18 décembre 2022 à 22:25:54

@tomleuj:
Tu peux optimiser ceci:
        num = len([one for one in tmp if one == '1'])
 
from time import perf_counter
from random import choices
n = 1000000
b = "".join(choices(['0', '1'], k=n))
begin=perf_counter()
num = len([c for c in b if c == "1"])
print(round(perf_counter()-begin, 3), "secondes")
begin = perf_counter()
num = b.count('1')
print(round(perf_counter()-begin, 3), "secondes")
 
0.038 secondes                                                                                                          
0.003 secondes

-

Autre chose: tu places les colonnes les unes à la suite des autres.
Quand on décales par colonnes, c'est correct de faire des shift >> ou <<
Mais quand on décale par  lignes, on se déplace d'une ligne à une autre, le décalage n'est pas le même que pour les colonnes.
Il faudrait un tableau de lignes dans lequel chaque nombre représente une colonne.

-
Edité par PierrotLeFou 19 décembre 2022 à 3:32:34

ok, en repartant sur du vecteurs, en changeant le tableau.

on stock la fréquence des vecteurs dans un tab[xb-xa][yb-ya]

les coordoonées du tableau représente les vecteurs, le tableau contient le nombre d'occurence

def main():
    import sys
    input = sys.stdin.readline
    print = sys.stdout.write
   
    lines, cols = map(int, input().split())
    vectorsA = [(l, c) for l in range(lines) for c, p in enumerate(map(int, input().split())) if p]
    vectorsB = [(l, c) for l in range(lines) for c, p in enumerate(map(int, input().split())) if p]
    translations = [[0] * (cols * 2) for l in range(lines * 2)]
    for vA in vectorsA:
        for vB in vectorsB:
            translations[lines + vB[0] - vA[0]][cols + vB[1] - vA[1]] += 1    
    swarm = ()
    maximum = 0
    for line in range(lines *2):
        for col in range(cols *2):
            if translations[line][col] > maximum:
                maximum = translations[line][col]
                swarm = (line - lines, col - cols)
    print(str(maximum))
    print('\n')
    for vA in vectorsA:
        try:
           vectorsB.index((vA[0] + swarm[0], vA[1] + swarm[1]))
           print(str(vA[0] + swarm[0] + 1))
           print(' ')
           print(str(vA[1] + swarm[1] + 1))
           print('\n')
        except:
            pass
               
main()

ça marche mieux, 15 / 20

tomleuj a écrit:

ça marche mieux, 15 / 20

Je suis encore pus déconcerté ...

L'idée c'est que c'est peut être un peu moins laborieux de faire ressortir le vecteur

mais après pour afficher les coordonnées je sais pas si c'est opti mon système

l'autre moyen que je vois c'est de faire une copie de l'image B et de tester pour chaque point dans A si y'a un point dans B après la translation

je ne sais pas si try et .index() sont lourd ?

Après, une personne très diligente sur le forum de FranceIOI m'a dit que les chapitres d'entrainement ont été ajouté après et ne sont pas conçus pour le python. Son algo en c++ passe tous les tests, mais celui en python n'en passe que 75%

-
Edité par tomleuj 20 décembre 2022 à 12:17:53

As-tu son algo en C++? On pourrait essayer de le traduire.

C'est autant une question d'algo que de code.

-
Edité par PierrotLeFou 20 décembre 2022 à 18:35:38

tomleuj a écrit:

ok, en repartant sur du vecteurs, en changeant le tableau.

on stock la fréquence des vecteurs dans un tab[xb-xa][yb-ya]

les coordoonées du tableau représente les vecteurs, le tableau contient le nombre d'occurence

def main():
    import sys
    input = sys.stdin.readline
    print = sys.stdout.write
   
    lines, cols = map(int, input().split())
    vectorsA = [(l, c) for l in range(lines) for c, p in enumerate(map(int, input().split())) if p]
    vectorsB = [(l, c) for l in range(lines) for c, p in enumerate(map(int, input().split())) if p]
    translations = [[0] * (cols * 2) for l in range(lines * 2)]
    for vA in vectorsA:
        for vB in vectorsB:
            translations[lines + vB[0] - vA[0]][cols + vB[1] - vA[1]] += 1    
    swarm = ()
    maximum = 0
    for line in range(lines *2):
        for col in range(cols *2):
            if translations[line][col] > maximum:
                maximum = translations[line][col]
                swarm = (line - lines, col - cols)
    print(str(maximum))
    print('\n')
    for vA in vectorsA:
        try:
           vectorsB.index((vA[0] + swarm[0], vA[1] + swarm[1]))
           print(str(vA[0] + swarm[0] + 1))
           print(' ')
           print(str(vA[1] + swarm[1] + 1))
           print('\n')
        except:
            pass
               
main()

ça marche mieux, 15 / 20

Mon essai avec ton code donne seulement 14 succès et bien qu'il passe un test de plus que mon code, il est 2 fois plus lent sur le test n°16, le plus exigeant évaluable. Ton algo reste l'algo que nous avons vu jusqu'à maintenant (sauf la fin qui est un peu plus rapide car tu ne parcours que les points d'une des grilles).

Ta ligne 24 est potentiellement coûteuse, il vaudrait mieux convertir vectorsB en un set Python.

Ton astuce de doubler la taille pour capturer des offsets négatifs est bien vue. 

Curieux tes print(str(...)), on fait pas ça en Python. 

Finalement, après de nombreux essais en C++ et trop lent, mon code passe les 20 tests en C :

#include <stdio.h>
#define NL 1000
#define NC 1000
#define NP 1000
int T1[NL][NC];
int P1[NP][2];
int P2[NP][2];
int NB_OCC[2 * NL][2 * NC];
int
main ()
{
  int n, p;
  scanf ("%d%d", &n, &p);
  int N1 = 0, N2 = 0;
  int maxi = 0;
  int xmax = 0, ymax = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < p; j++)
      {
        int q;
        scanf ("%d", &q);
        if (q)
          {
            T1[i][j] = 1;
            P1[N1][0] = i;
            P1[N1][1] = j;
            N1++;
          }
      }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < p; j++)
      {
        int q;
        scanf ("%d", &q);
        if (q)
          {
            P2[N2][0] = i;
            P2[N2][1] = j;
            N2++;
          }
      }
  for (int i = 0; i < N1; i++)
    for (int j = 0; j < N2; j++)
      {
        int x1 = P1[i][0], y1 = P1[i][1];
        int x2 = P2[j][0], y2 = P2[j][1];
        NB_OCC[n + x2 - x1][p + y2 - y1]++;
        if (NB_OCC[n + x2 - x1][p + y2 - y1] > maxi)
          {
            maxi = NB_OCC[n + x2 - x1][p + y2 - y1];
            xmax = x2 - x1;
            ymax = y2 - y1;
          }
      }
  printf ("%d\n", maxi);

  for (int i = 0; i < N2; i++)
    {
      int x2 = P2[i][0], y2 = P2[i][1];

      if (x2 - xmax >= 0 && y2 - ymax >= 0 && T1[x2 - xmax][y2 - ymax])
        printf ("%d %d\n", x2 + 1, y2 + 1);
    }
  return 0;
}

Ce code est à peine moins rapide que le code corrigé en C++ et d'ailleurs, ça semble être le même algo. Je pense que ce code correspond plus ou moins à ce que tu as écrit.

Les contraintes données dans l'énoncé semblent fausses car si je prend un nombre de lignes ou de colonnes valant au max 500, mon code plante sur trois test (perdu beaucoup de temps avec ça).

L'équivalent du code ci-dessus écrit en Python a toutes les raisons d' être plus lent qu'un code utilisant un simple dictionnaire, comme ce code :

from sys import stdin
from collections import Counter


def solve():
    input=stdin.readline
    n, p=map(int, input().split())

    im1=[input().split() for _ in range(n)]
    im2=[input().split() for _ in range(n)]

    P1=[(i,j) for i in range(n) for j in range(p) if im1[i][j]=='1']
    P2=[(i,j) for i in range(n) for j in range(p) if im2[i][j]=='1']
                

    T=[(x2-x1, y2-y1) for x1,y1 in P1 for x2,y2 in P2]

    C=Counter(T)
    u,m= C.most_common(1)[0]

    print(m)
    a,b=u
    S1=set(P1)

    for (i,j) in P2:
        if (i-a, j-b) in S1:
            print(i+1, j+1)

solve()

mais qui ne passe que 13 tests.

Mon code C++ avec le même algo et utilisant un set et un dictionnaire ne passait pas tous les tests :

#include <cstdio>
#include <map>
#include <set>
#include <vector>
using namespace std;
typedef pair<int, int> Point;
int
main ()
{
  int n, p;
  vector<Point> P1, P2;
  map<Point, int> C;
  set<Point> S1;
  int maxi = 0;
  Point maxi_pair;
  scanf ("%d%d", &n, &p);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < p; j++)
      {
        int q;
        scanf ("%d", &q);
        if (q)
          {
            Point pt = make_pair (i, j);
            P1.push_back (pt);
            S1.insert (pt);
          }
      }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < p; j++)
      {
        int q;
        scanf ("%d", &q);
        if (q)
          P2.push_back (make_pair (i, j));
      }
  for (auto p1 : P1)
    for (auto p2 : P2)
      {
        int x1{ p1.first }, x2{ p2.first }, y1{ p1.second }, y2{ p2.second };
        Point p = make_pair (x2 - x1, y2 - y1);
        if (C.find (p) != C.end ())
          {
            C[p]++;
            if (C[p] > maxi)
              {
                maxi = C[p];
                maxi_pair = p;
              }
          }
        else
          C[p] = 1;
      }
  if (maxi == 0)
    {
      maxi = 1;
      maxi_pair.first = P2[0].first - P1[0].first;
      maxi_pair.second = P2[0].second - P1[0].second;
    }
  printf ("%d\n", maxi);
  int xmax = maxi_pair.first, ymax = maxi_pair.second;
  for (auto p2 : P2)
    {
      int x2 = p2.first, y2 = p2.second;
      Point p1 = make_pair (x2 - xmax, y2 - ymax);
      if (S1.count (p1))
        printf ("%d %d\n", x2 + 1, y2 + 1);
    }
  return 0;
}

Au test 16, ce code est seulement 3 fois plus rapide que du Python, il faut dire que les map et set du C++ sont très lents.

@tomleuj OK, j'ai compris pour tu utilises str. J'ai récris ton code avec un set mais ça ne change rien. 

-
Edité par PascalOrtiz 21 décembre 2022 à 11:04:01

j'en suis là, j'ai m'impression que c'est + ou - la même chose que le code de PascalOrtiz mais je fais 11/10.

toujours 6 erreurs de résultat et 3 temps dépassés.

le test 16 passe en 0.25s.

import sys
from collections import Counter

nbln,nbcol,*l = sys.stdin.read().split()
nbln,nbcol  = int(nbln),int(nbcol)

image2 = {point2 for point2,c in enumerate(l[nbln*nbcol:]) if c=='1'}
image1 = [point1 for point1,c in enumerate(l[:nbln*nbcol]) if c=='1']

 
c = Counter(point2-point1 for point1 in image1 for point2 in image2).most_common(1)
if c:
   a,b = c[0]
   print(b)
   for point in {point1+a for point1 in image1}&image2: print(point//nbcol+1,point%nbcol+1)

-
Edité par josmiley 20 décembre 2022 à 19:52:51

josmiley a écrit:

j'en suis là, j'ai m'impression que c'est + ou - la même chose que le code de PascalOrtiz mais je fais 11/10.

toujours 6 erreurs de résultat et 3 temps dépassés.

le test 16 passe en 0.25s.

import sys
from collections import Counter

nbln,nbcol,*l = sys.stdin.read().split()
nbln,nbcol  = int(nbln),int(nbcol)

image2 = {point2 for point2,c in enumerate(l[nbln*nbcol:]) if c=='1'}
image1 = [point1 for point1,c in enumerate(l[:nbln*nbcol]) if c=='1']

 
c = Counter(point2-point1 for point1 in image1 for point2 in image2).most_common(1)
if c:
   a,b = c[0]
   print(b)
   for point in {point1+a for point1 in image1}&image2: print(point//nbcol+1,point%nbcol+1)

-
Edité par josmiley il y a environ 1 heure

Le système d'id de chaque point de la grille est astucieux car effectivement avec le quotient et le reste tu peux identifier un point de la grille de manière unique. Toutefois, rien ne dit que ça passe quand tu fais une différence de vecteurs (si les vecteurs sont les mêmes les différence d'id le serront aussi par contre, il faudrait s'assurer que des différences d'id égales donnent des vecteurs égaux)

J'essaye un contre-exemple. Imaginons que le nombre de colonnes d'une grille soit p=10 et prenons les points 

• A1=(1,2)  et B1=(1, 8) sur l'image 1 
• A2=(2,4) et B2=(3,0) sur l'image 2

L'id d'un point (x, y) est px+y. Donc, ici les id sont  :

• idA1=12, idB1=18
• odA2=24, idB2=30

• Pour (A1,A2), la différence d'id est 24-12=12
• Pour (B1,B2), la différence d'id est 30-18=12

Les différences sont égales donc elle sont comptées comme telles par Counter ligne 11.

Or, les vecteurs ne sont pas égaux :

• A1A2=(1,2)
• B1B2=(2, -8)

donc le comptage des ces vecteurs est incorrect.

Mais oui, que je suis bête, surtout que j'en avais tenu compte dans mes essais bit à bit... Trop bête.

Merci d'avoir pris le temps de lire mon code.

13/20 sans Counter.  Je construits directement un dictionnaire. Le test 16 passe en 0.28s.

import sys

nbln,nbcol,*l = sys.stdin.read().split()
nbln,nbcol  = int(nbln),int(nbcol)
shift = {} 
image2 = {(point2//nbcol)*nbcol+point2:point2 for point2,c in enumerate(l[nbln*nbcol:]) if c=='1'} 
image1 = [(point1//nbcol)*nbcol+point1 for point1,c in enumerate(l[:nbln*nbcol]) if c=='1']

for point1 in image1:
    for point2,point in image2.items() :
        shift.setdefault(point2-point1,[]).append(point) 

a = max(shift.values(), key=len) 
print(len(a)) 
for point in a:
    print(point//nbcol+1,point%nbcol+1)

16/20 avec Counter. les tests 4,18,19,et 20 ne passent pas.

import sys
from collections import Counter

nbln,nbcol,*l = sys.stdin.read().split()
nbln,nbcol  = int(nbln),int(nbcol)

image2 = {(point2//nbcol)*nbcol+point2:point2 for point2,c in enumerate(l[nbln*nbcol:]) if c=='1'}
image1 = [(point1//nbcol)*nbcol+point1 for point1,c in enumerate(l[:nbln*nbcol]) if c=='1']
 
 
c = Counter(point2-point1 for point1 in image1 for point2 in image2).most_common(1)
if c:
   a,b = c[0]
   print(b)
   for point in {point1+a for point1 in image1}&set(image2): print(image2[point]//nbcol+1,image2[point]%nbcol+1)

-
Edité par josmiley 21 décembre 2022 à 9:44:31

josmiley a écrit:

16/20 avec Counter. les tests 4,18,19,et 20 ne passent pas.

import sys
from collections import Counter

nbln,nbcol,*l = sys.stdin.read().split()
nbln,nbcol  = int(nbln),int(nbcol)

image2 = {(point2//nbcol)*nbcol+point2:point2 for point2,c in enumerate(l[nbln*nbcol:]) if c=='1'}
image1 = [(point1//nbcol)*nbcol+point1 for point1,c in enumerate(l[:nbln*nbcol]) if c=='1']
 
 
c = Counter(point2-point1 for point1 in image1 for point2 in image2).most_common(1)
if c:
   a,b = c[0]
   print(b)
   for point in {point1+a for point1 in image1}&image2: print(image2[point]//nbcol+1,image2[point]%nbcol+1)

-
Edité par josmiley il y a 25 minutes

Erreur d'exécution (set & dict).

Il faut juste convertir le dict en set et ça marche très vite :

import sys
from collections import Counter

nbln, nbcol, *l = sys.stdin.read().split()
nbln, nbcol = int(nbln), int(nbcol)

image2 = {
    (point2 // nbcol) * nbcol + point2: point2
    for point2, c in enumerate(l[nbln * nbcol :])
    if c == "1"
}
image1 = [
    (point1 // nbcol) * nbcol + point1
    for point1, c in enumerate(l[: nbln * nbcol])
    if c == "1"
]


c = Counter(point2 - point1 for point1 in image1 for point2 in image2).most_common(1)
if c:
    a, b = c[0]
    print(b)
    s={point1 + a for point1 in image1}
    for point in s & set(image2):
        print(image2[point] // nbcol + 1, image2[point] % nbcol + 1)

EDIT : si tu places tout ton code dans une fonction, tu peux même passer un test de plus (17) :

def solve():
    import sys
    from collections import Counter    
    nbln, nbcol, *l = sys.stdin.read().split()
    nbln, nbcol = int(nbln), int(nbcol)

    image2 = {
        (point2 // nbcol) * nbcol + point2: point2
        for point2, c in enumerate(l[nbln * nbcol :])
        if c == "1"
    }
    image1 = [
        (point1 // nbcol) * nbcol + point1
        for point1, c in enumerate(l[: nbln * nbcol])
        if c == "1"
    ]


    c = Counter(point2 - point1 for point1 in image1 for point2 in image2).most_common(1)
    if c:
        a, b = c[0]
        print(b)
        s={point1 + a for point1 in image1}
        for point in s & set(image2):
            print(image2[point] // nbcol + 1, image2[point] % nbcol + 1)
solve()

Bravo !

-
Edité par PascalOrtiz 21 décembre 2022 à 9:48:40

effectivement, erreur de copie/colle de version, on peut même se passer du test à la fin.

Ton code passe 17 tests et le même algo écrit en C++ (mapping et set), cf. le code ICI, passe aussi les mêmes 17, donc je crois qu'il va être difficile d'en passer un de plus en Python et le même algo.

Bonjour,

voici le code C++ de Frigory , merci à lui. (C'est okay de le poster ? éthiquement parlant ?)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
   
    int lines, cols;
    cin >> lines >> cols;
    vector<pair<int, int>> vectorsA, vectorsB;
    for (auto * vectors: { &vectorsA, &vectorsB }) {
        for (int l = 0; l < lines; ++l) {
            for (int c = 0; c < cols; ++c) {
                int p;
                cin >> p;
                if (p) {
                    vectors->push_back({ l, c });
                }
            }
        }
    }
    vector<pair<int, int>> translations(vectorsA.size() * vectorsB.size());
    int num = 0;
    for (auto const & vA: vectorsA) {
        for (auto const & vB: vectorsB) {
            translations[num] = { vB.first - vA.first, vB.second - vA.second };
            ++num;
        }
    }
    auto sortedT = translations;
    sort(sortedT.begin(), sortedT.end());
    sortedT.push_back({ -lines * 3, -cols * 3 });
    int total = 0, maximum = 0;
    auto swarm = sortedT[0], current = sortedT[0];
    for (auto const & t: sortedT) {
        if (t == current) {
            ++total;
        } else {
            if (total > maximum) {
                maximum = total;
                swarm = current;
            }
            total = 1;
            current = t;
        }
    }
    cout << maximum << '\n';
    int sizeB = vectorsB.size();
    num = 0;
    for (auto const & translation: translations) {
        if (translation == swarm) {
            auto const & pos = vectorsB[num % sizeB];
            cout << pos.first + 1 << ' ' << pos.second + 1 << '\n';
        }
        ++num;
    }
}

Merci. C'est une variante moins simple que ce que tu avais proposé ICI.

Sur mon fichier de test assez gros, ce code est toutefois 3 x plus lent que le corrigé (et aussi que le code C ci-dessus) avec 3 parcours d'une longue liste Normalement, l'algorithme devrait être codé plus confortablement avec un mapping et un ensemble, comme josmiley l'a fait ci-dessus en Python, il faudrait le récrire en C++ pour voir si cette fois ça passe tous les tests.

PascalOrtiz a écrit:

Normalement, l'algorithme devrait être codé plus confortablement avec un mapping et un ensemble, comme josmiley l'a fait ci-dessus en Python, il faudrait le récrire en C++ pour voir si cette fois ça passe tous les tests.

J'ai récrit le code Python de josmiley en C++ avec unordered_map (un dictionnaire) et cette fois ça passe tous les tests, même si c'est assez lent. C'est le fait d'avoir des clés entières qui le permet.

#include <cstdio>
#include <unordered_map>
#include <vector>

using namespace std;

int
main ()
{
  int n, p;

  vector<int> image1;
  unordered_map<int, int> image2;
  unordered_map<int, int> C; // Sera l'analogue de Counter en Python

  scanf ("%d%d", &n, &p);

  for (int i = 0; i < n * p; i++)
    {
      int q;
      scanf ("%d", &q);
      if (q)
        image1.push_back ((i / p) * p + i);
    }

// Besoin du mapping à la fin du code    
  for (int i = 0; i < n * p; i++)
    {
      int q;
      scanf ("%d", &q);
      if (q)
        image2[(i / p) * p + i] = i;
    }

  // Construction de Counter
  // occurrence (maxi_delta) en nombre maximal (maxi)    
    
  int maxi = 0, maxi_delta = 0;


  for (auto p1 : image1)
    for (auto p2 : image2)
      {
        int delta = p2.first - p1;
        if (C.find (delta) != C.end ())
          {

            if (++C[delta] > maxi)
              {
                maxi = C[delta];
                maxi_delta = delta;
              }
          }
        else
          C[delta] = 1;
      }
// Cas où pas de vecteurs égaux
  if (maxi == 0)
    {
      maxi = 1;
      // vecteur arbitraire
      auto it = image2.begin ();
      int p1 = image1[0];
      maxi_delta = (*it).first - p1;
    }

  printf ("%d\n", maxi);
  
// On reconstruit les extrémités
  // des vecteurs
  for (auto p1 : image1)
    {
      int pt = p1 + maxi_delta;// translaté
      
      if (image2.find (pt) != image2.end ())
        printf ("%d %d\n", image2[pt] / p + 1, image2[pt] % p + 1);
    }

  return 0;
}

-
Edité par PascalOrtiz 22 décembre 2022 à 17:44:41