Consideram matricea:

1
1 2
1 2 3
1 2 3 4

Sa vedem cum se traduce gasirea valorii k din sir cu gasirea unui element (kx, ky) in matrice.

In primul rand, matricea de mai sus are 1 + 2 + 3 + 4 = 4*5/2 = 10 elemente.

Primele i linii au, in total i*(i + 1)/2 elemente.
Linia i are i elemente 1 2 ... i.

Al k-lea element este pe cea mai mica linie kx astfel incat kx*(kx + 1)/2 >= k

=> kx^2 + kx - 2k >= 0

kx^2 + kx - 2k = 0
delta = 1 - 4*(1 * (-2k)) = 1+8k > 0
kx = [-1 +/- sqrt(1 + 8k)] / 2

Varianta cu - evident nu convine, deoarece kx nu poate fi negativ

=> kx = [-1 + sqrt(1 + 8k)] / 2
=> kx = Ecuatie(1, 1, -2k)

De exemplu, pentru al cincilea element:

kx^2 + kx - 10 = 0
delta = 1 + 40 = 41

kx = [-1 + sqrt(41)] / 2 = 3 (rotunjit in sus)

Pana la linia 3 sunt 3 elemente, deci ky = 5 - 3 = 2

Al doilea element de pe linia 3 este 2.

CMMMC(a, b) = (a*b)/CMMDC(a, b)

CMMMC(a, b, c) = CMMMC( CMMMC(a, b), c )
CMMMC(a, b, c, d) = CMMMC{ CMMMC[ CMMMC(a, b), c ], d }

... etc.

Ar trebui sa fie suficient de rapid asa.

Am facut problema cu arbori de intervale. Daca trimit numai citirea si sortarea, imi ia cam jumatate de timp. Folosesc sort din STL. Cum as putea sorta mai rapid niste stringuri?

Nu stiu exact cum faci, dar windows trece cu vederea unele erori aparent neimportante din partea programatorului. De exemplu, ti se cere sa afisezi produsele sortate. Banuiesc ca parcurgi o data sirul si le copiezi pe toate intr-o matrice. Cand termini de copiat cuvantul, ai grija sa pui '\0' la sfarsit (asta nu stiu daca chiar conteaza, dar e bine de facut oricum). Vezi sa declari vectorii folositi putin mai mari decat ai nevoie in cazul sirurilor de caractere, ca sa poti retine si caracterele '\n' si '\0'; asta este o posibila cauza de eroare care apare pe linux dar pe windows nu intotdeauna. Ai grija sa nu fie ceva la sortare tot de genul acesta.

Eu am luat 100 avand grija sa citesc cu fgets, sa nu ma intereseze de '\n', sa declar vectorii de dimensiuni mai mari si sa pun '\0'.

Apropo, nu se acorda punctaje partiale asa cum scrie in enunt.

Daca citesti cu gets / fgets vezi ce se intampla cand ai si cand nu ai '\n' la sfarsitul liniei.

Ori asta ori afisam cu -. Oricum, practic inseamna raspuns gresit, daca mai are cineva probleme.

Ce inseamna "Format incorect"? Trebuie afisat intr-un fel anume (cu privire la spatii sau linii noi, in afara de ce precizeaza enuntul) sau inseamna ca raspunsul este gresit?

In trie bagi toate cele N cuvinte care ti se dau, iar apoi pentru fiecare sufix al lui L, vezi daca vreun prefix (de lungime maxim K bineinteles) al acelui sufix se gaseste in trie. Trebuie sa fii atent la cazul in care ai mai multi virusi identici, sa stii sa incrementezi pentru amandoi raspunsul. Poti sa tii o lista pentru asta.

Memorie nu-ti trebuie O(L*K) pentru trie. Iti trebuie O(K²).

Merge si trie simplu in O(L*k)... si inca foarte rapid: http://infoarena.ro/job_detail/192070

Cred ca testele sunt cam slabe...

Tu ai ales minimul dintre valori ale matricii costurilor. Eu am zis ca se alege minimul dintre apeluri recursive.

Uite un program care l-am scris rapid, nu stiu daca e 100% corect, dar pe exemplul tau da corect: 7.

Cod:

int n, m;
int a[maxn][maxn];
int memo[maxn][maxn];
int v[maxn][maxn];

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int back[maxn][maxn];

int go(int x, int y)
{
    if ( memo[x][y] != -1 )
        return memo[x][y];

    if ( v[x][y] )
        return 1 << 29;

    v[x][y] = 1;

    for ( int i = 0; i < 4; ++i )
    {
        int X = x + dx[i];
        int Y = y + dy[i];

        if ( X > 0 && Y > 0 && X <= n && Y <= m )
            if ( go(X, Y) + a[x][y] < memo[x][y] || memo[x][y] == -1 )
                memo[x][y] = go(X, Y) + a[x][y], back[x][y] = i;
    }

    v[x][y] = 0;

    return memo[x][y];
}

int main ()
{
    fscanf(in, "%d %d", &n, &m);

    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= m; ++j )
            fscanf(in, "%d", &a[i][j]), memo[i][j] = -1;

    memo[1][1] = a[1][1];

    printf("%d\n", go(3, 3));

    for ( int i = 1; i <= n; ++i )
    {
        for ( int j = 1; j <= m; ++j )
            printf("%d ", back[i][j]);
        printf("\n");
    }

    return 0;
}

Problema nu merge si cu memoizare?

Fie f(i, j) costul minim pentru a ajunge de la punctul de plecare (x, y) pana in (i, j). f(i, j) = cost[ i ][ j ] + min(f(i+1, j), f(i, j+1), f(i-1, j), f(i, j-1)).

f(x, y) se initializeaza cu cost[ x ][ y ] si eventual mai trebuie avut grija sa nu se apeleze recursiv pentru zone inaccesibile (i, j < 0 etc)

Pare corect. Complexitatea nu ar fi patratica daca se aplica memoizare?

Eu sunt foarte curios cum se face submatrice maxima plina de zerouri in O(n²)... as fi recunoscator daca ar explica cineva ideea .

Mie mi-a intrat cu cautare binara clasica.

Care e "hashul cu functia lui Mircea"?

A intrat asa . Mersi!

Cum adica sa parsez citirea, aici? Citesc cu fgets sirul initial si apoi fiecare cuvant in parte tot cu fgets. Daca trimit doar citirea cel mai mare timp e 0.6 pe testul 8. Se poate mai rapid?

Nu reusesc nicicum sa iau testele 8 si 9. Restul intra in sub o secunda, la astea primesc TLE. Folosesc 2 hashuri. Imi dati va rog o sugestie?

Tocmai, ca inca se precizeaza ca exista intotdeauna solutie, ceea ce m-a dus cu gandul ca exemplul ar fi gresit. Asta era, imi intra in ciclu infinit cand nu aveam solutie.

Si cred ca trebuie n < 2 miliarde, nu 20 de miliarde, pt ca eu am luat 100 folosind int.

E corect exemplul 2? Se cere nivelul minim 100 iar el termina jocul cu nivelul 19?

Roy-Floyd nu e acelasi lucru cu Floyd-Warshall? Wikipedia asa zice

As contribui si eu... m-as putea ocupa de dijkstra, bellman-ford si eventual niste algoritmi care vad ca nu sunt trecuti acolo: subsecventa de suma maxima, distanta levenshtein, exponentiere logaritmica...

Pai.. ai doua solutii ca sa afli bitii de 1 dintr`un numar.
1. Daca in program, trebuie sa afli bitii de 1, din foarte multe numere, poti face o precalculare in O(Nmax), apoi raspunzi in O(1) pt fiecare numar.
2. Daca in program, trebuie sa aflii bitii de 1, din foarte putine numere, poti face chestia asta in O(nr_de_biti_de_1). [Practic imparti la 2 numarul pe care il ai, si numeri de cate ori nr respectiv % 2 ==1).
 In ambele cazuri, e bine sa folosesti operatiile pe biti, ca sa micsorezi timpul de executie.
Apropo, problema poate fi rezolvata si O(N^2*M) cu parsarea citirii. 

La 2 e O(log₂Numar) sau O(numar_total_de_biti) asa cum zici tu, nu O(nr_biti_de_1), pentru ca tu verifici si bitii care sunt pe 0 impartind la 2 si facand modulo 2 la fiecare pas.

Ai grija sa opresti cautarea (break, return) cand ai ajuns la solutie.

Eu am o sursa veche care intra lejer in 0.2 secunde. Probabil ca se poate si in 0.1.. deci 0.4 e oricum mult

Cred ca merge si daca imparti fiecare factor si abia apoi faci modulo, adica:

3*4 / 2 = E

3 nu se divide la 2, il ignori
4 se divide, il imparti => E = 3*2

Acuma faci modulo 3 mod 7 = 3, 2 mod 7 = 2 3*2 = 6, 6 mod 7 = 6.

Ce-ai intrebat tu poti sa faci inteligent tot ca la ciurul lui Erastotene si sa obtii O(MAX*logMAX).

Intr-adevar, a intrat in sub o secunda asa. Mersi!