Am sa incerc sa mi-l instalez sper sa n-am probleme la partiti ca si alti.

Daca vreu sa folosesc ubuntu impreuna cu un alt sistem de operare imi creaza el meniu din care sa aleg ce sistem de operare sa folosesc?

Da NlogN e solutia.Eu am facut cu un arbore de intervale si o lista dublu inlantuita si am luat doar 50p

Poate sa-mi explice si mie cineva ce e gresit in urmatoarea sursa. Am luat in considerare toate cazurile cand segmentele se intersecteaza is paralele sau segmentele is pe aceasi dreapta si iau doar 20p??

Cod:

const fis='geometry';
      nmax=500;
var x1,x2,y1,y2,a,b,c:array[1..nmax] of longint;
    n,rez:longint;

Procedure read_data;
var i:longint;
begin
readln(n);
for i:=1 to n do
    begin
    readln(x1[i],y1[i],x2[i],y2[i]);
    a[i]:=y2[i]-y1[i];
    b[i]:=x2[i]-x1[i];
    c[i]:=(x1[i]*y2[i])-(x2[i]*y1[i]);
    end;
end;

Procedure compute;
var i,j:longint;
    y:real;

Function peg(n1,n2:longint):boolean;
begin
if a[n1]*b[n2]=a[n2]*b[n1]
then peg:=true
else peg:=false;
end;

Function ini(aa,bb:longint;c:real):boolean;
var a,b:longint;
begin
if aa<=bb
then begin
     a:=aa;
     b:=bb;
     end
else begin
     a:=bb;
     b:=aa;
     end;
if (a<=c) and (c<=b)
then ini:=true
else ini:=false;
end;

begin
for i:=2 to n do
    for j:=1 to i-1 do
        if peg(i,j)
        then begin
             if (c[i]=c[j]) and (ini(x1[i],x2[i],x1[j]) or
             ini(x1[i],x2[i],x2[j]) or ini(x1[j],x2[j],x1[i]) or ini(x1[j],x2[j],x2[i]))
             then inc(rez);
             end
        else begin
             y:=((c[j]*a[i])-(c[i]*a[j]))/((b[i]*a[j])-(b[j]*a[i]));
             if ini(y1[i],y2[i],y) and ini(y1[j],y2[j],y)
             then inc(rez);
             end;
end;

begin
assign(input,fis+'.in');
reset(input);
assign(output,fis+'.out');
rewrite(output);
read_data;
compute;
writeln(rez);
close(output);
close(input);
end.

Imi poate spune si mie cum se fac sufix array-urile in N log N. Nu stiu cum fac sortarea aia in O(n) implementat cu merge sort are complexitate N log^2N si iau 80p dar is curios cum se face  in N log N.

da cred ca de aia luam numai 80p.

Pai complexitatea ii NlogN. Hint cauta binar lungimea. Problemele astea ii clasice incearca sa faci si secventa 3 ideea ii cam aceeasi.

094Hotel -misto ideea cu arborele binar
098Parcela -ii faina ideea chiar daca inca n-am avut timp s-o implementez
217Popandai2 -la Moisil nu imi trecea prin minte ca ar merge cu o cautare binar si am facut brute force
025Munte -la momentul cand am rezolvat-o mi se parea cea mai grea problema de dinamica pe care am facut-o
084Algola -inainte sa o fac nu credeam ca se face asa usor mi se parea chiar imposibila

Poate cineva sa dea un hint la problema asta.

Algoritmul in O(NlogN) la problema asta nu-i optim exista un algoritm in O(N) care ii usor de demonstrat si merge la prob asta. Am luat 80p cu el dar faza ii ca am gresit la implementare ca de obicei. Si faza ii ca nu-i greedy cum scria Matrix mai sus ci PD  .

Ce fel de fibbonaci se poate face? Eu ma gandeam sa precalulez care is valori nodurilor si sa vad pt fiecare nod care nod e parintele lui dar nu am destula memorie poate sa-mi spuna cineva si mie ce algoritm sa folosesc

Ok, o sa-l citesc si o sa incerc sa il implementez.

Da am vazut acum cu algoritmul meu in N log^2 N merge de 30 pe restu iau tle.  Dar nu stiu cum sa-l aduc la N log N. Ideea ii ca folosesc 2 arbori de intervale unul care retine minimul si unul care retine suma. Faza ii ca atunci cand elimin o scandura trebe updatati cei 2 arbori. Ca sa modific in arborele cu minim tre sa fac log^2 N operatii deoarece la ficare nivel in fii care contin nodul eliminat  tre sa vad cat ii minimul rasmas si asta o fac verificand cat ii suma in minimul in stanga si dreapta. Imi puteti spune careva cum sa mai optimizez.

Mi-ati putea da si mie un hint. Singura solutie pe care o stiu la problema asta merge in N^2 si evident nu intra in timp.

La problema asta cat ii complexitatea. Algoritmul meu merge in N log^2 N se poate si in NlogN???

Totusi ce ii un graf planar ca nu am mai auzit de denumirea asta?

Pentru testul 1,3,4,2,1 raspunsul va fi
2
1 4?

Cu un Lee iti merge sigur mai ales ca graful este rar fiecare nod poate avea cel mult 4 muchii.Ai grija numai cum implementezi .

De la ora 8 si un sfert nu merge evaluatorul. Puteti face ceva ca acesta sa porneasca ? sau daca nu spuneti peste cat timp va porni?

Scuze  Mircea cati-am scris pe private topic dar sunt la primul mesaj pe acest form si nu m-am prea descurcat. Deci as dori la aceasta problema Loto unul din testele 5,6,8,11,13,14,15,16,17,18,19 sau 20 ca sa-mi dau seama unde am gresit.