685 Pluricex

[•DITzoneC]

Aici puteţi discuta despre problema Pluricex.

[•Mishu91]

Sfatu meu e sa mai taiati un pic din limita de memorie si de timp. Macar memoria sa fie ca la oji

[•DITzoneC]

Am micsorat limitele de timp si memorie. Am reevaluat sursele.

[•jupanu92]

Eu cred ca totusi limita de timp este cam mica ... sursa mea obtine doar 80 de p .... la fel ca si sursa oficiala .. cred ca ar trebui totusi sa maritii la 0.2 limita de timp .. 

[•Mishu91]

Se vede ca ai micsorat dar acu nu mai iau 100 iau doar 80 .... nush cum ...

Inseamna ca nu faci optim

[•jupanu92]

Cum as putea face mai optim de atat daca pana si sursa oficiala de la oji ia 80 de p ....

LA : am facuto pana la urama de 100 cu combinari .

[•Mishu91]

Io mi-am generat toate combinarile de n luate cate k si am verificat daca respectiva configuratie e solutie. Deci complexitatea O(C^k_n * k)

[•vlad_oltean]

Eu am asemenea functie de verificare

Cod:

//vectorul elev[23] reprezinta stiva, apar[23] reprezinta aparitiile disciplinelor in cadrul unei combinari
//matricea stie[23][10] ia valoarea 1 daca elevul i stie disciplina j si 0 altfel

inline int bun()
{   int i,j;

    for(i=0;i<k;i++)
        for(j=1;j<=d;j++)
            if(stie[elev[i]][j]) apar[j]++;
    for(i=1;i<=d;i++)
	{   if(!apar[i])
		{	for(j=i;j<=d;j++) apar[j]=0; //reinitializez pentru combinarea urmatoare
			return 0;
		}
		apar[i]=0;
	}
    return 1;
}

void back(int x)
{
     if(k==x)
     {   if(bun())
	     {   for(int i=0;i<k;i++) printf("%d ",elev[i]);
	         printf("\n");
	     }
     }
     else
         for(int i=elev[x-1]+1;i<=n;i++)
         {   elev[x]=i;
             back(x+1);
         }
}

totusi nu obtin decat 80 de puncte... ce anume sa optimizez?

[•Mishu91]

backu de generare a combinarilor e facut optim?

[•vlad_oltean]

eu cred ca e optim...

[•Mishu91]

Io am facut generare de combinari si verificare de aceeasi complexitate ca si a ta si am luat suta

[•zalman]

imi puteti da si mie un test mai mare?
 

[•toni2007]

Ia-le pe cele de la OJI (erau si teste mai mari, cu N 20)

[•mordred]

i-ale = fail

[•alexdmotoc]

Cred ca este prea mica limita de timp... Nu vad cum ar intra o sursa cu back in 0.05 sec... A mea nu intra

[•informatician28]

Mie imi intra destul de bine in timp cu un backtracking aproape "normal", pot sa zic!  . Iau 90 pct cu TLE totusi pe un test.
Inca nu-mi dau seama unde as mai putea optimiza...

[•Andrei.Xwe]

Am facut un back recursiv cu care am luat initial 70, apoi l-am optimizat pana la 80 si nu stiu ce sa-i mai fac.Am luat sursa oficiala si am trimis-o, dar a luat doar 70.Cred ca ar trebui scazuta limita de timp, dar am vazut ca unii au reusit sa ia suta.Imi puteti spune si mie ce optimizari sa mai fac?(am incercat si sa schimb cititrea, dar degeaba...tot 80):

Cod:

#include<fstream>
using namespace std;
#include<stdio.h>
FILE  *fcin=fopen("pluricex.in","r");
FILE  *fcout=fopen("pluricex.out","w");
int n,s[23],k,u=1,d,m[23][11];
void read()
{
	fscanf(fcin,"%d %d %d",&n,&k,&d);
	int x,y;
	for(int i=1;i<=n;i++)
	{
		fscanf(fcin,"\n%d ",&x);
		for(int j=1;j<=x;j++)
		{
			fscanf(fcin,"%d ",&y);
			m[i][y]=1;
		}
	}	
}
bool bun()
{
	int j;
	for(int i=1;i<=d;i++)
	{
		for(j=1;j<=k;j++)
			if(m[s[j]][i])
				break;
		if(j==k+1)
			return 0;
	}
	return 1;
}
void print()
{
	for(int i=1;i<=k;i++)
		fprintf(fcout,"%d ",s[i]);
	fprintf(fcout,"\n");
}
bool cont(int x)
{
	for(int i=1;i<x;i++)
		if(s[i]==s[x])
			return 0;
	return 1;
}
void back(int x)
{
	if(x==k+1){
		if(bun())
			print();}
	else
		for(int i=u;i<=n;i++)
		{
			s[x]=i;
			u=i;
			if(cont(x))
				back(x+1);
		}
}
int main()
{
	read();
	back(1);
	return 0;
}

[•darkseeker]

O prima optimizare a codului tau ar fi renuntarea la functia cont si la variabila u, in for-ul din back punand in loc de

Cod:

 for ( i = u; i <= n; i++ ) 

acest cod

Cod:

 for ( i = s[x - 1] + 1; i <= n ; i++) 

.
De asemenea poti consulta si http://infoarena.ro/problema/combinari .

[•Andrei.Xwe]

Da, stiam de problema cu combinarile, dar m-a ajutat ideea ta, am luat 90 in prima faza, apoi 100, schimband din nou citirea si scrierea
Multumesc mult!