826 Project management

[•DITzoneC]

Aici puteţi discuta despre problema Project management.

[•pauldb]

Acum ar trebui sa se poate submita si la aceasta problema.

[•vlad.manea]

Am trimis o solutie si nu primesc niciun raspuns pentru primul test (obtin 90p).
Alti concurenti primesc un raspuns ("a doua valoare gresita") la unele teste gresite.
Sunt cazuri in care evaluatorul nu trimite inapoi raspuns?

[•gabitzish1]

S-a rezolvat. Imi cer scuze pentru neplacere!

[•mihaionly]

Și la această problemă, și la cerc3 de la oji2009 îmi dă "Killed by signal 11(SIGSEGV)." pe toate testele, deși când le evaluez manual după testele de la oji, nu apare nicio problemă. Nu depășesc limitele niciunui vector

[•savim]

Poti sa primesti acest mesaj si daca declari prea multa memorie.

[•Florian]

Și la această problemă, și la cerc3 de la oji2009 îmi dă "Killed by signal 11(SIGSEGV)." pe toate testele, deși când le evaluez manual după testele de la oji, nu apare nicio problemă. Nu depășesc limitele niciunui vector

Ai grija la numele fisierelor .in si .out.  Am asa o vaga banuiala ca aici gresesti 

[•alexandru92]

Mai intai La multi ani
Nu inteleg unde gresesc in calcularea celei de a 2 valori. Folosesc CPM. Pe exemplu din enunt, la ultima valoare afiseaza 8 8 in loc de 8 9

Cod:

for( i=n-1; i >= 0; --i )
    {minim=inf; 
        for( it=vt[order[i]].begin(), iend=vt[order[i]].end(); it < iend; ++it )
            minim=min( minim, lt[*it]-cost[order[i]] );
        if( minim != inf )
          lt[order[i]]=minim;
    }

order - se gasesc nodurile 0, 1, ...,n-1 sortate topologic
vt - retin lista de adiacenta a grafului transpus
cost - timpul necesar indeplinirii fazei i
lt  - timpul maxim la care poate incepe faza i.
Daca ma puti ajuta, va rog

[•toni2007]

Mai intai La multi ani
Nu inteleg unde gresesc in calcularea celei de a 2 valori. Folosesc CMP. Pe exemplu din enunt, la ultima valoare afiseaza 8 8 in loc de 8 9

Cod:

for( i=n-1; i >= 0; --i )
    {minim=inf; 
        for( it=vt[order[i]].begin(), iend=vt[order[i]].end(); it < iend; ++it )
            minim=min( minim, lt[*it]-cost[order[i]] );
        if( minim != inf )
          lt[order[i]]=minim;
    }

order - se gasesc nodurile 0, 1, ...,n-1 sortate topologic
vt - retin lista de adiacenta a grafului transpus
cost - timpul necesar indeplinirii fazei i
lt  - timpul maxim la care poate incepe faza i.
Daca ma puti ajuta, va rog

Ce este CMP ?

[•alexandru92]

Scuze era CPM Critical Path Method.
LE: Am rezolvat, n-am tratat cazul in care procesul i nu are succesori

[•AndreiD]

Cred ca este o eroare in evaluator, afisez corect doar timpul minim si iau 79 puncte, in loc de 40 puncte.

[•stef2n]

Am reparat. Acum vei lua 46 de puncte, nu 40 (testul 1 e mai special )

[•Alexa_ioana_14]

ca sa aflu timpul minim la care poate fi inceput un proiect fac un fellman-ford in care initial toate distantele sunt -1, si incerc la fiecare pas sa obtin pentru un nod costul maxim (nu minim).
pe ideea asta iau 88 pct. E gresita ideea, sau am busit la implementare? [n-am gasit niciun contraexeplu, iar sursa pare ok]

[•andrei.sfrent]

S-ar putea ca implementarea sa fie de vina. Si eu tot Bellman Ford am folosit.

[•Alexa_ioana_14]

da, era de la sursa, multumesc !


O mica observatie in ceea ce priveste evaluatorul: evalul spunea ca e gresita a 2-a valoare insa bugul era la cea de-a 3-a!

[•wscsprint3r]

Imi spune si mie cineva unul din testele (inafara de primu) de la ceasta problema va rog? Pe exemplu merge dar iau 29 de puncte

[•Andreid91]

Sunt aceleasi teste ca si la oji din cate stiu eu. Le gasesti in sectiunea downloads aici http://infoarena.ro/downloads

Spor 

[•shnako]

Am folosit Critical Path si iau 82 de puncte. Ideea e ca pe 6 teste nu imi da bine a doua valoare. Asta este partea care afla a doua valoare, daca reuseste cineva sa se prinda ce am gresit fac o bere ca pe mine deja ma termina psihic chestia asta.
Sper ca nu e prea explicit, pentru ca nu poti lua puncte doar cu bucata asta.

Cod:

void critical_path(void)
{
	t=0;
	for (i=1;i<=n;i++)
		check[i]=0;
	for (i=1;i<=n;i++)
	{
		sw=0;
		for (j=1;j<=n;j++)
			if (m[j][i])
			{
				sw=1;
				break;
			}
		if (!sw)
		{
			check2[i]=1;
			check[i]=1;
			st[++t]=i;
			v[i].tfmax=cost;
			v[i].tsmax=v[i].tfmax-v[i].c;
		}
	}
	
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			if (m[st[i]][j]&&!check2[j])
			{	
				st[++t]=j;
				check2[j]=1;
			}

	
	for (i=1;i<=n;i++)
	{
		sw=0;
		for (j=1;j<=n;j++)
			if ((m[j][st[i]]&&!check[j])||check[st[i]])
			{
				sw=1;
				break;
			}
		if (!sw)
		{
			min=MARE;
			for (j=1;j<=n;j++)
				if (m[j][st[i]]&&v[j].tsmax<min)
					min=v[j].tsmax;
			v[st[i]].tfmax=min;
			v[st[i]].tsmax=v[st[i]].tfmax-v[st[i]].c;
			check[st[i]]=1;
		}
	}
}

[•alexandru92]

Inainte de a aplica Critical Min Path ai facut  o sortare topologica ?

[•DanceKriss]

Poate sa-mi dea cineva un link cu critical path .... iau 44 de pct cu o metoda implementata de mine ...... 
p.s : SE POT LUA 100 DE PCT SI  CU MATRICE DE3 ADIACENTA? :>
 

[•gabitzish1]

Sigur ca se poate ... sunt maxim 100 de noduri.

[•DanceKriss]

merci   Ideea e ca pe matrice faci parcurgerea mai ushor

[•gapdan]

Imi explica si mie cineva va rog ce este Critical Path Method?