564 Rfinv

[•DITzoneC]

Aici puteţi discuta despre problema Rfinv.

[•Dastas]

Exista ceva cazuri particulare mai subtile? Am facut rezolvarea in O(n³) si iau incorect

[•filipb]

Ai grija sa verifica ca daca pentru o pereche (i j) nu exista nici un k pentru care distanta de la i la k + distanta de la k la j sa fie egala cu distanta de la i la j si nu ai muchie de la i la j in graful initial, atunci trebuie sa afisezi ca nu exista solutie.

[•Dastas]

Pai, in solutia oficiala spune:

Pe fiecare muchie a grafului (i,j) se pune o distanta egala cu valoarea A[j] (A fiind matricea data). Se aplica apoi algoritmul Roy-Floyd pe acest graf, iar matricea distantelor obtinuta trebuie sa fie identica cu matricea distantelor data (in caz contrar neexistand solutie).

Eu asa am facut. Am mai pus si verificarea zisa de tine, dar tot incorect iau..

N-ar trebui sa ajunga doar pasii din solutia oficiala?

[•filipb]

Eu am facut un pic altfel ( de fapt e acelasi lucru cu solutia oficiala dar e formulat altfel ):

* pentru fiecare pereche (i j) trebuie sa am A[ i ][ j ] <= A[ i ][ k ] + A[ k ][ j ] pentru orice k. Daca exista un k pt. care A[ i ][ k ] + A[ k ][ j ] < A[ i ][ j ] => nu am solutie
* daca exista o pereche (i j) pt. care nu exista nici un k a. i. A[ i ][ j ] = A[ i ][ k ] + A[ k ][ j ] si nu am muchie de la i la j in graf => nu am solutie

Eu am facut asa si am obtinut 100 .

[•Dastas]

Mi-a iesit pana la urma, mersi!

[•toni2007]

solutia in n^4 nu intra in timp? (nici cea din articolul de solutii nu-mi intra)

[•sigrid]

Intra un O(n^3) . Ce faci tu in O(n^4)?

[•toni2007]

fac exact ca in articolul de solutii

Vom sorta toate cele O(N2) distante din matrice in ordine crescatoare si vom initializa o matrice D[j]=infinit, pentru i <> j, respectiv 0, pentru i=j. Pe masura ce parcurgem sirul sortat al distantelor, vom actualiza valorile din matricea D. Sa presupunem ca am ajuns la o distanta avand valoarea x, ce reprezinta distanta minima dintre 2 noduri i si j. Daca D[j] < x sau D[j] > x si nu exista muchie in graf intre i si j, atunci nu avem solutie si ne oprim. Daca D[j] > x si exista muchie intre i si j, atunci vom pune pe aceasta muchie costul x. In continuare, va trebui sa actualizam valorile D[a] afectate de setarea valorii x pe muchia (i,j). Mai exact, pentru fiecare pereche de noduri (a,b), D[a] va fi egal cu minimul dintre valoarea actuala D[a] si min { D[a] + x + D[j], D[a][j] + x + D }.

Daca nu am intalnit nici o contradictie pe masura ce am parcurs muchiile, atunci raspunsul este "DA" ; in caz contrar, raspunsul este "NU".

am schimbat sortarea din qsort in sort din stl si acum merge in timp da imi da incorect...

puteti si voi sa puneti un test mai lung? ca nu ma prind

[•fireatmyself]

Cod:

3
5 8
1 2
1 3
1 5
2 3
2 4
3 4
3 5
4 5
0 9 67 71 41
98 0 165 169 139
67 165 0 4 26
71 169 4 0 30
41 139 26 30 0
6 8
1 4
1 5
2 3
2 4
3 4
3 5
4 6
5 6
0 39 9 80 6 82
39 0 30 101 33 109
9 30 0 71 3 79
80 101 71 0 74 60
6 33 3 74 0 76
82 109 79 60 76 0
7 16
1 2
1 4
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7
0 28 57 56 52 62 72
28 0 31 32 24 34 44
57 31 0 1 7 17 27
56 32 1 0 8 18 28
52 24 7 8 0 10 20
62 34 17 18 10 0 10
72 44 27 28 20 10 0

raspunsurile sunt NU, DA, respectiv DA.

[•sigrid]

Eu aveam o problema la rfinv pentru ca nu initializam matricea inainte de fiecare test si ramaneau in ea valori din testele anterioare. Vezi sa nu gresesti si tu asta 

[•toni2007]

mie imi da NU NU NU... tre sa mai lucrez la ea  si aia cu reinitializarea o aveam la inceput si nu imi mergea nici testu din enunt parca... dupaia am modificat si mi-a mers deci nu-i problema de la aia... da ciudat e ca am doua rezolvari (una in N^3 si una in N^4) care iau 0 puncte

LE: Cu cealalta sursa imi da NU DA DA dar iau 0 puncte

Cod:

for (k=0;k<nr;++k){
        xx=x[k];
        //printf("%d %d %d\n",x[k].val,x[k].i,x[k].j);
if (d[ii[xx]][jj[xx]]>val[xx] && y[ii[xx]][jj[xx]]!=1 || d[ii[xx]][jj[xx]]<val[xx] && y[ii[xx]][jj[xx]]!=1){
           printf("NU\n");
           return;
        }
        if (d[ii[xx]][jj[xx]]>val[xx] && y[ii[xx]][jj[xx]]==1){
           d[ii[xx]][jj[xx]]=val[xx];
           for (a=0;a<n;++a)
               for (b=0;b<n;++b)
                      d[a][b]=min(d[a][b],min(d[a][ii[xx]] + val[xx] + d[jj[xx]][b], d[a][jj[xx]] + val[xx] + d[ii[xx]][b]));
        }
    }
    printf("DA\n");

asa fac... x este vectorul sortat iar d este matricea cu distantele. in val retin valoarea initiala in ii linia pe care se afla si in jj coloana

[•fireatmyself]

in principiu asa fac si eu. ai sortat perechile (i,j) din matricea initiala, crescator, dupa valoare?

[•toni2007]

da... nu stiu sigur daca am implementat sort din stl bine (eu lucrez in c) da cu qsort nu intra in timp... cu asta intra dar imi da incorect

[•fireatmyself]

nu stiu ce sa zic. trimite-mi sursa ca pm.

[•S7012MY]

Ma poate ajuta cineva sa-mi spuna ce gresesc aici :

Cod:

#include <cstdio>
template <class T>
class pereche {
public:
int prim,ultim;

};

void rezolva() {
    pereche <int> muchii[2500];
    int i,j,k;
    int init[51][51],rez[51][51],n,m;
    scanf("%d %d",&n ,&m );
    ///<citire muchii>
    for(i=1; i<=m; i++)
        scanf("%d %d",&muchii[i].prim,&muchii[i].ultim);
    ///</citire muchii>
    for(i=1; i<=n; i++) for(j=1; j<=n; j++) scanf("%d",&rez[i][j]);//citire matr initiala
    for(i=1; i<=m; i++) {
        init[muchii[i].prim][muchii[i].ultim] = rez[muchii[i].prim][muchii[i].ultim];
        init[muchii[i].ultim][muchii[i].prim] = rez[muchii[i].prim][muchii[i].ultim];
    }
    ///<royfloyd>
    for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (init[i][k] && init[k][j] &&
(init[i][j] > init[i][k] + init[k][j] || !init[i][j]) &&
i != j)
                    init[i][j] = init[i][k] + init[k][j];
    ///</royfloyd>
    for(i=1; i<=n; i++) for(j=1; j<=n; j++)
        if(init[i][j]!=rez[i][j]) {
            printf("NU\n"); return;
        }
    printf("DA\n");

}

int main()
{
    int t,i;
    freopen("rfinv.in","r",stdin);
    freopen("rfinv.out","w",stdout);
    scanf("%d",&t);
    for(i=0; i<t; i++)
       rezolva();
    return 0;
}

[•mathboy]

Initializeaza unde nu ai muchii in matricea init cu o valoare destul de mare (100000000), iar atunci cand faci roy-floyd fa asa :

Cod:

if (i != j && i != k && j != k)
           init[i][j] = min (init[i][j], init[i][k] + init[k][j])

Ar trebui sa mearga asa

[•S7012MY]

Nu merge 

[•mathboy]

La initializare ai grija cand i == j sa pui init [ i ] [ j ] = 0 ?

[•diehard]

Eu am rezolvat problema cu 2 foruri si 15 if-uri am luat maxim 100 de puncte. 

[•Eby7]

Imi poate explica, va rog, cineva care este motivul pentru care nu primesc punctaj pe sursa asta?

Cod:

#include<fstream>
using namespace std;
ifstream f("rfinv.in");
ofstream g("rfinv.out");
int t;
int n,m;
int a[51][51];
int b[51][51];
int i,j;
int x,y;
int ok;
int r;
int main()
{
    f>>t;
    for(int k=1;k<=t;k++)
    {
        ok=0;
        f>>n>>m;
        for(i=1;i<=n;i++)
         for(j=1;j<=n;j++)
          a[i][j]=b[i][j]=0;
        for(i=1;i<=m;i++)
        {
            f>>x>>y;
            a[x][y]=a[y][x]=1;
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                f>>r;
                b[i][j]=r;
            }
        }
        for(i=1;i<=n;i++)
         for(j=1;j<=n;j++)
          if((a[i][j]==0&&b[i][j]>0)||(a[i][j]>0&&b[i][j]==0))
              ok=1;
        if(ok==0)
          g<<"DA"<<"\n";
        else
          g<<"NU"<<"\n";
    }
    return 0;
}

[•TrascaAndrei]

Daca se mai uita cineva la problema aceasta, am si eu nevoie de ajutor. Imi merge pe ambele exemple(si cel din enunt si cel de la "fireatmyself") dar iau 0 puncte. Am incercat si metoda lui Dastas, merge pe exemple, dar tot 0 puncte iau 

Cod:

#include <iostream>
#include <stdio.h>
#define infile "rfinv.in"
#define outfile "rfinv.out"
#define N 51
#define inf 100001

using namespace std;

int c[N][N],n,m,t,a[N][N];

FILE * in=fopen(infile,"r");
FILE * out=fopen(outfile,"w");

void cit()
{
    fscanf(in,"%d %d\n",&n,&m);
    int i,j;
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
        {
            a[i][j]=a[j][i]=inf;
            c[i][j]=c[j][i]=inf;
        }
    for(i=1;i<=m;i++)
    {
        int x,y;
        fscanf(in,"%d %d",&x,&y);
        a[x][y]=a[y][x]=1;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            fscanf(in,"%d",&c[i][j]);
            if(a[i][j])
                a[i][j]=c[i][j];
        }
}

void roy_floyd()
{
    int i,j,k;
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(i!=j && j!=k && i!=k)
                    a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
}

bool sol2()
{
    int i,j,k,sw=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            sw=0;
            for(k=1;k<=n;k++)
                {
                    if(c[i][j]>c[i][k]+c[k][j])
                        return 0;
                    if(c[i][j]==c[i][k]+c[k][j])
                        sw=1;
                }
            if(!sw && a[i][j]==inf)
                return 0;
        }
    return 1;
}

inline void verif()
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(a[i][j]!=c[i][j])
            {
                fprintf(out,"NU");
                return ;
            }
    fprintf(out,"DA");
}

int main()
{
    int i;
    fscanf(in,"%d\n",&t);
    for(i=1;i<=t;i++)
    {
        cit();
        roy_floyd();
        verif();
        /*if(sol2())
            fprintf(out,"DA");
        else
            fprintf(out,"NU");*/
        fprintf(out,"\n");
    }
    return 0;
}

Sol2 este solutia lui Dastas

[•PlayLikeNeverB4]

Cod:

if(a[i][j])

Conditia nu e tot timpul adevarata?

Incearca sa eviti pe viitor conditii formulate dubios. In loc de "if (x)", pune explicit "if (x > 0)".

[•TrascaAndrei]

Salut! Multumesc de raspuns, nu imi dadusem seama ca initializasem matricea cu infinit. O sa incerc sa vad daca acum merge, dar observ ca sunt probleme la compilator momentan.

[•TrascaAndrei]

Cod:

if(a[i][j])

Conditia nu e tot timpul adevarata?

Incearca sa eviti pe viitor conditii formulate dubios. In loc de "if (x)", pune explicit "if (x > 0)".

Se pare ca tot 0 puncte iau, chiar si cu aceasta modificare. Nu pot sa imi dau seama care este problema