eu am facut backtracking iterativ si iau doar 30 de puncte.. ma asteptam sa iau cam atat, totusi cum as putea optimiza? (optimizata cred ca ar trebui transformarea din baza 2 in baza 10, pentru ca eu fac liniar, se poate in o(1) ?)
multumesc

daca pun s pe int iau incorect pe 4 teste, ca zice la restrictii ca e recomandat sa lucrezi cu var de tip long long (64 biti)

nu prea inteleg cum sa fac asta, eu in deque tin pozitiile in vectorul s (cel long long), iar la s am s[ i] = (b[1]-d[1]) + (b[2]-d[2]) + ... + (b[ i]-d[ i]) unde b[] sunt litri la o benzinarie si d[] distanta, deci nu prea vad cum cu o variabila  

eu iau MLE cu un deque de int si un vector long long de 2.000.000
chiar nu am idei ce sa mai scot.. ma poate ajuta cineva?
multumesc

am si eu o intrebare: rezolvarea cu deque e buna si intra la limita nu? (adica eu am luat prima data 90, apoi am retrimis aceeasi sursa si am luat 100) 

da dar solutia nu e chiar O(n), e mai mult (O(n * nr de intoarceri) nu?)

eu am alta idee care nu e o(N)
fac cam asa:
iau un vector in care v[ i ] este pozitia turnului din stanga pana la care se poate vedea de pe turnul i
apoi fac un for de la 1 la n si det turnul pana la care se poate vedea asa:
daca sunt la turnul i, verific pentru turnul i - 1.
daca turnul i - 1 e mai inalt ca i atunci ne oprim si punem v[ i ] = i - 1;
daca nu ne ducem la v[i - 1], care e primul turn strict mai inalt ca i - 1 (sa zicem ca v[i - 1] = j) si verificam pentru ala
daca ala e mai inalt ne oprim si punem v[ i ] = j;
daca nu verificam pt v[j], care e primul turn strict mai inalt decat j
si tot asa...
asta pentru partea stanga, si pentru dreapta tot asa
si eu am pe un test cam o secunda, deci sigur nu e solutia buna, o sa ma uit la cea cu stiva chiar is curios cum ai scos o(n)
multumesc

L.E. : da mi se pare ca de fapt is aceleasi solutii nu?

pai nu cred ca e o(n) complexitatea avand in vedere ca limita e 1.7 sec nu ?

daca fis de intrare ar arata asa:
3
100
30
10

si ne-am uita de pe turnul 3, nu am vedea turnul 1 deoarece e blocat de turnul 2? (pt ca turnul 2 e strict mai inalt ca turnul 3 si e primul ca distanta?)
multumesc

intr-adevar depaseam dimensiunea vectorului B (nu mi-am dat seama ca daca este || i-ul se va duce pana la l care e maxim 1.000.000 )

mersi pentru ajutor paul

eu iau 40 cu KBS pe testele 5 - 10, facand M = N + (D - (N % D)) (pe numere mari)
care sa fie problema?(am verificat sa nu fie impartiri la 0, sa nu fie nr prea mare, sa intre in mem)

multumesc

am nevoie de putin ajutor, am 2 surse aproape identice, una de 100 si alta de 60 si chiar nu vad care e diferenta
sursa de 100:

Cod:

# include <fstream>
  using namespace std;
    int A, B, st, dr, p1, p2, sol;
	char a[(10000000 >> 3) + 100000];
    int main (){
		ifstream f ("difprim.in");
		ofstream g ("difprim.out");
		f >> A >> B;
		int i = 4;
		for (i = 4; i <= 10000000; i += 2)
			a[i >> 3] |= (1 << (i & 7) );
		i = 1;
		while (i <= 400000){
			do{ 
				i += 2;
			}while (     ( a[i >> 3] & (1 << (i & 7) ) )      );
			for (int j = i + i; j <= 10000000; j += i) 
				a[j >> 3] |= (1 << (j & 7) );
		}
		//for (i = 1; i <= 30; ++i) 
		//	if (    !( a[i >> 3] & (1 << (i & 7) ) )      )
		//		g << i << ' ';
		for (i = A + 1; i < B; ++i){
			if (  !(   a[i >> 3] & (1 << (i & 7) )   )  ){
				st = dr;
				dr = i;
				if (sol < dr - st && st){
					sol = dr - st;
					p1 = st;
					p2 = dr;
				}
			}
		}
		if (!sol) g << "-1\n";
		else
			g << p1 << ' ' << p2 << '\n';
		g.close ();
		return 0;
	}
	

si cea de 60:

Cod:

# include <fstream>
  using namespace std;
    std :: ifstream f ("difprim.in");
	std :: ofstream g ("difprim.out");
	char a[(10000000 >> 3) + 10000];
	int A, B;
	void ciur (){
		for (int i = 4; i <= 10000000; i += 2)
			a[i >> 3] |= (1 << (i & 7) );
		int i = 1;
		while (i <= 100000){
			do {
				i += 2;
			} while (a[i >> 3] & (1 << (i & 7) ));
			for (int j = i + i, val = (i << 1); j <= 10000000; j += i) a[j >> 3] |= (1 << (j & 7) );
		}
	}
	int af1, af2, MAX = 0;
	int main (){
		f >> A >> B;
		ciur ();
		int ac, an;
		for (int i = A + 1; i < B; ++i){
			if ( !(a[i >> 3] & (1 << (i & 7) ) ) ){
				an = ac, ac = i;
	    		if (MAX < ac - an && an){
				    MAX = ac - an;
					af1 = an;
					af2 = ac;
				}
			}
		}
		if (!MAX) g << "-1\n";
		else
			g << af1 << ' ' << af2 << '\n';
		return 0;
	}

as fi recunoscator celui care mi-ar zice ce e gresit in cea de-a doua
multumesc  

are ceva special testul 7 ?  

si mie imi pica acelasi test, are cineva vreo idee cam despre ce e vorba?
multumesc

din complexitatea oficiala (NlogN), logN e de la cautare binara?

mi-a iesit in cele din urma, multumesc tuturor pentru ajutor

totusi, cautarea aceea (sa cauti al i-lea elem intrat) nu se poate face si cu hashing? 

acum am inteles ideea, dar iau 10 puncte cu sursa implementata asa 
i-am mai dat teste si ies toate, am facut si cu debuggerul ca sa fiu sigur ca trece bine in t[] si intr-adevar e bine , iar testele de la atasamente sunt cam mari ..
as ramane recunoscator celui care m-ar ajuta

multumesc

paul, tu vrei sa zici ca iau un vector v[] in care v[ i ] e al i-lea inserat si mai iau un vector t[] in care t[ i ] este pozitia in heap a celui de-al i-lea inserat?

si daca e asa, ca sa fac elementul al 2-lea inserat sa zicem fac:
int element = v[2];
int pozitie = t[2];  

da dar cum, nu vad cum ar putea intra in memorie (nr sunt pana la 1000000000) deci nu pot lua un vector in care fac ap[v] = i;

imi spune cineva va rog ce as mai putea optimiza la sursa asta http://infoarena.ro/job_detail/514478?action=view-source

multumesc

multumesc pentru raspuns

am inteles asta, dar alta era intrebarea:

de exemplu daca am alt text


Ieri am fost la mare  ....      !!!     asa e

sunt  3 propozitii sau 2? (adica altfel formulat, o fraza poate avea numai semne de punctuatie sau trebuie neaparat si litere)

in urmatorul text:



Ieri am fost la mare ...   !!!       



sunt 2 fraze sau una singura?

cred ca erorile tale ar putea fi urmatoarele:
1.ar fi http-ul ala de la inceput dar cred ca a aparut de la site
2.ai grija ca implementarea trebuie pe nr mari
3.nici solutia nu e buna, tu poti si sa aduni nu numai sa scazi, citeste solutia lui robert simoiu din acest topic si incearca sa o faci pe numere mari pentru 100 de puncte (operatiile pe numere mari le gasesti in articolul cu smenuri de programare)

bafta 

imi explica va rog si mie cineva care e ideea cu heapuri ca nu pot sa imi dau seama 
multumesc

dar de ce este necesar sa scri numarul in baza 2, nu merge si fara, sau e pentru optimizare?