Episodio IV: tracce di DNA 65/100

Aiuto
1

Ho provato ha risolvere questo problema, tuttavia il massimo che sono riuscito ad ottenere è 65, sono consapevole del che cosa non mi fa prendere 100, ma non riesco a sistemarlo.
Spiego qua cosa fa il mio algoritmo perché non ho commenti nel testo che lo fanno.
Parto da una stringa vuota, e man mano faccio un test della stringa aggiungendo un 1 alla fine se esce true allora la stringa diventa quella che era prima + con alla fine un 1, se esce false alla fine ci metto uno 0, dopo 16 volte che aggiungo 0 alla stringa controllo se ho raggiunto la fine (alla stringa manca molto probabilmente ancora la prima parte), se davvero sono presenti 16 zeri, allora continua azzerando il conteggio degli errori, in caso contrario si è raggiunta la fine, allora per trovare il modo in cui finisce la stringa uso una specie di binary search (ho già controllato i finali …1, …01, …001 ecc… fino a 15 zeri e un 1) tolgo gli ultimi 16 caratteri e parto dalla metà precisa e faccio un test aggiungendo 8 zeri, se esce true allora passo a 12 se esce false passo a 4 fino a che non trovo il finale corretto, poi da qui uso la stessa tecnica ma al contrario, cioè aggiungendo i caratteri all’inizio della stringa, (test aggiungendo 1 alla fine se è corretto lo aggiungo se non lo è aggiungo 0) finché non raggiungo N. In più se il numero è maggiore di 9950 faccio 1/2 test per provare a guadagnare qualche tentativo (non serve considerato che nel caso peggiore il mio test fa circa 10400 tentativi e guadagnarne 8 è troppo poco, ma l’ho scritto pensando di puntare al 100). Se la stringa fosse generata randomicamente il mio algoritmo funzionerebbe 99,999…% delle volte
Mi servirebbe una mano / un consiglio su come andare avanti.

Ecco il codice con il grader d’esempio:

#include <bits/stdc++.h>

using namespace std;

static string secret;
static size_t cnt;
typedef vector<string>::iterator it;

bool test(string qry) {
    cnt += 1;
    return secret.find(qry) != string::npos;
}

string analizza(int N){
	string dna="";
	int l=0;
	if(N>9950) {
		if(test("0000000000")){
			dna="0000000000";
			l=10;
		}
		else if (test("1111111111")){
			dna="1111111111";
			l=10;
		}
	}
	bool keep = true;
	while(keep){
		int wrongC=0;
		while (l<N&&wrongC<16){
			/*if(wrongC>0&&wrongC%5==0){
				if (test(dna+'0')){
					dna.push_back('0');
					l++;
					wrongC=0;
				}
				else {
					dna.push_back('1');
					l++;
					wrongC++;
				}
			}*/
			if (test(dna+'1')) {
				dna.push_back('1');
				l++;
				wrongC=0;
			}
			else {
				dna.push_back('0');
				l++;
				wrongC++;
			}
			//cout<<dna<<" "<<l<<endl;
		}
		if(wrongC==	16&&test(dna))continue;
		//cout<<l<<" "<<wrongC<<endl<<dna<<endl;
		if(test(dna))break;
		if(wrongC!=0){
			l-=wrongC;
			dna.erase(l,wrongC);
			//cout<<dna<<" "<<l<<endl;
			int cur=wrongC/2,range=wrongC/2;
			if(wrongC%2!=0){
				cur++;
				range++;
			}
			keep = true;
			if(test(dna+'0')==false) keep=false;
			//cout<<cur<<" "<<range<<" "<<l<<" "<<keep<<endl;
			//cout<<"Binary:"<<endl;
			while (keep){
				dna.insert(l,cur,'0');
				//cout<<cur<<" "<<range<<" "<<l<<endl;
				//cout<<dna<<" "<<l<<endl;
				if (test(dna)){
					if (range>1){
						dna.erase(l,cur);
						if(range%2!=0)range++;
						range/=2;
						cur+=range;
					}
					else {
						keep=false;
						l+=cur;
					}
				}
				else {
					dna.erase(l,cur);
					if(range%2!=0)range++;
					range/=2;
					cur-=range;
				}
				//cout<<dna<<" "<<l<<endl;
			}
			//cout<<cur<<" "<<range<<" "<<l<<" "<<keep<<endl;
		}
		//cout<<dna<<" "<<l<<endl;
	}
	while (l<N){
		if(test('1'+dna)){
			dna.insert(0,"1");
			l++;
		}
		else {
			dna.insert(0,"0");
			l++;
		}
		//cout<<dna<<endl;
	}
	//cout<<dna<<endl;
	return dna;
}

int main() {
    cin.exceptions(ios::failbit | ios::badbit);

    // se preferisci leggere e scrivere da file ti basta decommentare le seguenti due righe:
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    cin >> secret;

    cnt = 0;
    string ans = analizza(secret.size());

    if (ans == secret) {
        cout << "Risposta corretta!\n" << cnt << " chiamate a test." << endl;
    } else {
        cout << "Risposta sbagliata!" << endl;
    }

    return 0;
}

poi ho provato a scrivere un altro algoritmo basandomi su quello sopra per provare a prendere 100, ma fallisce su alcuni casi e non riesco proprio a capire il perché, allego solo il codice senza spiegarlo poiché il ragionamento è molto contorto. Non serve che qualcuno mi dia una mano su questo codice, ma magari se qualcuno ha voglia ho trova un input per il quale non funziona, gliene sarei grato:

#include <bits/stdc++.h>
using namespace std;

bool test(string T);

string analizza(int N){
	string dna="";
	int l=0;
	if(N>9950) {
		if(test("0000000000")){
			dna="0000000000";
			l=10;
		}
		else if (test("1111111111")){
			dna="1111111111";
			l=10;
		}
	}
	bool keep = true;
	while(keep){
		int wrongC=0;
		bool pos[]={false,false,false};
		while (l<N&&wrongC<16){
			if(wrongC>0&&wrongC%5==0){
				if (test(dna+'0')){
					dna.push_back('0');
					l++;
					wrongC=0;
					pos[0]=false;pos[1]=false;pos[2]=false;
				}
				else {
					dna.push_back('1');
					l++;
					wrongC++;
					pos[wrongC/5-1]=true;
				}
			}
			else if (test(dna+'1')) {
				dna.push_back('1');
				l++;
				wrongC=0;
				pos[0]=false;pos[1]=false;pos[2]=false;
			}
			else {
				dna.push_back('0');
				l++;
				wrongC++;
			}
			//cout<<dna<<" "<<l<<" "<<wrongC<<endl;
		}
		if(wrongC==	16&&test(dna))continue;
		//cout<<wrongC<<" pos: "<<pos[0]<<" "<<pos[1]<<" "<<pos[2]<<endl<<dna<<" "<<l<<endl;
		if(test(dna))break;
		if(wrongC!=0){
			l-=wrongC;
			dna.erase(l,wrongC);
			//cout<<dna<<" "<<l<<endl;
			int cur=wrongC/2,range=wrongC/2;
			if(wrongC%2!=0){
				cur++;
				range++;
			}
			keep = true;
			if(test(dna+'0')==false) keep=false;
			//cout<<cur<<" "<<range<<" "<<l<<" "<<keep<<endl;
			//cout<<"Binary:"<<endl;
			while (keep){
				if(pos[0]||pos[1]||pos[2]){
					int tem=0;
					if(pos[0]&&cur>5){
						dna.insert(l,5,'0');
						dna.push_back('1');
						tem+=6;
					}
					if(pos[1]&&cur>10){
						dna.insert(l+tem,4,'0');
						dna.push_back('1');
						tem+=5;
					}
					if(pos[2]&&cur>15){
						dna.insert(l+tem,4,'0');
						dna.push_back('1');
						tem+=5;
					}
					if ((cur-1)%5!=0) dna.insert(l+tem,(cur-1)%5,'0');
				}
				else dna.insert(l,cur,'0');
				//cout<<cur<<" "<<range<<" "<<l<<endl;
				//cout<<dna<<" "<<l<<endl;
				if (test(dna)){
					if (range>1){
						dna.erase(l,cur);
						if(range%2!=0)range++;
						range/=2;
						cur+=range;
					}
					else {
						keep=false;
						l+=cur;
					}
				}
				else {
					dna.erase(l,cur);
					if(range%2!=0)range++;
					range/=2;
					cur-=range;
				}
				//cout<<dna<<" "<<l<<endl;
			}
			//cout<<cur<<" "<<range<<" "<<l<<" "<<keep<<endl;
		}
		//cout<<dna<<" "<<l<<endl;
	}
	while (l<N){
		if(test('1'+dna)){
			dna.insert(0,"1");
			l++;
		}
		else {
			dna.insert(0,"0");
			l++;
		}
		//cout<<dna<<endl;
	}
	//cout<<dna<<endl;
	return dna;
}
2

La soluzione da 100/100 è più complicata, però puoi fare ancora qualche punto usando la strategia da 65/100.
L’idea è questa:

Quando scegli di controllare se la string è valida dopo 16 presunti zeri stai scegliendo un valore arbitrario. C’è un valore ottimale che minimizza le chiamate alla funzione test.
Soluzione:

Chiama x il numero di presunti zeri dopo il quale controlli. Fai sicuramente una chiamata a test() per carattere, inoltre fino a:
N/x chiamate per controllare se ci sono davvero x zeri consecutivi;
x chiamate che restituiscono false “oltre la fine della stringa” prima di accorgerti che quegli zeri non ci sono davvero;
log(x) chiamate per fare la binary search degli zeri alla fine.
a questo punto devi minimizzare N/x+x+log(x).

Ecco alcuni input che il secondo programma sbaglia:
001000
00000011100110111010011010001101101000110011111110
01100100100000000101001001110000101111100011110010

1 Mi Piace
3

non capisco cosa voglia dire questo, e cosa centri N/x perché dovrebbe dipendere dalla lunghezza della stringa, in ogni caso non so trovare il minimo di una funzione ora (non ho ancora studiato quell’argomento, magari dopo me lo vado a studiare).

grazie agli input che mi hai dato ho sistemato il codice del secondo programma, ma nonostante abbia preso 100/100 in più casi rispetto a prima il punteggio generale resta 65 anche per quello.

altra domanda: per prendere 100/100 c’è bisogno di conoscere qualche tecnica algoritmica o qualche argomento di matematica specifici, o si può risolvere anche con conoscenze scarse?

4

Per fare 100/100 non servono conoscenze specifiche, ma il ragionamento è un po’ contorto.
Perché fai fino a N/x chiamate:
immagina di avere una stringa fatta da 10000 zeri.
Il tuo metodo ogni 16 chiamate controlla se la stringa contiene davvero tutti quegli zeri o se in realtà è finita alcuni caratteri prima.

Quindi il programma fa 10000/16 = 625 chiamate ‘extra’ a test().

Come trovare il minimo della funzione: chiedi a Wolfram Alpha. x = sqrt(N)

1 Mi Piace
5

ok ho capito grazie, in questo modo dovrei riuscire nel caso peggiore ad arrivare a poco più di 10200 chiamate (per usare Wolfram Alpha ho dovuto sostituire N con 10000 altrimenti non mi trovava la formula, ma in ogni caso è il caso peggiore che mi interessa quindi va bene così).

Ultima domanda sempre riguardo l’algoritmo per prendere 100/100, anche se non so quanto puoi aiutarmi / consigliarmi senza dirmi la soluzione: questo algoritmo è completamente diverso da quello che avevo pensato io? Immagino che ci sia una chiamata per carattere più pochissime chiamate “extra” per capire quando si arriva alla fine/inizio (probabilmente è qua la differenza nei 2 algoritmi) ma farlo in meno di 15 chiamate mi sembra impossibile, so che hai detto che non c’è niente da sapere per risolverlo, ma magari c’è qualche argomento che posso andare a studiare per poterlo risolvere? Perché se proprio non c’è niente che io possa fare per capirlo meglio allora è probabile che non lo risolverò mai.
In ogni caso grazie dell’attenzione e dell’aiuto che mi hai dato.

edit: mi ero ricordato di una cosa che volevo provare ad aggiungere, cioè creare un’array di una grandezza limitata tipo 10 o 100 e aggiungere li le prime stringhe che restituivano false e prima di chiamare la funzione test controllare se nella stringa ci fosse presente già una di quelle nell’array. Dubito però che questo serva a qualcosa, perché aiuta solo nei casi in cui la lunghezza massima di ‘0’ o di ‘1’ non superi i 7/8 caratteri

6

La soluzione non è difficile da implementare e non richiede strutture dati particolari, è solo molto difficile da trovare.
Alcuni hint:
Puoi evitare di controllare ogni 100 zeri se la sequenza esiste davvero, e invece limitarti a capire quando è per forza finita?
Puoi usare l’informazione ricavata dallo step sopra per iniziare il processo già con una stringa che è per forza nella sequenza?
Il metodo sopra dà un ottimo punteggio, ma non fa ancora 100.

E per fare 100…
Sinceramente mi sono appena accorto che la mia soluzione da 100 lamera e in locale riesco a fare testcse che richiedono 10100 test, che non è da 100.
Eppure la soluzione che ho implementato dovrebbe essere quella ufficiale che hanno spiegato alle finali a biella. Quindi bho, apro un altro thread e ti faccio sapere.

1 Mi Piace
7

grazie mille per l’aiuto, ci penserò un po’ su in questi giorni