Imprimă pagina - 132 Distante

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: ditzone din Noiembrie 19, 2005, 16:06:25

Titlul: 132 Distante
Scris de: ditzone din Noiembrie 19, 2005, 16:06:25

Aici puteÅ£i discuta despre problema Distante (http://infoarena.ro/problema/distante).

Titlul: 132 Distante
Scris de: Sara Nicolae Bogdan din Noiembrie 19, 2005, 16:09:38

Ce librarie trebuie sa includ sa folosesc memset?

Titlul: 132 Distante
Scris de: Bogdan-Cristian Tataroiu din Noiembrie 19, 2005, 16:21:15

string.h

Titlul: 132 Distante
Scris de: Sara Nicolae Bogdan din Noiembrie 19, 2005, 18:07:59

Titlul: Raspuns: 132 Distante
Scris de: Rus Cristian din Aprilie 10, 2006, 19:13:14

la problema asta...am facut un Lee...din nodul sursa...si iau 60 de pct....TLE pe restu...e mai bun Dijkstra?...

Titlul: Raspuns: 132 Distante
Scris de: Vlad Berteanu din Aprilie 10, 2006, 19:21:56

Nu prea cred ca ai facut lee pentru ca muchiile nu au cost 1...presupun ca ai facut Bellman-Ford care este N * M...Dijkstra este N^2 sau ( N + M ) Log N ( cu heapuri ). :thumbup:

Titlul: Raspuns: 132 Distante
Scris de: Rus Cristian din Aprilie 10, 2006, 19:32:11

dar..trebuie ca muchii sa aiba neaparat costul 1?...merge si fara sa fie 1...

Titlul: Raspuns: 132 Distante
Scris de: Filip Cristian Buruiana din Aprilie 10, 2006, 19:41:25

Nu merge cu Lee / BFS ( = cautare in latime ). Algoritmi de acest gen functioneaza numai in cazul in care toate costurile sunt egale. Aici costurile muchiilor pot fi diferite, deci trebuie facut cu djikstra pentru a calcula drumurile minime explicit.
Totusi tu trebuie sa vezi doar daca distantele sunt bune, deci nu trebuie sa faci djikstra, trebuie sa verifici daca vectorul indeplineste conditiile impuse in djikstra:
http://info.devnet.ro/articole.php?page=art&art=74&artpage=6
Deci algoritmul optim este O(N).

Titlul: Raspuns: 132 Distante
Scris de: Rus Cristian din Aprilie 10, 2006, 21:55:29

asa....deci....Dijkstra in N+M...
la inceput pun sursa in lista...apoi verific pt toate nodurile adiacente, distantele...daca is mai bune...pun nodul in lista...si il "relaxez"?...

Titlul: Re: 132 Distante
Scris de: Gogu Marian din Aprilie 10, 2006, 22:42:07

Nu prea ai cum sa faci Dijkstra in O(N+M). Solutia din articol nu mai face relaxari, decat verifica daca costurile date se pot obtine (daca se gaseste pentru fiecare nod x un alt nod y astfel incat c[y]+cost[y,x]=c[ x ]) si mai vede daca nu se pot imbunatatii costurile prin relaxare.

Titlul: Raspuns: 132 Distante
Scris de: Andrei Grigorean din Aprilie 12, 2006, 16:21:18

tie in problema nu ti se cere sa calculezi distantele, doar sa verifici daca sunt bune cele din fisierul de intrare. articolul cu solutii ar trebui sa te lamureasca. ;)

Titlul: Raspuns: 132 Distante
Scris de: VladS din Aprilie 13, 2006, 11:58:45

Nici eu nu cred ca ai cum sa rezolvi problema cu Lee pentru ca Lee face infasuratoare convexa.

Titlul: Raspuns: 132 Distante
Scris de: Filip Cristian Buruiana din Aprilie 13, 2006, 12:55:13

? Esti sigur ca face asta?... Eu cred ca pentru infasuratoare convexa e Hill ( sau Graham ), nu Lee...

Titlul: Re: 132 Distante
Scris de: Tiberiu-Lucian Florea din Aprilie 13, 2006, 13:46:22

Nu exista nici un algoritm Lee, decat in folclorul romanesc.
Lee, asa cum il numim noi, reprezinta de fapt cautare in latime (BFS).

Titlul: Raspuns: 132 Distante
Scris de: u-92 din Aprilie 13, 2006, 15:11:31

defapt exista algoritmul lui Lee, numai ca e ceva pt infasuratoare convexa cum zicea VladS mai sus (am gasit pe google :P )

Titlul: Re: 132 Distante
Scris de: Bogdan-Cristian Tataroiu din Aprilie 13, 2006, 15:29:36

Dude, ala e Hill... si nici ala nu prea exista oficial sub denumirea asta.. doar in folcloru' romanesc :)

[Later edit: mdea am gasit si eu pe google lee's algorithm pentru infasuratori convexe :-' ]

Titlul: Raspuns: 132 Distante
Scris de: ditzone din Aprilie 13, 2006, 15:32:57

Eh .. sunt doar denumiri.. nu cred ca e asa important ...
Oricum la problema asta nu e nevoie nici de Hill, nici de Lee :)

Titlul: Raspuns: 132 Distante
Scris de: Idolu' Femeilor din Mai 08, 2006, 12:10:02

Puteti sa-mi dati si mie niste teste la pb asta pls! Pe testele mele(facut de generator si rezolvate cu brute) imi merge dar evaluatoru imi da numai 0p. ](*,) ](*,) ](*,) ](*,)

Titlul: Raspuns: 132 Distante
Scris de: Damian Alexandru din Februarie 05, 2007, 17:08:26

are ceva special testul 7 la problema asta??

Titlul: Raspuns: 132 Distante
Scris de: Adrian Diaconu din Februarie 05, 2007, 19:11:49

Ai verificat ca intr-adevar fiecare nod i se afla la distanta D_i, adica exista o muchie (x,i) de cost c astfel incat D_i=D_x+c ?

Titlul: Raspuns: 132 Distante
Scris de: Damian Alexandru din Februarie 05, 2007, 20:01:14

nu, nu faceam asta. 10x. :thumbup:

Titlul: Raspuns: 132 Distante
Scris de: Savin Tiberiu din Februarie 05, 2007, 21:22:34

hmm.. si totusi de ce e o(n)?? mie mi se pare o(n*m). Ptr fiecare nod verific toate muchiile care pleaca din el. sau am inteles eu gresit??

Titlul: Raspuns: 132 Distante
Scris de: Bogdan-Cristian Tataroiu din Februarie 05, 2007, 21:26:44

M e numarul total de muchii. Pentru un nod nu verifici toate cele m muchii existente, ci doar cele care pleaca din acel nod. Per total verifici N noduri si M muhcii. -> complexitate O(N + M)

Titlul: Raspuns: 132 Distante
Scris de: Marius Stroe din Februarie 05, 2007, 21:27:04

Citat din mesajul lui: Savin Tiberiu din Februarie 05, 2007, 21:22:34

hmm.. si totusi de ce e o(n)?? mie mi se pare o(n*m). Ptr fiecare nod verific toate muchiile care pleaca din el. sau am inteles eu gresit??

Daca ai liste de adiacenta, atunci fiecare nod are grad[n] noduri in lista sa. Dar suma tuturor gradelor nodurilor e 2 * M, de unde complexitatea O(N + M).

Titlul: Raspuns: 132 Distante
Scris de: Savin Tiberiu din Februarie 05, 2007, 21:31:33

](*,) ](*,) ](*,) ](*,) ](*,) yep your'e right. scuze probabil ca lipsa orelor de somn isi face efectul :D. :fool:

Titlul: RÄƒspuns: Raspuns: 132 Distante
Scris de: Ciocas Radu din Februarie 28, 2007, 16:17:05

:'( incerc sa fac problema cu Dijkstra cu heapuri dar doar primul test e corect, la restul iau raspuns incorect, mi-am facut mai multe exemple si imi da bine, nu imi dau seama unde gresesc, la operatiile cu heap-ul sau unde... ca sa pot efectua Descreste_cheie(poz, val),cand relaxez, pastrez un vector id, id[i ]=pozitia in heap a nod-ului i, #-o . Ar putea cineva sa-mi dea un test si raspunsul :oops:(cu care cat de cat se poate face debug)? ... i just don't get it...(stiu ca este si solutie O(V+E) dar e important si acest algoritm)
Anyone ? :sad:

Titlul: RÄƒspuns: 132 Distante
Scris de: Paul Grigoras din Aprilie 15, 2008, 13:08:21

grafu e neorientat:)) eu am ncerkt sa o fac cu grafu orientat si...ghici ce! nu mi a mers. vz sa nu faci la fel:PP

Titlul: RÄƒspuns: 132 Distante
Scris de: Emanuel Cinca din Aprilie 18, 2008, 08:09:49

Am si eu o intrebare... am incercat sa fac Dijkstra si dupa aceea sa verific daca da acelasi rezultat...si bineinteles ca iau TLE pe 9 teste :-'... Am incercat sa verific doar conditiile, dar iau WA atunci... probabil nu verific corect... imi poate da cineva un indiciu despre cum ar trebui? In ce moment trebuie sa verific aceste conditii??? Ms! :peacefingers:

Titlul: RÄƒspuns: 132 Distante
Scris de: Bogdan-Alexandru Stoica din Aprilie 18, 2008, 09:14:33

ai citit articolul cu solutii (http://infoarena.ro/preoni-2006/runda-1/solutii)?
eu am luat 100 folosind Bellman Ford cu coada.

Titlul: RÄƒspuns: 132 Distante
Scris de: Emanuel Cinca din Aprilie 18, 2008, 10:14:38

O sa incerc si solutia explicata in articol... Dupa aceea o sa ma documentez si depsre Bellman Ford...ca nu stiu in ce consta algoritmul :P :D :peacefingers: Ms again!

Titlul: RÄƒspuns: 132 Distante
Scris de: avram florin constantin din Martie 02, 2011, 16:37:48

Poate cineva sa imi explice ce e gresit in rationamentul meu pentru ca iau doar 40 de puncte.Eu iau fiecare muchie din fisier si incerc sa vad daca pot obtine un drum mai scurt,adica x,y sunt capetele muchie,iar c costul si verific daca d

+c<d[y]||d[y]+c<d
,iar daca e asa inseamna ca Bronzarel nu a calculat bine distanta minima.E ceva gresit in asta?

Titlul: RÄƒspuns: 132 Distante
Scris de: Florin Chirica din Septembrie 12, 2012, 20:29:47

Cand aveti timp, puteti mari limita de timp? Solutia O(T * (N + M)) ia doar 50 de puncte, iar sursa asta lua inainte 100: http://infoarena.ro/job_detail/787223?action=view-source . Multumesc.

Titlul: RÄƒspuns: 132 Distante
Scris de: Mihai Calancea din Septembrie 12, 2012, 20:36:24

Pai din cauza sursei aleia si altora in genul ei am schimbat limita. Sursa aia face dijkstra. Probabil era intr-adevar prea stransa, am mai pus 0.02 :roll:.
Daca tot nu merge, nu mai folosi STL, si nu fa operatii inutile. N-ai nevoie sa construiesti graful deloc aici. Ai nevoie doar sa parcurgi muchiile o data.

Titlul: RÄƒspuns: 132 Distante
Scris de: liana tucar din Noiembrie 22, 2012, 19:00:09

Cred ca limita de timp e prea mica. Iau 60 de puncte(cu tle pe testul 7) si nu stiu cum as mai putea optimiza. Am O(t*(n+m)).

Titlul: RÄƒspuns: 132 Distante
Scris de: Salajan Razvan din Noiembrie 22, 2012, 19:53:52

Incearca sa parsezi citirea. S-a luat 100 de puncte chiar azi.

Titlul: RÄƒspuns: 132 Distante
Scris de: Petcu Ioan Vlad din Februarie 18, 2013, 18:01:51

Faptul ca c poate fi si 0 nu se prea vede in teste...

Edit: Nu m-am exprimat destul de clar, pe testul
4 3 1
0 1 2 1
1 3 2
1 2 7
2 4 0

una din solutiile oficiale ar raspunde DA, iar raspunsul este NU

Titlul: RÄƒspuns: 132 Distante
Scris de: Elena Obreja din Mai 07, 2013, 08:50:26

Va rog frumos daca puteti sa ma ajutati putin. Am trimis o sursa care da 0 puncte. Treaba este ca, la primul test totul da bine si de la urmatoarele nu mai da corect. Cred ca are legatura cu folosirea succesiva a unor vectori. Oricum, daca imi puteti spune opinia voastra...

Asta e sursa :D

Cod:

#include<fstream>
#define inf 10001
using namespace std;
ifstream f("distante.in");
ofstream g("distante.out");
struct muchie
{
    long x,y,c;
}q[100001];
long t;
long n,m,s,gasit;
long d[50001];
long v[50001];
int main()
{
    long x,y,c;
    long ok;
    f>>t;
    for(long k=1;k<=t;k++)
    {
        gasit=0;
        f>>n>>m>>s;
        for(long j=1;j<=n;j++)
         f>>v[j];
        for(long j=1;j<=m;j++)
        {
            f>>x>>y>>c;
            q[j].x=x;
            q[j].y=y;
            q[j].c=c;
            if(x==s)
             d[y]=c;
            if(y==s)
             d[x]=c;
        }
        for(long i=1;i<=n;i++)
         if(d[i]==0&&i!=s)
             d[i]=inf;
        do
        {
            ok=1;
            for(long i=1;i<=m;i++)
             if(d[q[i].y]>d[q[i].x]+q[i].c)
             {
                 d[q[i].y]=d[q[i].x]+q[i].c;
                 ok=0;
             }
        }while(!ok);
        /*for(long i=1;i<=n;i++)
         g<<d[i]<<" ";
        g<<"\n";*/
        for(long i=1;i<=n;i++)
          if(d[i]!=v[i])
           gasit=1;
        if(!gasit)
         g<<"DA"<<"\n";
        else
         g<<"NU"<<"\n";
    }
    return 0;
}

Foloseste tag-ul [ code ] [/ code ] cand postezi cod.

Titlul: RÄƒspuns: 132 Distante
Scris de: Matei Vlad din Mai 18, 2013, 14:26:35

Vezi ca tu nu ai eliminat muchiile din graf. Fiecare nou graf va mosteni muchiile predecesorului sau. Am patit si eu aceeasi chestie.

Titlul: RÄƒspuns: 132 Distante
Scris de: SwissRhino din Iulie 22, 2013, 22:18:29

Testele la problema aceasta sunt foarte proaste.
O solutie care verifica doar daca nu se pot face imbunatatiri ia 100 de puncte.

Cod:

 if (best[a] + c < best[b] || best[b] + c < best[a]) ok = false

Asa ca va rog sa inlocuiti un test cu acest test

Cod:

2 1 1
0 0
1 2 1

PS: cred ca 5 din ultimele 6 surse de 100 sunt gresite.

Titlul: RÄƒspuns: 132 Distante
Scris de: theprdv din Martie 31, 2015, 04:38:01

Citat din mesajul lui: SwissRhino din Iulie 22, 2013, 22:18:29

Testele la problema aceasta sunt foarte proaste.
O solutie care verifica doar daca nu se pot face imbunatatiri ia 100 de puncte.

Cod:

 if (best[a] + c < best[b] || best[b] + c < best[a]) ok = false

Asa ca va rog sa inlocuiti un test cu acest test

Cod:

2 1 1
0 0
1 2 1

asa e... nu sunt bune testele pentru ca nu e nici un test in care se verifica daca o distanta calculata de Bronzarica ala e mai mica decat cea corecta.. (adica verificam pentru toate nodurile daca se gaseste distanta calculata de Br.)

PS: cred ca 5 din ultimele 6 surse de 100 sunt gresite.