Dimensiunea sirului si numarul de operatii sunt pe aceeasi linie. Imi cer scuze. Enuntul a fost modificat. Multumesc pentru sesizare.

 long long

Da, intra.

Partial match se mai poate face si cu suffix array. Sa zicem ca esti la pozitia i in A si la pozitia j in B vrei sa afli cate caractere sunt la fel. Poti afla folosindu-te de suffix array.

Multa bafta!!!

Acel arbore binar e defapt un trie; dar avand in vedere ca sigma = 2 => o sa fie binar. Intr-un trie memoria folosita e lungTot*sigma, unde lungTot = suma lungimilor cuvintelor bagate in trie si sigma = 2(numarul caracterelor distincte folosite) => memoria folosita N * K * 2. => O(N*K) memorie. Trie-ul se contruieste similar cu cel din arhiva educationala.

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).

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.

Uite un exemplu pe care pica :

Cod:

5 1 1
2
3
3
2
2
Raspunsul corect e 7.

Cum pot scapa de MLE ?

Prima greseala : pierzi cazul cand K = j + 2; A 2-a : minimul  si maximul sunt doar pe intervalul j+1..k-1 (trebuie pe j+1..k);

Cod:

int Dreapta=0;
        int K=-1;
        minim=min(a[j+1],a[j+2]);
        maxim=max(a[j+1],a[j+2]);
        for(int k=j+2;k<=n-2;k++)
        {
            if(a[k]<minim)minim=a[k];
            if(a[k]>maxim)maxim=a[k];

            int aux=maxim-minim+MaxD[k+1]-minD[k+1];
            if(aux>Dreapta){Dreapta=aux;K=k;}
        }

Pierzi cazul cand n > 1( dupa ce l-ai descompuns in factori primi ). Trateaza acest caz si o sa iei 100.

E vorba despre operatii pe biti. Iti recomand sa cauti pe infoarena/google ce sunt. a << b <=> a * 2^b; iar secventa "i & (1<<(j-1))" verifica daca al (j-1) bit din configuratia binara a lui i are valoarea 1.

Nu chiar. E exact 64 de mega. 1 mega = 1024 kb. Si pe viitor poti folosi sizeof( ).

Nu e corect ce zici; e gresit pentru ca, pur si simplu e gresit...! Si la ce te ajuta ca stii ca ai cele mai multe drumuri cu distanta 1 ? Uite un exemplu pe care pica :

Cod:

.in : 
8
2 4 
2 5
2 1
1 3
3 6
6 7
7 8

.out : dat de tine nodul 2 cu ceva distanta
si corect nodul 1 si distanta 15

Ideea se bazeaza pe o dinamica in n^3. In primul rand pentru orice sir vei folosi n operatii de tipul top(); numarul de operatii de tipul push() va fi tot timpul egal cu numarul de operatii de tipul pop(). Acum problema devine in afla numarul minim de operatii de tipul push() a. i. sa obtii sirul [i..j]; Raspunsul final fiind Nr minim de operatii de a obtine sirul 1...n * 2 (nr de pop-uri) + n (nr de top() -uri); dinamica ar fi dp[ i ] [ j ] = nr minim de operatii de tipul push pentru a obtine sirul i...j;

Cod:

dp[i][j] = dp[i][j-1] + 1;// pur si simplu mai pun caracaterul Text[j];
sau dp[i][j] = dp[i][k] + dp[k+1][j-1], cu k = i,j-1 si Text[k] == Text[j];// asta inseamna ca fac sirul i...k cu un numar minim de operatii dupa care il fac pe k+1...j-1 si cand il pun pe j nu il pun in mod practic ( adica numai apelez push() ) ci scot tot ce e pe 
intervalul [k+1..j-1] si o sa ii dau "top()" de Text[j];

Pica pentru ca afisezi capatul stang gresit! Gandeste-te la urmatorul caz : gasesti cea mai buna secventa pe intervalul [5, 10]; iar apoi pe la pasul 15 gasesti sum < 0 si faci sum = a[ i ] iar st = i; in continuare cea mai buna secventa e aia de pe [5, 10] la pasul 16 te opresti si tu afisezi suma de pe [5,10] 15, 10; ceea ce e gresit .

Intr-adevar, rolul cifrei diferite e doar de a minimiza costul; doar ca tu obti acest numar, cred, dintr-un numar pe care nu il puteai forma. Tind sa cred ca formula, dupa care formezi restul, e gresita. Descrie modul cum formezi noul rest...

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

Nu am reusit sa inteleg exact dinamica ta... Dar tin minte ca si eu aveam probleme asemanatoare si din cat tin minte problema era la formarea noului rest. gen ma duc din starea (i, rest) in (newI, newRest) doar ca modul in care formam newRest nu era corect.

Prima data sa intelegi de ce pica solutia cu cmlsc. Tu cand fixezi 2 siruri( fie primul Sir[ k ] si al 2 -lea Sir[ l ]) faci cmlsc intre astea doua si rezultatul e 3 sa zicem; apoi faci cmlsc intre Sir[ k ] si Sir[ l + 1 ] rezultatul e 2 sa zicem; acum tu iei minimul si zici ca raspunsul e 2. Doar ca nu e corect sa faci chestia asta; pentru ca poate sa apara cazul in care cmlsc gasit la prima verificare sa fie total diferit fata de cel gasit la a 2-a verificare.
Uite un exemplu :

Cod:

5 4
1 3 4 5 2 
3 4 1 2 5 
3 2 5 1 4 
2 5 1 4 3 

Sursa ta se comporta total aiurea.

Cod:

cmlsc intre sirul 1 si sirul 2 e: 3
iar sirul e :5 4 3 

cmlsc intre sirul 1 si sirul 3 e: 2
iar sirul e :4 1 

cmlsc intre sirul 1 si sirul 4 e: 2
iar sirul e :3 1 


cmlsc intre sirul 2 si sirul 3 e: 3
iar sirul e :5 2 3 

cmlsc intre sirul 2 si sirul 4 e: 2
iar sirul e :5 2 


cmlsc intre sirul 3 si sirul 4 e: 4
iar sirul e :4 1 5 2 

Sirurile sunt in ordine inversa

Asa dupa tine, cat crezi ca e ?

Ai putea face in felul urmator : pentru fiecare numar afisat care are mai putine cifre decat n-ul initial bagi spatii inainte;
uite si cod :

Cod:

#include<iostream>
using namespace std;

inline int afla(int x){
    int cnt = 0;
    while(x!=0){
        cnt++; x /= 10;
    }
    return cnt;
}

int main()
{
    int n, d=2, m;
    cout<<"\n dati numarul natural nenul n = ";
    cin>>n;
    cout << "\n";
    int nrCifre = afla(n);
    while(n>1)
    {
        while(n%d==0)
        {
            m=n;
            n=n/d;
            int ceva = afla(m);
            for(int dif=nrCifre-ceva; dif>0; dif--) cout << " ";
            cout << m<<" | "<<d<<"\n";
        }
        d++;
    }

    int ceva = afla(n);
    for(int dif=nrCifre-ceva; dif>0; dif--) cout << " ";
    cout << n<<" | "<<"\n";
    return 0;
}

http://www.infoarena.ro/forum/index.php?topic=8883.0

Pe a doua linie din input se vor gasi P numere V1,V2...VN reprezentand vitezele de deplasare ale celor N personaje. in loc de P nu ar trebui N ?