Multumesc!

Circuitele ce se unesc trebuie sa aibe aceeasi intensitate?

Ce se intelege prin "cel mai mic sef comun al celor doi componenti din echipa"? - valoarea nodului ce reprezinta LCA-ul nodurilor sau seful comun cu valoarea cea mai mica?
Multumesc!

Pentru cei care sunt surprinsi ca pica testul 9: matricea pe care o afisati trebuie pusa pe long long! 

Iertati-ma daca nu stiu sa editez un comentariu! Raspunsul la testul trecut este defapt: 3999999989. 

Un test pe care se ia usor TLE:

1000000000
20
999999999
999999997
999999993
999999997
999999999
999999993
999999999
999999993
999999997
999999999
999999999
999999997
1000000000
999999999
999999997
999999997
999999999
999999993
999999997
999999997

Raspuns: 9634934603

[functia prefix]

Va rog, imi poate spune si mie cineva(care a rezolvat problema pe baza KMP)daca ideea mea este cea buna(am primit WA)?

Am spus ca sirul "a" este sirul cel mai mic din pereche si ca "b" este sirul cel mai mare din pereche.

Intai m-am uitat sa vad daca "a" este prefix al lui "b". Daca este, atunci solutia va fi lungimea lui "b".
Daca nu, calculam cel mai lung prefix al lui "a" care este sufix al lui "b" si cel mai lung prefix al lui "b" care este sufix al lui "a". 
Dintre aceste doua rezultate aleg maximul "max", iar solutia va fi : lungimea lui "a" + lungimea lui "b" - max.

Pentru a calcula cele doua rezultate am folosit de doua ori functia prefix de la KMP, cu doua mici modificari(am pus "p" in loc de "str"):

Cod:

int preprocessing(char *str, int n, char *p) {
  int i, k = 0;
  for (i = 1; i < n; i++) {
    while ((k > 0) && (str[i] != p[k])) {
      k = pi[k - 1];
    }
    if (str[i] == p[k]) {
      k++;
    }
    pi[i] = k;
  }
  return k;
}

ID : http://www.infoarena.ro/job_detail/1479236

Am vazut ca la comentarii toti vorbesc de KMP, dar eu nu imi dau seama unde sa-l folosesc! 
Multumesc mult! 

  Pentru cei interesati de metoda cu hash, dupa ce mi-am trimis sursa ca un copil constiincios (KMP + dinamica) 
m-am uitat peste sursele celorlalti si am gasit sursa aceasta : http://www.infoarena.ro/job_detail/1065650, si altele ca si ea din aceeasi
zi. Dar aceasta sursa m-a impresionat!!! (112 ms, 424 kb). O solutie cu KMP scoate fix dublu ca timp, iar ca memorie de 8 ori mai mult!
  Habar nu am ce sunt hash-urile, dar propozitia aceasta: "Sursa cu hashuri originala avea in jur de 4 secunde pe testul maxim"  m-a facut sa caut un curajos care a reusit sa faca cu aceasta metoda.
  Spor!

Da, merge! 

Am pornit Bellman-Ford-ul din nodul 1(nu din nodul N - cum am zis in comentariul trecut).
Deci, cine vrea sa implementeze aceasta idee, chiar ii recomand (e foarte asemanatoare cu cea de complexitate O(K * M * N)).

Cine vrea sa vada timpii -
    * ID: http://www.infoarena.ro/job_detail/1459472 (complexitate O(K * M * N))
    * ID: http://www.infoarena.ro/job_detail/1460000 (complexitate O(M * N))

Bafta!

Stiu ca suna cam dubios, dar merge cu un singur Bellman-Ford?(doar intreb ca poate, poate, cineva s-a mai gandit la ideea asta).

Eu m-am gandit ca se poate pleca cu parcurgerea din nodul N, calculand pentru fiecare nod necesarul minim de watti pe care trebuie sa-i folosim pentru a obtine distanta minima. Am implementat ceva care ia doar 10 puncte, dar sunt sigur ca aceasta idee trebuie sa mearga. 

Daca vede cineva comentariul acesta, il rog sa se gandeasca la ideea aceasta ca poate va reusi sa o implementeze perfect (eu ma voi stradui in continuare  ).

Am si o intrebare..
Am codul urmator...

Cod:

//Iisuse miluieste -ma
#include<fstream>
#define GOD 500000000
using namespace std;

void GOD_sort( long int a[ ] , long  int n )
{
long int p , aux , gasit;
do {
    gasit = 0 ;
    for( p = 0 ; p < n; p ++ )
       {
      if( a[ p ] > a[ p + 1 ] )
        {
        aux = a[ p ];
        a[ p ] = a[ p + 1];
	a[ p + 1] = aux;
	gasit = 1;
 	}
      }
  }while( gasit );
}
int main()
{
long int targ[ GOD ] , x , d , k , i , j , N ;
//Iisuse miluieste - ma 
ifstream f("lalele.in");
ofstream g("lalele.out");
f>>N;
f>>d;
f>>x;
i = 0;
while( !f.eof() )
     {
         if( x )
      	   {
 	   while( d )
  		{
  		 targ[ i ] = x;
		 for( j = 0; j <= i ; j ++ )
   		     targ[ j ] ++;
		i ++;
		d --;
		}
	  }
       if ( !x )
  	  {
           k = i;
	   GOD_sort ( targ , ( k - 1 ) );
	   while ( d )
                {
                  k = k / 2;
	          g<<targ[ k ]<<'\n';
		  d --;
		  for ( j = 0; j < k ; j ++ )
		       targ [ j ] ++;
                  }
            i = k;
	    }
      f>>d;
      f>>x;
      }
f.close();
g.close();
return 0;
}

si imi da killed by signal 11
Stiu ce e un signal 11 dar nu stiu la ce parte din cod imi face asta....
Va rog,daca puteti sa ma ajutati !!
e problema lalele de pe varena