Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 685 Pluricex  (Citit de 5756 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
DITzoneC
Nu mai tace
*****

Karma: 301
Deconectat Deconectat

Mesaje: 962



Vezi Profilul
« : Aprilie 01, 2008, 11:39:50 »

Aici puteţi discuta despre problema Pluricex.
« Ultima modificare: Aprilie 01, 2008, 14:02:51 de către Andrei Grigorean » Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #1 : Aprilie 01, 2008, 17:12:10 »

Sfatu meu e sa mai taiati un pic din limita de memorie si de timp. Macar memoria sa fie ca la oji Think
Memorat
DITzoneC
Nu mai tace
*****

Karma: 301
Deconectat Deconectat

Mesaje: 962



Vezi Profilul
« Răspunde #2 : Aprilie 01, 2008, 21:06:36 »

Am micsorat limitele de timp si memorie. Am reevaluat sursele.
Memorat
jupanu92
Client obisnuit
**

Karma: -86
Deconectat Deconectat

Mesaje: 76



Vezi Profilul
« Răspunde #3 : Aprilie 02, 2008, 13:53:12 »

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 .. 
« Ultima modificare: Aprilie 02, 2008, 14:15:24 de către Popescu Marius » Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #4 : Aprilie 02, 2008, 14:03:24 »

Se vede ca ai micsorat dar acu nu mai iau 100 iau doar 80 .... nush cum ...
Inseamna ca nu faci optim
Memorat
jupanu92
Client obisnuit
**

Karma: -86
Deconectat Deconectat

Mesaje: 76



Vezi Profilul
« Răspunde #5 : Aprilie 02, 2008, 14:21:31 »

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 .
« Ultima modificare: Mai 02, 2008, 21:06:37 de către Popescu Marius » Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #6 : Aprilie 02, 2008, 14:33:35 »

Io mi-am generat toate combinarile de n luate cate k si am verificat daca respectiva configuratie e solutie. Deci complexitatea O(Ckn * k)
Memorat
vlad_oltean
Strain
*

Karma: 2
Deconectat Deconectat

Mesaje: 25



Vezi Profilul
« Răspunde #7 : Aprilie 02, 2008, 17:16:00 »

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? Eh?
« Ultima modificare: Aprilie 02, 2008, 17:59:00 de către Vladimir Oltean » Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #8 : Aprilie 02, 2008, 17:34:17 »

backu de generare a combinarilor e facut optim?
Memorat
vlad_oltean
Strain
*

Karma: 2
Deconectat Deconectat

Mesaje: 25



Vezi Profilul
« Răspunde #9 : Aprilie 02, 2008, 18:13:17 »

eu cred ca e optim...
Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #10 : Aprilie 02, 2008, 18:34:29 »

Io am facut generare de combinari si verificare de aceeasi complexitate ca si a ta si am luat suta Smile
Memorat
zalman
Strain
*

Karma: -11
Deconectat Deconectat

Mesaje: 31



Vezi Profilul
« Răspunde #11 : Mai 28, 2008, 07:39:58 »

imi puteti da si mie un test mai mare?
 Very Happy
Memorat
toni2007
Nu mai tace
*****

Karma: 160
Deconectat Deconectat

Mesaje: 663



Vezi Profilul
« Răspunde #12 : Mai 28, 2008, 13:11:02 »

Ia-le pe cele de la OJI (erau si teste mai mari, cu N 20)
« Ultima modificare: Martie 13, 2009, 13:47:07 de către Pripoae Teodor Anton » Memorat
mordred
Client obisnuit
**

Karma: -39
Deconectat Deconectat

Mesaje: 51



Vezi Profilul
« Răspunde #13 : Martie 13, 2009, 12:34:00 »

i-ale = fail
Memorat
alexdmotoc
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #14 : Ianuarie 04, 2012, 17:38:21 »

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
Memorat
informatician28
Strain
*

Karma: 6
Deconectat Deconectat

Mesaje: 27



Vezi Profilul
« Răspunde #15 : Ianuarie 23, 2012, 19:16:11 »

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

Karma: -4
Deconectat Deconectat

Mesaje: 38



Vezi Profilul
« Răspunde #16 : Mai 28, 2012, 16:28:10 »

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;
}
Memorat
darkseeker
De-al casei
***

Karma: 29
Deconectat Deconectat

Mesaje: 106



Vezi Profilul
« Răspunde #17 : Mai 28, 2012, 17:39:42 »

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 .
« Ultima modificare: Mai 28, 2012, 17:53:38 de către Boaca Cosmin » Memorat
Andrei.Xwe
Strain
*

Karma: -4
Deconectat Deconectat

Mesaje: 38



Vezi Profilul
« Răspunde #18 : Mai 29, 2012, 08:19:29 »

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 Winner 1st place
Multumesc mult!
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines