467 Orase

[•DITzoneC]

Aici puteţi discuta despre problema Orase.

[•gabitzish1]

Ce complexitate trebuie sa aiba solutia?

[•cos_min]

Eu am reusit sa scot un O(n*logn), pe total, si am luat 100 pcte.

[•Dastas]

in exemplu, strazile sunt:

5 6
2 2 (1)
0 3
2 7 (2)

distanta dintre orasele de la capatul strazilor (1) si (2), care este? 7+2 = 9, sau 7-2 = 5? Se pot suprapune strazile?

[•Florian]

Pai..dupa cum vezi in explicatie [ in desen ] strazile au fost desenate una in sus si una in jos, asta pentru a simplifica probabil intelegerea. Cred k se pot suprapune, insa calculul distantei va ramane la fel [ dist (i,j)=li+ lj <=>asta doat in cazul suprapunerii]. Sau...mai simplu:considera orice pereche i,j kare s-ar "suprapune" k fiind opuse [ k in desen] si s-a rezolvat tot. 

[•Dastas]

pai si daca am:

2 2
2 3
2 4

cum mai consider ca sunt opuse? 
probabil ca-i asa cum spui, n-am rezolvat inca problema, dar nu prea e logic...

[•Protoman]

Din moment ce nu este precizat modul lor de asezare atunci ramane de datoria ta sa il alegi... si pentru a obtine maximul te duci cu max1 intr-o directie si cu max2 in cealalta . In cazul tau rezultatul va fi 7

[•sima_cotizo]

Am facut un program N log N, imi ia 30 cu TLE si un WA... nu asta conteaza... ci faptul ca am facut in main

Cod:

return 50;

daca N>50000... si am 6 teste cu NonZero Exit Status... Care sunt limitele pana la urma?

[•cos_min]

N <= 50000. Pentru ca eu mi-am declarat astfel sirurile pe care le-am folosit si a mers fara probleme.

[•sima_cotizo]

Tocmai scriam un reply in care sa sustin ca nu e asa, dar am gresit ... citeam (n,m) nu (m,n)... Greseala mea, scuze! 

[•c_sebi]

[..]
distanta dintre orasele de la capatul strazilor (1) si (2), care este? 7+2 = 9, sau 7-2 = 5? Se pot suprapune strazile?

Probabil ca atunci cand vrei sa mergi dintr-un oras in altul trebuie sa treci si pe strada principala: dist(i, j)=L[ i]+L[j]+|D[ i]-D[j]|.

[•Florian]

Cum se face asta in N logN? Care e idea care sta la baza algoritmului..? k nu ma prind Am o rezolvare N^2 cu care prind numa` 40 de puncte...

[•Binary_Fire]

Pai N*logN vine de la sortare , dupa care liniar determini maximul . Mai mult nu zic ca deja e mare spoiler ce am zis

[•c_sebi]

Am rezolvat problema, insa nu m-am folosit nicaieri de M (lungimea strazii principale). Voi ati folosit-o undeva?

[•CezarMocan]

Pai probabil ca te ajuta daca faci sortare de aia in timp liniar ca sa nu mai trebuiasca sa afli maximu din sir... alta utilizare nu-i vad...

[•peanutz]

In articol e:

Cod:

distanta care trebuie parcursa intre doua orase i < j: Li+Di+Lj-Dj

cred ca e j < i..

[•domino]

Asa e.

[•anna_bozianu]

Am rezolvat problema, insa nu m-am folosit nicaieri de M (lungimea strazii principale). Voi ati folosit-o undeva?

Eu nu. Doar ca am vazut ca solutia este <=3.000.000 deci intra pe long int. In rest in m-a "ajutat" ca pe altii sa fac citirea in ordine gresita a lui m si n 

[•zloteanu.adrian]

Am incercat solutia oficiala, dar iau numai 50 de puncte, restul sunt TLE-uri
ce sortare ar trebui sa folosesc?(cu insertion sort fac acum)
http://infoarena.ro/job_detail/329952
cred ca se blocheaza undeva, dif de timp e uriasa!

[•c_e_manu]

Foloseste quicksort. Desi ar trebui sa intre si cu mergesort, ambele avand complexitatea O(nlogn).

[•zloteanu.adrian]

nu am invatat quicksort, chiar daca stiu ca e cel mai rapid 
oricum, caut pe net

[•CezarMocan]

Foloseste sort-ul din STL. Incluzi libraria <algorithm> si apoi scrii sort(sir + 1, sir + N + 1);

[•zloteanu.adrian]

adica pentru vectorul a[50000] scriu sort(a+1,a+n+1)?

[•jupanubv92]

  Da, unde n reprezinta numarul de elemente din vectorul a[50001] . Daca ai elemente in vector de la 1 atunci scri sort(a+1,a+n+1) , iar daca ai de la 0 scri sort(a,a+n);
  Uite aici un exemplu , sper sa te ajute :

Cod:

#include<fstream.h>
#include<algorithm>

using namespace std;

int n,a[500001];

int main()
{
    ifstream fin("sort.in");
    ofstream fout("sort.out");
    fin>>n;
    for(int i=1;i<=n;++i)
      fin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i)
      fout<<a[i]<<" ";
    return 0;
}

[•zloteanu.adrian]

multumesc mult!! karma plus la toti