248 Map

[•wefgef]

Merge de 100 de puncte sa cauti cu brute raspunusul

[•DITzoneC]

S-au modificat niste teste la map si s-a micsorat limita de timp la 0.4. Acum cu brute-force se ia aproximativ 50p.

Multumim PaulDB pentru teste.

[•wefgef]

S-ar putea ca unele surse cu KMP sa nu mai mearga.

Declarati matricea de dimensiuni 2048*2048 si inversati liniile si coloanele. Ar trebui sa intre in timp asa.

[•bogdan2412]

Sau poti sa nu folosesti matrice deloc

[•Marius]

Mai bine trimit un brute, decat un KMP. Nu am nici o matrice in program si cu toate astea iau doar 45, restul TLE. Nu inteleg de ce nu merge.

Matricea e intr-un vector, iar vectorul pentru KMP e obtinut asa:

Cod:

for (i = k = 0; i < M; ++ i)
     for (j = 0; j < N; ++ j)
          A[j * M + i] = X[k ++];

Ce alte trucuri mai stii Wef ? 

[•wefgef]

Marmot solution: Faci KMP pentru fiecare linie si in final alegi o pozitie care se potriveste pentru toate. Asa ai memorie O(N).

[•vlad_D]

am sanse cu rabin karp la 100?

iau tle pe ultimele 6 teste..

[Later Edit 1]: defapt ar tb.. ca a fost propusa la arhiva educationala la hashuri///

[Later Edit 2]: gata a intrat... am dato de pe long long pe int..