Jump to content

ONI 2012 - Qualificação - B - Código Genético

Warrior

By Warrior
in Concursos de Programação

 Share

Recommended Posts

  • Replies 44
  • Created
  • Last Reply

Top Posters In This Topic

Top Posters In This Topic

xtrm0 boolean user

xtrm0

Posted
Posted

Fiz um algoritmo que nao sei o nome. Este passa por ir guardando sempre as melhores subsequencias encontradas. E depois vendo quantas das sequencias contem essa subsequencia. Acho que da tambem para os 100p.

B(100%):

#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct seqr{
int ap[200][100];
int na[200];
};
vector <seqr> seq;
vector <seqr> nseq;
vector <string> dnas;
int K;

int main() {
    string tmp;
int N, sa;
seqr s1;
cin >> N >> K;

for (int i=0; i<N; i++) {
	cin >> tmp;
	dnas.push_back(tmp);
}


for (int i=0; i<N; i++) {
	s1.na[i]=0;
	for (int j=0; unsigned(j)<dnas[i].size(); j++) {
		if (dnas[i][j]=='A') {
			s1.ap[i][s1.na[i]]=j;
			s1.na[i]++;
		}
	}
}
sa=0;
for (int i=0; i<N; i++) {
	if(s1.na[i]>0) sa++;
}
if (sa>=K) {
	seq.push_back(s1);
}

for (int i=0; i<N; i++) {
	s1.na[i]=0;
	for (int j=0; unsigned(j)<dnas[i].size(); j++) {
		if (dnas[i][j]=='T') {
			s1.ap[i][s1.na[i]]=j;
			s1.na[i]++;
		}
	}
}
sa=0;
for (int i=0; i<N; i++) {
	if(s1.na[i]>0) sa++;
}
if (sa>=K) {
	seq.push_back(s1);
}

for (int i=0; i<N; i++) {
	s1.na[i]=0;
	for (int j=0; unsigned(j)<dnas[i].size(); j++) {
		if (dnas[i][j]=='G') {
			s1.ap[i][s1.na[i]]=j;
			s1.na[i]++;
		}
	}
}
sa=0;
for (int i=0; i<N; i++) {
	if(s1.na[i]>0) sa++;
}
if (sa>=K) {
	seq.push_back(s1);
}

for (int i=0; i<N; i++) {
	s1.na[i]=0;
	for (int j=0; unsigned(j)<dnas[i].size(); j++) {
		if (dnas[i][j]=='C') {
			s1.ap[i][s1.na[i]]=j;
			s1.na[i]++;
		}
	}
}
sa=0;
for (int i=0; i<N; i++) {
	if(s1.na[i]>0) sa++;
}
if (sa>=K) {
	seq.push_back(s1);
}

int tamanho=0;
while(!(seq.empty())) {
	tamanho++;
	nseq.clear();
	for (int l=0; unsigned(l)<seq.size(); l++){
		for (int i=0; i<N; i++) {
			s1.na[i]=0;
			for (int j=0; j<seq[l].na[i]; j++) {
				if (dnas[i][seq[l].ap[i][j]+tamanho]=='A') {
					s1.ap[i][s1.na[i]]=seq[l].ap[i][j];
					s1.na[i]++;
				}
			}
		}
		sa=0;
		for (int i=0; i<N; i++) {
			if(s1.na[i]>0) sa++;
		}
		if (sa>=K) {
			nseq.push_back(s1);
		}
	}

	for (int l=0; unsigned(l)<seq.size(); l++){
		for (int i=0; i<N; i++) {
			s1.na[i]=0;
			for (int j=0; j<seq[l].na[i]; j++) {
				if (dnas[i][seq[l].ap[i][j]+tamanho]=='C') {
					s1.ap[i][s1.na[i]]=seq[l].ap[i][j];
					s1.na[i]++;
				}
			}
		}
		sa=0;
		for (int i=0; i<N; i++) {
			if(s1.na[i]>0) sa++;
		}
		if (sa>=K) {
			nseq.push_back(s1);
		}
	}


	for (int l=0; unsigned(l)<seq.size(); l++){
		for (int i=0; i<N; i++) {
			s1.na[i]=0;
			for (int j=0; j<seq[l].na[i]; j++) {
				if (dnas[i][seq[l].ap[i][j]+tamanho]=='T') {
					s1.ap[i][s1.na[i]]=seq[l].ap[i][j];
					s1.na[i]++;
				}
			}
		}
		sa=0;
		for (int i=0; i<N; i++) {
			if(s1.na[i]>0) sa++;
		}
		if (sa>=K) {
			nseq.push_back(s1);
		}
	}


	for (int l=0; unsigned(l)<seq.size(); l++){
		for (int i=0; i<N; i++) {
			s1.na[i]=0;
			for (int j=0; j<seq[l].na[i]; j++) {
				if (dnas[i][seq[l].ap[i][j]+tamanho]=='G') {
					s1.ap[i][s1.na[i]]=seq[l].ap[i][j];
					s1.na[i]++;
				}
			}
		}
		sa=0;
		for (int i=0; i<N; i++) {
			if(s1.na[i]>0) sa++;
		}
		if (sa>=K) {
			nseq.push_back(s1);
		}
	}
	seq = nseq;
}
cout << tamanho << endl;
}

<Signature goes here>

gangsterveggies void

gangsterveggies

Posted
Posted

Fiz um algoritmo que nao sei o nome. Este passa por ir guardando sempre as melhores subsequencias encontradas. E depois vendo quantas das sequencias contem essa subsequencia. Acho que da tambem para os 100p.

B(100%):

#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct seqr{
int ap[200][100];
int na[200];
};
vector <seqr> seq;
vector <seqr> nseq;
vector <string> dnas;
int K;

int main() {
    string tmp;
int N, sa;
seqr s1;
cin >> N >> K;

for (int i=0; i<N; i++) {
	cin >> tmp;
	dnas.push_back(tmp);
}


for (int i=0; i<N; i++) {
	s1.na[i]=0;
	for (int j=0; unsigned(j)<dnas[i].size(); j++) {
		if (dnas[i][j]=='A') {
			s1.ap[i][s1.na[i]]=j;
			s1.na[i]++;
		}
	}
}
sa=0;
for (int i=0; i<N; i++) {
	if(s1.na[i]>0) sa++;
}
if (sa>=K) {
	seq.push_back(s1);
}

for (int i=0; i<N; i++) {
	s1.na[i]=0;
	for (int j=0; unsigned(j)<dnas[i].size(); j++) {
		if (dnas[i][j]=='T') {
			s1.ap[i][s1.na[i]]=j;
			s1.na[i]++;
		}
	}
}
sa=0;
for (int i=0; i<N; i++) {
	if(s1.na[i]>0) sa++;
}
if (sa>=K) {
	seq.push_back(s1);
}

for (int i=0; i<N; i++) {
	s1.na[i]=0;
	for (int j=0; unsigned(j)<dnas[i].size(); j++) {
		if (dnas[i][j]=='G') {
			s1.ap[i][s1.na[i]]=j;
			s1.na[i]++;
		}
	}
}
sa=0;
for (int i=0; i<N; i++) {
	if(s1.na[i]>0) sa++;
}
if (sa>=K) {
	seq.push_back(s1);
}

for (int i=0; i<N; i++) {
	s1.na[i]=0;
	for (int j=0; unsigned(j)<dnas[i].size(); j++) {
		if (dnas[i][j]=='C') {
			s1.ap[i][s1.na[i]]=j;
			s1.na[i]++;
		}
	}
}
sa=0;
for (int i=0; i<N; i++) {
	if(s1.na[i]>0) sa++;
}
if (sa>=K) {
	seq.push_back(s1);
}

int tamanho=0;
while(!(seq.empty())) {
	tamanho++;
	nseq.clear();
	for (int l=0; unsigned(l)<seq.size(); l++){
		for (int i=0; i<N; i++) {
			s1.na[i]=0;
			for (int j=0; j<seq[l].na[i]; j++) {
				if (dnas[i][seq[l].ap[i][j]+tamanho]=='A') {
					s1.ap[i][s1.na[i]]=seq[l].ap[i][j];
					s1.na[i]++;
				}
			}
		}
		sa=0;
		for (int i=0; i<N; i++) {
			if(s1.na[i]>0) sa++;
		}
		if (sa>=K) {
			nseq.push_back(s1);
		}
	}

	for (int l=0; unsigned(l)<seq.size(); l++){
		for (int i=0; i<N; i++) {
			s1.na[i]=0;
			for (int j=0; j<seq[l].na[i]; j++) {
				if (dnas[i][seq[l].ap[i][j]+tamanho]=='C') {
					s1.ap[i][s1.na[i]]=seq[l].ap[i][j];
					s1.na[i]++;
				}
			}
		}
		sa=0;
		for (int i=0; i<N; i++) {
			if(s1.na[i]>0) sa++;
		}
		if (sa>=K) {
			nseq.push_back(s1);
		}
	}


	for (int l=0; unsigned(l)<seq.size(); l++){
		for (int i=0; i<N; i++) {
			s1.na[i]=0;
			for (int j=0; j<seq[l].na[i]; j++) {
				if (dnas[i][seq[l].ap[i][j]+tamanho]=='T') {
					s1.ap[i][s1.na[i]]=seq[l].ap[i][j];
					s1.na[i]++;
				}
			}
		}
		sa=0;
		for (int i=0; i<N; i++) {
			if(s1.na[i]>0) sa++;
		}
		if (sa>=K) {
			nseq.push_back(s1);
		}
	}


	for (int l=0; unsigned(l)<seq.size(); l++){
		for (int i=0; i<N; i++) {
			s1.na[i]=0;
			for (int j=0; j<seq[l].na[i]; j++) {
				if (dnas[i][seq[l].ap[i][j]+tamanho]=='G') {
					s1.ap[i][s1.na[i]]=seq[l].ap[i][j];
					s1.na[i]++;
				}
			}
		}
		sa=0;
		for (int i=0; i<N; i++) {
			if(s1.na[i]>0) sa++;
		}
		if (sa>=K) {
			nseq.push_back(s1);
		}
	}
	seq = nseq;
}
cout << tamanho << endl;
}

Não sei se passa. Depende. A tua solução é excelente quando a resposta é pequena, por exemplo de tamanho  entre 1 e 10. Mas se forem 100 strings de tamanho 100 e k = 1 ficas com Stack Overflow e não passa no tempo. Dependendo dos testes tens ou não 100. Mas duvido.

Experimenta ver isto: http://en.wikipedia.org/wiki/Suffix_tree

--

GangsterVeggies - DCC/FCUP

Localhost boolean user

Localhost

Posted
Posted

Pedro, codaste uma suffix tree..? Por acaso eu li este problema de relance e também pensei nisso porque já houve uma altura em que li sobre suffix trees e vi lá uma aplicação delas que era mesmo isto. Mostra o teu código 😄

here since 2009

gangsterveggies void

gangsterveggies

Posted
Posted

Oh que fofinho kkkk  😄

Ahah. Por acaso achei este problema "parecido" com o B do ano passado. Não que a solução fosse semelhante, mas envolvia Strings e uma Data Structure engraçada (tries no ano passado). Na realidade todos os problemas me lembraram dos do ano passado  😄 1 Ad-Hoc simples; 1 Strings e 1 DP...

--

GangsterVeggies - DCC/FCUP

scorch try-catch user

scorch

Posted
Posted

Bem, eu tentei usar uma coisa parecida com suffix tries, e o resultado é que funcionou (pelo menos testei com vários inputs e funcionou) mas o código não é muito aconselhável a pessoas sensíveis.

A verdade é que nunca tinha ouvido falar de suffix tries, e implementar uma solução funcional à primeira vez acho que é bom. Anyway, a lógica está lá. 😄

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

struct trie {
trie *subtries[4];
char count;
int lastSequence;
};

trie *mainTrie;

int biggestSize = -1;
int numCadeias;
int minCadeias;

int getHash(char caractere){
if (caractere == 'A'){
	return(0);
} else if (caractere == 'G'){
	return(1);
} else if (caractere == 'C'){
	return(2);
} else if (caractere == 'T'){
	return(3);
} else {
	return(-1);
}
}

trie* createSub(){
trie *newTrie;
newTrie = (trie *)malloc((sizeof(trie)));
newTrie->subtries[0] = NULL;
newTrie->subtries[1] = NULL;
newTrie->subtries[2] = NULL;
newTrie->subtries[3] = NULL;
newTrie->count = NULL;
newTrie->lastSequence = -1;

return(newTrie);
}

void inserirSequencia(char texto[], int sequence){
int i = 0, i2 = 0;
trie *parent;
char newText[100];

for (i = 0; i < strlen(texto); i++){
	parent = mainTrie;
	for (i2 = i; i2 < strlen(texto); i2++){
		if (parent->subtries[getHash(texto[i2])] == NULL){
			parent->subtries[getHash(texto[i2])] = createSub();
		}
		parent = parent->subtries[getHash(texto[i2])];

		if (parent->lastSequence < sequence){
			parent->count += 1;

			if ((i2 - i + 1 > biggestSize || biggestSize == -1) && parent->count >= minCadeias){
				biggestSize = i2 - i + 1;
			}

			parent->lastSequence = sequence;
		}
	}
}
}

int main(){

int i;

mainTrie = createSub();


char cadeias[100];

scanf("%d %d", &numCadeias, &minCadeias);

for (i = 0; i < numCadeias; i++){
	scanf("%s", cadeias);

	inserirSequencia(cadeias, i);
}

printf("%d\n", biggestSize);
return(0);
}

O meu maior problema era verificar o fim das tries (tentei com o NULL, mas deu-me cá uma dor de cabeça). Por fim, acabei por inicializar tudo a null ao criar cada nó. 😄

PS: Não respondo a perguntas por mensagem que podem ser respondidas no fórum.

gangsterveggies void

gangsterveggies

Posted
Posted

Bem, eu tentei usar uma coisa parecida com suffix tries, e o resultado é que funcionou (pelo menos testei com vários inputs e funcionou) mas o código não é muito aconselhável a pessoas sensíveis.

A verdade é que nunca tinha ouvido falar de suffix tries, e implementar uma solução funcional à primeira vez acho que é bom. Anyway, a lógica está lá. 😄

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

struct trie {
trie *subtries[4];
char count;
int lastSequence;
};

trie *mainTrie;

int biggestSize = -1;
int numCadeias;
int minCadeias;

int getHash(char caractere){
if (caractere == 'A'){
	return(0);
} else if (caractere == 'G'){
	return(1);
} else if (caractere == 'C'){
	return(2);
} else if (caractere == 'T'){
	return(3);
} else {
	return(-1);
}
}

trie* createSub(){
trie *newTrie;
newTrie = (trie *)malloc((sizeof(trie)));
newTrie->subtries[0] = NULL;
newTrie->subtries[1] = NULL;
newTrie->subtries[2] = NULL;
newTrie->subtries[3] = NULL;
newTrie->count = NULL;
newTrie->lastSequence = -1;

return(newTrie);
}

void inserirSequencia(char texto[], int sequence){
int i = 0, i2 = 0;
trie *parent;
char newText[100];

for (i = 0; i < strlen(texto); i++){
	parent = mainTrie;
	for (i2 = i; i2 < strlen(texto); i2++){
		if (parent->subtries[getHash(texto[i2])] == NULL){
			parent->subtries[getHash(texto[i2])] = createSub();
		}
		parent = parent->subtries[getHash(texto[i2])];

		if (parent->lastSequence < sequence){
			parent->count += 1;

			if ((i2 - i + 1 > biggestSize || biggestSize == -1) && parent->count >= minCadeias){
				biggestSize = i2 - i + 1;
			}

			parent->lastSequence = sequence;
		}
	}
}
}

int main(){

int i;

mainTrie = createSub();


char cadeias[100];

scanf("%d %d", &numCadeias, &minCadeias);

for (i = 0; i < numCadeias; i++){
	scanf("%s", cadeias);

	inserirSequencia(cadeias, i);
}

printf("%d\n", biggestSize);
return(0);
}

O meu maior problema era verificar o fim das tries (tentei com o NULL, mas deu-me cá uma dor de cabeça). Por fim, acabei por inicializar tudo a null ao criar cada nó. 🙂

Achei a tua solução estranha mas reparei em duas coisas...

1. char cadeias[100]; As Strings podiam ser até 100 caracteres, logo não cabe ai  😄

2. Testei com alguns casos meus e o teu código dá -1 de vez em quando. Confesso que não o analisei ao pormenor, por isso não sei que erro possas ter, mas achei estranho teres usado tries. Não vi soluções com isso...

--

GangsterVeggies - DCC/FCUP

Warrior try-catch user

Warrior

Posted
  • Author
Posted

O problema das Suffix Trees é que a implementação simples (como a do scorch) é O(N^2). Neste problema era propositadamente suficiente O(N^2), até porque era um problema de qualificação e seria exagerado pedir mais do que isto. Mas implementar Suffix Trees mais rápido pode ser importante e dá uma trabalheira dos diabos, especialmente os suffix links..

Quando o Pedro me enviou o problema resolvi com um Suffix Array, que é bastante mais simples de implementar em O(N*logN), embora ache que não permite exactamente todas as aplicações que se encontram numa suffix tree.

http://en.wikipedia.org/wiki/Suffix_array

http://apps.topcoder.com/forums/?module=Thread&threadID=627379&start=0&mc=16 (explicação detalhada de como implementar)

http://www.spoj.pl/problems/SUBST1/ (problema no SPOJ para testarem Suffix Trees/Suffix Arrays)

scorch try-catch user

scorch

Posted
Posted

1. char cadeias[100]; As Strings podiam ser até 100 caracteres, logo não cabe ai  😄

Oh sh*t. É no que dá não treinar mais em C.  ?

2. Testei com alguns casos meus e o teu código dá -1 de vez em quando. Confesso que não o analisei ao pormenor, por isso não sei que erro possas ter, mas achei estranho teres usado tries. Não vi soluções com isso...

A solução com suffix tries passava por fazer catalogar todas as subsequências possíveis, por exemplo para ATTGAA:

A

AT

ATT

(etc...)

E depois:

T

TT

TTG

E depois

T

TG

TGA

Mas como não me bastava ter as terminações mas também podiam existir tries com subsequências no meio das palavras, cada nó tinha um contador que contava em quantas cadeias aquela subsequência constava. Espero que pelo menos isso funcione. Agora fiquei mesmo desconcertado com esse problema dos 100 caracteres (o que um pequeno problema pode fazer ?). 😞

Quando o Pedro me enviou o problema resolvi com um Suffix Array, que é bastante mais simples de implementar em O(N*logN), embora ache que não permite exactamente todas as aplicações que se encontram numa suffix tree.

Não conhecia os suffix arrays, vou dar uma vista de olhos.

@gangsterveggies Podias-me dar um exemplo de input onde te calha -1? É que agora gostava de saber onde errei. 😄

PS: Não respondo a perguntas por mensagem que podem ser respondidas no fórum.

gangsterveggies void

gangsterveggies

Posted
Posted

Oh sh*t. É no que dá não treinar mais em C.  ?

A solução com suffix tries passava por fazer catalogar todas as subsequências possíveis, por exemplo para ATTGAA:

A

AT

ATT

(etc...)

E depois:

T

TT

TTG

E depois

T

TG

TGA

Mas como não me bastava ter as terminações mas também podiam existir tries com subsequências no meio das palavras, cada nó tinha um contador que contava em quantas cadeias aquela subsequência constava. Espero que pelo menos isso funcione. Agora fiquei mesmo desconcertado com esse problema dos 100 caracteres (o que um pequeno problema pode fazer ?). 😞

Não conhecia os suffix arrays, vou dar uma vista de olhos.

@gangsterveggies Podias-me dar um exemplo de input onde te calha -1? É que agora gostava de saber onde errei. 🙂

Quanto às subsequências no meio de tries, se implementasses bem, bastavam as terminações.

O meu exemplo é bastante grande, com 100 strings... Tenta gerar com C ou assim. Pessoalmente uso Python para gerar.

O problema das Suffix Trees é que a implementação simples (como a do scorch) é O(N^2). Neste problema era propositadamente suficiente O(N^2), até porque era um problema de qualificação e seria exagerado pedir mais do que isto. Mas implementar Suffix Trees mais rápido pode ser importante e dá uma trabalheira dos diabos, especialmente os suffix links..

Quando o Pedro me enviou o problema resolvi com um Suffix Array, que é bastante mais simples de implementar em O(N*logN), embora ache que não permite exactamente todas as aplicações que se encontram numa suffix tree.

http://en.wikipedia.org/wiki/Suffix_array

http://apps.topcoder.com/forums/?module=Thread&threadID=627379&start=0&mc=16 (explicação detalhada de como implementar)

http://www.spoj.pl/problems/SUBST1/ (problema no SPOJ para testarem Suffix Trees/Suffix Arrays)

Eu conhecia as Suffix Arrays, mas conhecia melhor as Suffix Trees e decidi arriscar nestas. Espero que passem no tempo, porque o meu worst case corria em menos de 1 segundo por pouco...

--

GangsterVeggies - DCC/FCUP

skiller10 void

skiller10

Posted
Posted

Este problema é praticamente igual a este do UVA:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2048

Foi o que me deu mais trabalho porque andei muito cansado/ocupado estes dias com outras actividades. Construi uma suffix trie a poucas horas do fim, usei construção O(N^2) embora tenha lido sobre construção em O(N) assim como construir suffix arrays mas como não percebi algumas coisas acabei por não arriscar e manter o O(N^2) que pelos testes que fiz (casos "estranhos" e casos extremos) devo ter 100p.

"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.."

djthyrax try-catch user

djthyrax

Posted
Posted

Este não tenho grande ideia como o resolvia para mais do que 50, para os 50 tentaria fazer uma comparação simples elemento a elemento ou algo do género.

Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!

skiller10 void

skiller10

Posted
Posted

Para 50 bastava pegar em cada substring e ver quantas strings aparecia 😄 (Foi a minha primeira solução)

"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.."

Joao brandao void

Joao brandao

Posted
Posted

Este foi sem duvida aquele problema que passei 1 dia inteiro a olhar para ele e a tentar criar a melhor soluçao possivel.. para ser sincero acho que fiz por volta de 3/4 programas so para este e havia sempre um pequeno erro que falhava me infelizmente.. Detesto strings mas tenho que admitir que algumas funçoes de strings ajudaram muito neste problema.

Fiz para os 100 pontos, agora n sei é se isto vai aguentar com os casos mais longos :-S

#include <vector>
#include <string>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

int main()
{
int qts, c_qts, t_maior, casas;
vector <string> txts;
string txt_maior,aux;
cin>>qts>>c_qts;
bool cont;
txt_maior ="";
t_maior=0;
casas=1;
int count=0;
//Leitura
for (int i =0 ; i<qts; i++){
    cin>>txt_maior;
    txts.push_back(txt_maior);
}
//Programa
if (!(c_qts>1)){
for (int i =0 ; i<qts; i++){
if ((int)t_maior<(int)txts[i].length()){
t_maior=(int)txts[i].length();
txt_maior=txts[i];
}
}
}else
for (int x = 0; x<=(int)(txts[0].length()-casas); x++){
cont=true;
//enquanto existirem mais substrings a comecar pela letra x
while(cont){
count++;
//verifica que ainda pode fazer substring
if ((int)txts[0].length()>=(int)(x+casas))
aux = txts[0].substr(x,casas);
else cont=false;
//para cada palavra vai ver se a substring esta presente
for (int j = 1 ; j<c_qts;j++){
if (!(txts[j].find(aux)>=0 && txts[j].find(aux)<txts[j].length())){
cont=false;
}
}
//se existir adiciona a nova substring como maior e o numero de casas dela
if (cont){
txt_maior=aux;
t_maior=casas;
casas++;
}
}
}
//Resultado
cout<<t_maior<<endl;
return 0;
}
gangsterveggies void

gangsterveggies

Posted
Posted

Este foi sem duvida aquele problema que passei 1 dia inteiro a olhar para ele e a tentar criar a melhor soluçao possivel.. para ser sincero acho que fiz por volta de 3/4 programas so para este e havia sempre um pequeno erro que falhava me infelizmente.. Detesto strings mas tenho que admitir que algumas funçoes de strings ajudaram muito neste problema.

Fiz para os 100 pontos, agora n sei é se isto vai aguentar com os casos mais longos :-S

#include <vector>
#include <string>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

int main()
{
int qts, c_qts, t_maior, casas;
vector <string> txts;
string txt_maior,aux;
cin>>qts>>c_qts;
bool cont;
txt_maior ="";
t_maior=0;
casas=1;
int count=0;
//Leitura
for (int i =0 ; i<qts; i++){
    cin>>txt_maior;
    txts.push_back(txt_maior);
}
//Programa
if (!(c_qts>1)){
for (int i =0 ; i<qts; i++){
if ((int)t_maior<(int)txts[i].length()){
t_maior=(int)txts[i].length();
txt_maior=txts[i];
}
}
}else
for (int x = 0; x<=(int)(txts[0].length()-casas); x++){
cont=true;
//enquanto existirem mais substrings a comecar pela letra x
while(cont){
count++;
//verifica que ainda pode fazer substring
if ((int)txts[0].length()>=(int)(x+casas))
aux = txts[0].substr(x,casas);
else cont=false;
//para cada palavra vai ver se a substring esta presente
for (int j = 1 ; j<c_qts;j++){
if (!(txts[j].find(aux)>=0 && txts[j].find(aux)<txts[j].length())){
cont=false;
}
}
//se existir adiciona a nova substring como maior e o numero de casas dela
if (cont){
txt_maior=aux;
t_maior=casas;
casas++;
}
}
}
//Resultado
cout<<t_maior<<endl;
return 0;
}

O teu código em termos de tempo, se não me engano, dá para 100 ou perto disso.

O problema é que não está certo. Só testas com as substrings da primeira string, enquanto a maior substring pode ser entre outras. Testei inclusive com alguns casos que inventei de cabeça e confirma-se...

--

GangsterVeggies - DCC/FCUP

gangsterveggies void

gangsterveggies

Posted
Posted

que erro grave da minha parte :-S deveria ter visto isso quando tava a testar  e a rever o codigo  para melhoria :-S é a minha mania de querer fazer tudo depressa e depois da nisto :-S

Pois... nas qualificações das ONI é sempre prudente gerar casos de teste. Muitos! Tens os pontos de todas os casos onde as substrings começam na primeira. Mas como se não me engano fizeste o A e o C, pelo menos o Bruto, acho que passas na mesma.

--

GangsterVeggies - DCC/FCUP

brunoalves5 void

brunoalves5

Posted
Posted

O meu B nao foi feito para 100 pts longe disso xD, fiz com brute force mas como os limites sao pequenos penso q apesar da complexidade da para chegar aos 50pts ou perto disso:

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

int main()
{
    char tmp[102],cod[202][102];
    int n,nm,j,i,v[202][102],k,jj,l,s,max,p,mmax;
    scanf("%d%d",&n,&nm);
    for (i=1;i<=n;i++)
    {
        scanf("%s",cod[i]);
    }
    for (i=1;i<n;i++)
    {
        for (j=i+1;j<=n;j++)
        {
            if (strlen(cod[j])>strlen(cod[i]))
            {
                                            strcpy(tmp,cod[i]);
                                            strcpy(cod[i],cod[j]);
                                            strcpy(cod[j],tmp);
            }
        }
    }
    for (i=1;i<=n;i++)
    {
        for (j=0;j<strlen(cod[i]);j++)
        {
            switch(cod[i][j])
            {
                             case 'A' : 
                             {
                                  v[i][j+1]=1;
                                  break;
                             }
                             case 'G' : 
                             {
                                  v[i][j+1]=2;
                                  break;
                             }
                             case 'C' : 
                             {
                                  v[i][j+1]=3;
                                  break;
                             }
                             case 'T' : 
                             {
                                  v[i][j+1]=4;
                                  break;
                             }
            }
        }
    }
    if (nm==1)
    {
              mmax=strlen(cod[1]);
    }else
    {
         mmax=1;
         s=1;
         for (p=1;p<=n-nm+1;p++)
         {
             for (l=1;l<strlen(cod[1]);l++)
             {
                 max=1;
                 for (i=p+1;i<=n;i++)
                 {
                     for (j=1;j<=strlen(cod[i])-s;j++)
                     {
                         k=0;
                         for (jj=0;jj<=s;jj++)
                         {
                             if (v[i][j+jj]!=v[p][l+jj])
                             {
                                                    k=1;
                                                    break;
                             }
                         }
                         if (k==0)
                         {
                              max++;
                              break;
                         }
                     }
                     if (max==nm)
                     {
                        mmax++;
                        s++;
                        l--;
                        break;
                     }
                 }
             }
         }
    }
    printf("%d\n",mmax);
    system("pause");
  return 0;
}

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
 Share
Go to topic listing
×
×
  • 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.