198 Custi

[•c_adelina]

Am mare nevoie de un hint la prbl asta,am rezolvat-o in (N*N*logN), dar am vazut ca exista cateva surse cu timpi sub 0.05 . Multumesc anticipat!

[•blasterz]

Am mare nevoie de un hint la prbl asta,am rezolvat-o in (N*N*logN), dar am vazut ca exista cateva surse cu timpi sub 0.05 . Multumesc anticipat!

Pai rezolvi cu dinamica in O(N^2):

dp[ i ][ j ] = lungimea celei mai mari submatrice patratice plina de 1 ce are coltul din dreapta jos in pozitia (i, j).

dp[ i ][ j ] se calculeaza in O(1)

Te las pe tine sa-ti dai seama cum calculezi numarul de submatrice plina de 1.

[•c_adelina]

gata  ms moolt pt ajutor    , mare diferenta intre O(1) si O(logN) vreo 200-300 ms )) , totusi nu inteleg cum au scos unii sub 0.05. 

[•klamathix]

Au parsat citirea. Adica au citit inputul ca string si l-au convertit apoi manual in numere. Merge mult mai repede, mai ales pentru 10 ^ 6 numere.

[•NicuCJ]

Salut, am luat TLE pe 3 teste [desi nu stiu de la ce].
Am facut o dinamica in O(N^2) si actualizez datele la fiecare pas al dinamicii, dar nu stiu care-i faza. Parsarea citirii poate face diferenta intre 70 si 100?

[•alex_unix]

O(n^2) cred ca intra in timp cu functiile din <cstdio> doar daca parsezi citirea . Cum nu cred ca asta era scopul problemei, poate mariti putin limita de timp daca sunteti de aceeasi parere cu mine 

[•Detrol2k]

De ce e asa comunista problema asta? Am trimis doar citirea cu scanf() + O SINGURA atribuire si imi da TLE la cateva teste. Am incercat si cu citire parsata si la fel face. Nici o diferenta. 

[•wefgef]

Functia strlen() are complexitatea O(N), deci practic tu ai acolo O(N^3).

[•Detrol2k]

Functia strlen() are complexitatea O(N), deci practic tu ai acolo O(N^3).

Am reusit! Nu mi-as fi dat seama de chestia asta in veci!   Iti multumesc mult!
Se pare ca trebuie sa rectific ce am zis mai sus. Problema nu e comunista, e cat se poate de capitalista.  

[•dariusdarius]

Timpul problemei asteia este gresit!!! Am facut problema O(n*n), doar partea de CITIRE si inca 2 for-uri de la 1 la n si imi da TLE

[•dariusdarius]

Ignorati mesajul interior, am schimbat din scanf/printf in cin/cout si am luat 100

[•Andrei1998]

Eu am inteles solutia O(n^2) dar sunt chiar curios de cea in O(nlogn). Cutare binara? Un hint, ceva, va rog.

,Andrei

[•repp4radu]

Nu ai cum sa scoti o solutie in O(N log N) din moment ce ai complexitate O(N^2) doar pentru citirea matricii.

[•Andrei1998]

Vroiam sa zic O(n^2*logn). Greseala mea.

,Andrei

[•taigi100]

Ok... Ma chinui de cateva ore si nu reusesc sa-mi dau seama ce e in neregula cu sursa mea  , pe primele 4 teste obtine punctaj maxim dar pe urmatoarele imi da o eroare de care nu am mai auzit.
Aici is rezultatele testelor:

Cod:

1	12ms	1972kb	OK	10
2	4ms	348kb	OK	10
3	4ms	468kb	OK	10
4	4ms	644kb	OK	10
5	4ms	248kb	Killed by signal 6(SIGABRT).	0
6	4ms	248kb	Killed by signal 6(SIGABRT).	0
7	4ms	248kb	Killed by signal 6(SIGABRT).	0
8	4ms	252kb	Killed by signal 6(SIGABRT).	0
9	4ms	248kb	Killed by signal 6(SIGABRT).	0
10	4ms	248kb	Killed by signal 6(SIGABRT).	0
Punctaj total	40

Din cate stiu nu pot sa pun sursa pe forum deci cine e dispus sa ma ajute va rog sa imi da-ti un pm.Multumesc.

[•Methus]

Stiu ca nu este cel mai potrivit loc pentru aceasta, insa daca tot sunt la aceasta problema doresc sa va indreb Q_Q Cum incep un program? In DEV C++ totul este inregula insa in Code::Blocks nu imi gaseste directoriul iostream.h si nici fstream.h Nu merge fara .h de asemenea. Observ ca aceasta chestie imi afecteaza evaluarea. 

[•SpiderMan]

Cele cu .h sunt deprecated, doar cele din C-ul vechi se mai pastreaza cu .h (gen stdio.h, stdlib.h, string.h, care in C++ sunt cstdio, cstdlib, cstring). Pentru fstreamuri, varianta noua este aceasta L

Cod:

# include <fstream> // sau # include <iostream>
using namespace std; // aici sunt citirile si tot ce trebuie, citeste pe cplusplus.com

[•Methus]

o, nice
merci \o/
sper ca acum o sa-mi iasa ceva c:

[•Eby7]

Iau 30 pe asta(TLE)... daca imi poate explica cineva ce trebuie sa mai modific pentru a da in timp.

Cod:

#include<fstream>
using namespace std;
ifstream f("custi.in");
ofstream g("custi.out");
int n,x,sum[1001][1001];
int i,j,k;
int nr,nr1;
int s;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    {
        f>>x;
        if(x==1)
         nr1++;
        sum[i][j]=x+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
    }
    g<<nr1<<"\n";
    for(k=2;k<=n;k++)
    {
        nr=0;
        for(i=k;i<=n;i++)
         for(j=k;j<=n;j++)
         {
             s=sum[i][j] - sum[i-k][j] - sum[i][j-k] + sum[i-k][j-k];
             if(s==(k*k))
              nr++;
         }
         g<<nr<<"\n";
    }
    return 0;
}

[•vendetta]

E prea mare complexitatea. Citeste ce s-a mai postat pe forum si incearca sa scoti O(n^2).

[•reking]

Vreun sfat?
http://www.infoarena.ro/job_detail/1001305
Dupa parerea mea am O(n*n) dar totusi iau TLE pe 3 teste 

[•vendetta]

Eu nu sunt de aceeasi parere... . Ai acolo un for, care chiar daca e micut, conteaza ).

Cod:

  for (k=1;k<=b[i][j];k++) h[k]++; 

Incearca sa scapi de el.

[•reking]

Corect, greseala mea. 
Si...vreo idee sa reduc acea parcurgere? (nu-mi vine nimic in minte) 

[•vendetta]

O idee ar fi smenul lui mars. Dar exista si alta solutia mai simpla. Gandeste-te in felul urmator : toate actualizarile sunt de forma [1..X], unde X e b[ i ][ j ] (la tine). Incearca sa scoti o solutie astfel incat actualizarile sa le faci in O(1).

[•reking]

Am reusit sa duc sursa la 90 de puncte 
http://www.infoarena.ro/job_detail/1003513
La "metoda" asta te refereai? (chiar daca nu prea am facut-o in O(1)...cred ca undeva pe la O(2) sau O(3) )