se garanteaza ca in fiecare test va fi macar un element diferit de # ?

Da. Cu cautare binara. Fa primadata solutia in n^2 si apoi incearca sa o reduci la N * log N.

Salut! Iau incorect pe primul test si nu ma prind de ce.
Solutia mea e cam asa : iau fiecare pereche de 2 segmente si vad daca se intersecteaza;
Verific daca doua segmente se intersecteaza astfel : iau un segment si vad daca punctele care determine celalalt segment se afla in semiplane opuse fata de segmentul ales.

L.E. : Mi-a iesit pana la urma.

Ai grija ce bagi in ciur2;in acel while cred ca la un momendat bagi numere mai mari ca si 100 de milioane; m-am uitat si peste ultima sursa trimisa de tine si ai la sfarsit for(int i=A; i<=B; ++i) if ( ciur2[ i ] ) blaala...; acel i depaseste 100 de milioane

Poti sa rezolvi problema http://infoarena.ro/problema/evaluare la care ai teste disponibile si apoi poti reveni la problema asta. Asa sigur iti vei da seama unde gresesti.  

Care e legatura dintre cele 2 probleme?

Salut!
Am complexitatea(M*K^2*logN) şi iau 40 de puncte cu tle. Iniţial mi s-a părut mult pentru 0.3 aşa că am încercat să optimizez soluţia dar nu am reuşit. Am citit soluţia şi spre surprinderea mea şi complexitatea oficială e la fel. Din ce cauză iau tle ? (Dijkstra l-am implementat cu priority_queue.) O fi de la evaluator sau de la mine ?!

Salut! Am încercat o soluţie în m*n*L; unde L = lungimea maximă a unui cuvânt; mai exact fac un dp[ i ] = numărul minim de caractere ce trebuie să le elimin astfel încât să pun un cuvânt care să nu treacă de poziţia i; practic pentru fiecare poziţie i încerc să pun un cuvânt  j, care să nu depăşească poziţia i. Cu această soluţie iau 30 de puncte. Pe restul testelor iau incorect şi tle.

L. E. : Mi-a ieşit pana la urmă!

Salut!
Am o complexitate de N*K*Const (const fiind de la numerele mari) dar iau maxim 90 de puncte! Ultima sursa de 100 de puncte a fost la inceputul anului. De vina e  : evaluatorul sau implementarea mea ?

Salut ! Am facut si eu o dinamica in B*N*K*10 dar iau TLE pe ultimul test; ceva idei de optimizare : http://infoarena.ro/job_detail/779421?action=view-source .

Raspunsul corect e 39.
Si ii iei asa : initial ai : 8 3 1 5 2.
Prima lupta : iei al 3 lea luptator cu ultimul luptator => Cost = 1 + 2 = 3; Raman luptatorii : 8 3 5 3(asta ultimul e noul format)
A 2-a : il iei pe al 2-lea si pe ultimul => Cost +=  3 + 3 = 9; Raman luptatorii : 8 5 6;
A 3-a : il iei pe al 2-lea si pe ultimul => Cost += 5 + 6 = 20; Raman luptatorii : 8 11;
Ultima lupta : pe primul si pe al 2-lea(evident ) ) => Cost = 20 + 8 + 11 = 39; Ramane doar unul singur si ma opresc

Fac mai multi arbori. In unul retin maximul , in unul minimul , in unul dif maxima , in unul dif min. Dif min este valoarea minima dintre: fiul stang , fiul drept , diferenta dintre maximul stang si maximul drept , diferenta dintre minimul stang si minimul drept. Cred ca mergea bine ( nu sunt sigur , dar cred ca de la implementare iau incorect ). Daca nu incearca pe alta idee. Succes.  

Cum adica doar crezi ca mergea? (din moment ce tu ai 100 de puncte ?)

stardust : uite cum m-am gandit eu sa fac operatia Min-dif(la celelalte presupun ca te descurci) : Tin un set in care pun diferenta dintre 2 termeni consecutivi; acum trebuie sa fi atent(sa vezi cum modifici set-ul cu diferentele) cand elimini un element si cand introduci un element; cu aceasta idee iau 60 de pct : 2 tle-uri si 2 Killed by signal 11

Salut ! Imi spune cineva cum ajung la complexitatea o(n^2); in momentul de fata am n^3 : iau cate o linie si presupun ca un dreptunghi se afla deasupra liniei si celalalt dedesubt(la fel si pt fiecare coloana); un dreptunghi de arie maxima il aflu in n^2;

Salut!
Am facut si eu 2 rezolvari : n * Hmax^2; iar a doua n * Hmax cu deque; cu ambele solutii iau incorect pe testul 3; (evident pe celelalte iau corect cu a 2 sursa si tle/mle cu prima)
Ce are acest test mai special ?

L.E : Mi-a iesit pana la urma; se pare ca am avut o greasela stupida in cod (ma mir ca am luat asa multe puncte cu acea greseala)

Salut!
Am facut o rezolvare M*N cu deque dar iau doar 40 de puncte;(pe restul iau tle)
Din cele citite mai sus aceasta ar fi complexitatea oficiala; si totusi care ar fi problema ?

8
38
128
138
290
359
443
In locul tau as incerca sa gasesc alt mod de a a sorta elementele!

Tot nu e bine! Schimba idea !
uite un test pe care pica sursa ta :
7
2 10
1 8
5 3
1 1
9 8
4 3
6 10
Out(corect) : 443

incearca si varianta in care comprimi fiecare linie in numere; asa nu vei avea m numere(de 0 si 1) ci vei m/x (x = numarul de biti din care formezi un numar)

A mers! Multumesc pentru sfat!

Iau pe ultimele 3 teste TLE. Am facut cu arbori de intervale si mi-am precalculat in o(n) puterile B^1...n % P. Am incercat si parsarea dar rezultatul a ramas la fel!

Presupun ca ai facut solutia in n^2... Pt o(n) idea e sa faci o singura parcurgere df si sa reti cateva informatii despre fiecare nod. Iti alegi un nod(o radacina) si apoi faci un df din acel nod; In arborele df ti pentru fiecare nod cate noduri are in subarbore(fie vectorul a[]) si adancimea maxima de la nodul actual pana la o frunza(fie vectorul b[]). Raspunsul va fi minimul din b[]; doar ca dupa ce faci df-ul trebuie sa actualizezi anumite valori din b[] pentru ca tu in Df ai calculat adancimea maxima de la nod in jos dar poate fi si varianta sa fie in sus; si tot ce ramane de facut e sa actulizezi
b[nod] = max(b[nod], n-a[nod]); avand n noduri si tu stiind ca in subarborele cu radacina nod ai a[nod] noduri atunci inseamna ca celalalt drum care exista si nu l-ai luat in considerare in parcurgerea Df va avea n-a[nod] noduri;

Iau 40 de puncte cu tle pe restul; am complexitatea o(2*L*n + m + 2^L*L); iar complexitatea oficiala e o(n + m + 2^L*L); acel 2*L de langa n sa fie problema sau alta care ar fi ?
L.E. : Am reusit pana la urma sa iau 100 de pct; intr-adevar acel 2*L era problema

nu prea inteleg la ce te referi prin "trucul ala sa updatez doar cand e nevoie."; la aceasta problema ai nevoie de minimul pe un interval si apoi trebuie sa actulizezi eficient intervalul[1,min.poz](complexitatea e log n, dupa cum ai zis si tu) pentru a actualiza un interval in log n te folosesti de lazy propagation; ti 2 vectori unul Min[]=care iti zice minimul si un vector add[] care iti spune cu cat a fost actualizat intervalul curent pana in acest moment ; de fiecare data cand faci udpate pe un interval [x,y] ii dai functiei tale de update nu o pozitie(ca de obicei) ci un interval [x,y] ; si acum cand gasesti un interval(din arborele de intervale) care intra in [x,y] trebuie sa ii actualizezi Min[nod] si add[nod]; acum mai ramane ca atunci cand te duci in sus pe arbore si iei minimul dintre fi,  acestui minim trebuie sa ii mai adaugi si add[nod](valoarea cu cat a fost actualizat acest interval); si ar cam trebui sa mearga

incearca sa scapi de for-ul de dupa ce afli pozitia (iti mananca timp si il poti scoate )

Pentru informatician28, uite un test pe care sursa ta il pica :
7 4
1 3
1 6
3 7
5 7
sursa ta afiseaza 1, 0, 1, 1 ; iar raspunsul corect e : 1, 0, 1, 0 ;

Salut! Iau 90 de puncte cu tle pe ultimul test. Am complexitatea (n+m) log n folosind un arbore de intervale si am folosit citerea parsata.
Am incercat cu aib si iau 60 de puncte cu tle pe ultimele 4.