Jump to content
Sign in to follow this  
skiller10

USACO - Healthy Holstein

Recommended Posts

skiller10

Heys,

Ontem voltei ao usaco e resolvi três problemas da secção 2.1, comecei a fazer o healthy hostein, primeiro comecei com um set completo com todas e ia separando em subsets, só que não passou no tempo no teste #8 acho, resolvi então fazer um dfs a começar num subset só com um elemento e ir juntando novas comidas até as vitaminas serem suficientes, mas também não passou no tempo, resolvi então fazer um bfs só que deu-me o seguinte erro:

Compiling...

Compile: OK

Executing...

  Test 1: TEST OK [0.000 secs, 3036 KB]

  Test 2: TEST OK [0.000 secs, 3036 KB]

  Test 3: TEST OK [0.000 secs, 3036 KB]

  Test 4: TEST OK [0.000 secs, 3036 KB]

  Test 5: TEST OK [0.000 secs, 3036 KB]

  > Run 6: Execution error: Your program had this runtime error: Bad

        syscall #32000175 (RT_SIGPROCMASK) [email kolstad if you think

        this is wrong]. The program ran for 0.027 CPU seconds before the

        error. It used 14376 KB of memory.

        ------ Data for Run 6 ------

        5

        163 221 146 425 509

        10

        98 69 68 18 129

        132 185 196 64 176

        40 70 57 9 115

        73 189 145 87 117

        45 114 45 0 18

        137 137 174 73 178

        48 143 33 142 192

        33 107 148 2 158

        32 42 153 90 41

        165 81 156 7 121

        ----------------------------

          Your program printed data to stderr.  Here is the data:

          -------------------

          terminate_called_after_throwing_an_instance_of_'std::bad_alloc'

          __what():__std::bad_alloc

          -------------------

    Test 6: SIGNAL 50 (0.027 secs, 14376 KB)

Isto significa MLE? se sim qual seria a melhor ideia para resolver este problema, deixo aqui o meu código e o link do problema:

http://ace.delos.com/usacoprob2?a=kI2XAQkrpbC&S=holstein

Será que se eu gerar todas as permutações de comida e fizer os respectivos testes às vitaminas que passa no tempo?

/*
ID: joao_m-1
LANG: C++
TASK: holstein
*/
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <fstream>
#include <assert.h>
#define MAX 100
using namespace std;

struct DDR{
    int indice;
    int vits[MAX];
};

struct GOING{
    vector <DDR> set;
    bool usados[MAX];
    int actualvit[MAX];
};

    int nVits, nFoods, vitamins[MAX];
    vector <DDR> sols;
    vector <DDR> foods;
    DDR states;
    GOING aux;

bool checkup(int actualvit[MAX]){
    for(int i=0; i<nVits; i++)
        if(actualvit[i] < vitamins[i])
            return false;
    return true;
}

void subsets(vector <GOING> inicial, int count){
        vector <GOING> novo;

    if(count > nFoods)
        return;

    for(int i=0; i<inicial.size(); i++){
        //Verificar se as vitamitas do subset sao suficientes:
        if(checkup(inicial[i].actualvit)){
            sols = inicial[i].set;
            return;
        }

        //Dividir o subset em todos possiveis:
        for(int j=0; j<nFoods; j++){
            if(inicial[i].usados[j] == false){
                aux = inicial[i];
                aux.usados[j] = true;
                aux.set.push_back(foods[j]);
                for(int k=0; k<nVits; k++)
                    aux.actualvit[k] += foods[j].vits[k];
                novo.push_back(aux);
            }
        }
    }

    subsets(novo, count+1);
    return;
}

int main(void){
        ifstream fin("holstein.in");
        ofstream fout("holstein.out");
        assert(fin!=NULL && fout!=NULL);
        vector <GOING> inicial;
        vector <DDR> prim;

    //Input dos dados;
    fin >> nVits;
    for(int i=0; i<nVits; i++)
        fin >> vitamins[i];
    fin >> nFoods;
    for(int i=0; i<nFoods; i++){
        for(int j=0; j<nVits; j++){
            fin >> states.vits[j];
        }
        states.indice = i + 1;
        foods.push_back(states);
    }

    //Inicializar comidas já usadas:
    for(int i=0; i<MAX; i++)
        aux.usados[i] = false;

    //Iniciar pesquisas em subsets:
    for(int i=0; i<foods.size(); i++){
        prim.clear();
        prim.push_back(foods[i]);
        aux.set = prim;
        aux.usados[i] = true;
        for(int j=0; j<nVits; j++)
            aux.actualvit[j] = foods[i].vits[j];
        inicial.push_back(aux);
        aux.usados[i] = false;
    }
    subsets(inicial, 1);

    //Imprimir solução:
    fout << sols.size();
    for(int i=0; i<sols.size(); i++)
        fout << " " << sols[i].indice;
    fout << endl;

    return 0;
}


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
Warrior

DFS funcionaria, embora haja um truque de implementação que simplifica bastante o problema. Uma espécie de atalho que tira partido do facto de só existirem 15 vitaminas.

Share this post


Link to post
Share on other sites
skiller10

Podes explicar esse truque, 15 tipos de vitaminas ou 15 tipos de comida? Já agora se poderes ir aparecendo do IRC para debatermos algumas ideias e isso :P

Será que se eu em vez de ir guardando a comida, meter so a true as que estou a usar, e depois no fim fazer o checkup a ver se chega passa no tempo? vou tentar implementar...


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
mogers

O erro deve estar relacionado com o exceder da stack, usada na recursividade.

O truque é uma das utilizações do texto do 1.5 sobre números binários. Podes ver tb http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
skiller10

Pelo que percebi basicamente temos um inteiro com, representado em binário, e vamos interando sobre o mesmo desde o set completo, e a cada iteração retiramos um elemento do set através da operação:

i = (i - 1) & superset

E geramos todas as possibilidades, e para cada uma delas, vamos testar se tem os requerimentos necessários. Só não percebi muit bem foi como usar inteiros como binário :s Dá para me dares uma breve explicação disso sff?

A nível de implementação deverá ser algo semelhante a isto não?

/*
ID: joao_m-1
LANG: C++
TASK: holstein
*/
#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <assert.h>
#include <climits>
#define MAXVIT 25
#define MAXFOOD 15
using namespace std;

    int nVits, nFoods, minisol = INT_MAX;
    int vitamins[MAXVIT];
    int foods[MAXFOOD][MAXVIT];
    bool sols[MAXFOOD];

bool checkup(int actualvit[MAXVIT]){
    for(int i=0; i<nVits; i++)
        if(actualvit[i] < vitamins[i])
            return false;
    return true;
}

void subsets(bool used[MAXFOOD], int actualvit[MAXVIT], int count){
        int novovit[MAXVIT];

    if(checkup(actualvit)){
        if(count < minisol){
            minisol = count;
            for(int i=0; i<nFoods; i++)
                sols[i] = used[i];
        }
        return;
    }

    if(count == nFoods)
        return;

    for(int i=0; i<nFoods; i++){
        if(!used[i]){
            used[i] = true;
            for(int j=0; j<nVits; j++)
                novovit[j] = actualvit[j] + foods[i][j];
            subsets(used, novovit, count+1);
            used[i] = false;
        }
    }

    return;
}

int main(void){
        ifstream fin("holstein.in");
        ofstream fout("holstein.out");
        assert(fin!=NULL && fout!=NULL);
        bool usados[MAXFOOD];
        int actualvit[MAXVIT];

    fin >> nVits;
    for(int i=0; i<nVits; i++)
        fin >> vitamins[i];
    fin >> nFoods;
    for(int i=0; i<nFoods; i++)
        for(int j=0; j<nVits; j++)
            fin >> foods[i][j];

    for(int i=0; i<nFoods; i++)
        usados[i] = false;
    for(int i=0; i<nFoods; i++){
        usados[i] = true;
        for(int j=0; j<nVits; j++)
            actualvit[j] = foods[i][j];
        subsets(usados, actualvit, 1);
        usados[i] = false;
    }

    fout << minisol;
    for(int i=0; i<nFoods; i++)
        if(sols[i])
            fout << " " << i+1;
    fout << endl;

    return 0;
}


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
Localhost

Curiosamente, na altura, a minha solução com dfs passou. Submeti novamente e passou na mesma. Não li o teu código mas já vi ali muita complicação...


here since 2009

Share this post


Link to post
Share on other sites
gangsterveggies

Eu acho que o teu erro está em passares um vector como argumento de função. Quando o fazes estás a passar uma cópia do vector, ou seja, gastas n iterações (sendo n o número de elementos do vector) sempre que o passas como argumento.

Se quiseres ler mais sobre isso vê isto: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary#vector.

A minha sugestão:

void subsets(const vector<int>& inicial, int count) {
    // Coisas
}

Isto para o primeiro exemplo. Há algum erro no segundo?


--

GangsterVeggies - DCC/FCUP

Share this post


Link to post
Share on other sites
mogers

i = (i - 1) & superset

isso é outra coisa. para gerar todos os 2^n sets fazes algo tipo

for ( mask = 0 ;  mask  < (1<<n) ; mask ++)
    ...
    for (j = 0 ; j < n ; j++)
           if ( mask & (1<<j) )
                 // conjunto com máscara de bits Mask contém o elemento J


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
skiller10

Tentei como disseste Pedro mas não resultou.

Localhost, complicação em quê? se poderes dar umas dicas de como melhorar :D

Já consegui:

Executing...

  Test 1: TEST OK [0.000 secs, 3028 KB]

  Test 2: TEST OK [0.000 secs, 3028 KB]

  Test 3: TEST OK [0.000 secs, 3028 KB]

  Test 4: TEST OK [0.000 secs, 3028 KB]

  Test 5: TEST OK [0.000 secs, 3028 KB]

  Test 6: TEST OK [0.000 secs, 3028 KB]

  Test 7: TEST OK [0.000 secs, 3028 KB]

  Test 8: TEST OK [0.000 secs, 3028 KB]

  Test 9: TEST OK [0.000 secs, 3028 KB]

  Test 10: TEST OK [0.000 secs, 3028 KB]

All tests OK.

No entanto se quiserem dar algumas dicas são sempre bem-vindas.

Agora vou ter formação, assim que tiver tempo vou voltar a fazer o exercicio, mas usando o metodo que o mogers falou :)


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
Localhost

Estava mesmo a referir-me à primeira solução que mostraste.

Já agora (visto que já resolveste o problema) deixo aqui a minha solução.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAXTYPES 30
#define MAXFEEDS 20
#define SIZE 50

int v,g,out = INT_MAX;
int req[MAXTYPES],vitamins[MAXFEEDS][MAXTYPES],used[size],set[size],state[size],final[size];

void input() {
int k=0,i=0;
FILE *fin=freopen("holstein.in","r",stdin);
scanf("%i", &v);
for(k=0;k<v;k++) scanf("%i",&req[k]);
scanf("%i", &g);
for(k=0;k<g;k++) {
	for(i=0;i<v;i++) scanf("%i",&vitamins[k][i]);
}
}

int ok() {
int k=0;
for(k=0;k<v;k++) {
	if(state[k]<req[k]) return 0;
}
return 1;
}

void change(int end) {
int k=0;
for(k=0;k<end;k++) final[k]=set[k];
}

void give(int feed) {
int k=0;
for(k=0;k<v+1;k++) state[k]+=vitamins[feed][k];
}

void take_from(int feed) {
int k=0;
for(k=0;k<v+1;k++) {
	if(state[k] >= vitamins[feed][k]) state[k]-=vitamins[feed][k];
}
}

void dfs(int feed, int d, int i) {
int k=0;
if(ok()) {
	if(d<out) {
		change(i);
		out=d;
	}
	return;
}
for(k=0;k<g;k++) {
	if(used[k] || k<feed) continue;
	give(k);
	used[k]=1;
	set[i]=k+1;
	dfs(k,d+1,i+1);
	take_from(k);
	used[k]=0;
	set[i]=0;
}
}

int main(void) {
int k=0;
FILE *fout=freopen("holstein.out","w",stdout);
input();
for(k=0;k<g;k++) {
	give(k);
	used[k]=1;
	set[0]=k+1;
	dfs(k,1,1);
	take_from(k);
	used[k]=0;
	set[0]=0;
}
printf("%i %i",out,final[0]);
for(k=1;k<out;k++) {
	if(k==11) putchar('\n');
	else putchar(' ');
	printf("%i",final[k]);
}
putchar('\n');
return 0;
}

p.s. Não ligues à indentação, etc.


here since 2009

Share this post


Link to post
Share on other sites
mogers

usando bits, seria algo do genero

#define two(n)		( 1 << (n) )
#define contain(Set,i)  ( (Set) & two(i) )
using namespace std;

int main() {
freopen( "holstein.in", "r" , stdin  );
freopen( "holstein.out", "w" , stdout  );

int i,j,k, soma, nbest = 10000 , bestMask , n , req[25] , feed[15][25] , V , G;
cin >> V;
for (i=0; i<V; i++)
	cin >> req[i];
cin >> G;
for (i=0; i<G; i++)
	for (j = 0; j<V; j++)
		cin >> feed[i][j];

for (i = 1 ; i < two(G) ; i++) {   // tenta todos as combinações possíveis 2^G  (0 não interessa neste caso)
	bool ok = true;
	for (j = 0 ; j < V && ok ; j++) {
		soma = n = 0;
		for (k = 0 ; k < G ; k++)
			if (contain( i , k )) {
				n++;
				soma += feed[k][j];
			}
		ok = soma >= req[j];
	}
	if (ok && n < nbest)  {
		nbest = n;
		bestMask = i;
	}
}
cout << nbest;
for (i=0; i< G ; i++)
	if (contain(bestMask, i))
		cout << " " << i+1;
cout << endl;
return 0;
}


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.