949 Kss

[•stef2n]

Aici puteti discuta despre problema Kss.

[•girl_style]

Am incercat sa rezolv pb Kss (conform solutiei postate de voi) , dar totusi iau doar 40 pct (pe restul testelor-incorect). Imi este destul de greu sa fac debbuging in lipsa unui test pe care sa crape implementarea mea.Daca aveti niste teste mai mari (cu tot cu rezultate) v-as fi recunoscatoare.

Sursa :

Cod:

void prel(char *sir,int lu,unsigned long long k)
{
	int x;
	//sol-vectorul in care constr solutia
	//sir-sirul initial de carcatere
	//lu-lungimea sirului
	//initializari
	sol[0]=0;
	for (int i=1; i<=26; i++)
		next[i][lu+1]=0;
	for (int i=lu; i>0; i--)
	{
		x=sir[i]-'a'+1;
		next[x][i]=i;
		for (int j=1; j<x; j++)
			next[j][i]=next[j][i+1];
		for (int j=x+1; j<=26; j++)
			next[j][i]=next[j][i+1];
	}
	for (int i=lu; i>=1; i--)
	{
		din[i]=1;
		for (int j=1; j<=26; j++)
			din[i]+=din[next[j][i+1]];
	}
	//sfarsit initializari
	int p,e=1,q=1;
	//e-caracterul pe care incerc sa-l pun in solutie
	while (1)
	{
	p=next[e][q];  // p - poz de pe care incerc sa iau caracterul din sirul initial pt a-l pune in sol
	// q - pozitia (din sirul initial) imediat de dupa ultimul caracter pus in solutie
	while (din[p]<k)
	{
 		k=k-din[p];
	    e++;
		if ((e>26))
		{
			g<<-1<<endl;
			return;
		}
		p=next[e][q];
	}
	sol[0]++;//tin nr de caractere din solutie
	sol[sol[0]]='a'+e-1;
	e=1;
	k--;
	if (!k)
	{
		afis();//afiseaza solutia
		return;
	}
//	q=next[e][q];
   // q++;
	q=p+1;
	}
}

[•Mishu91]

Problema are deja un topic in arhiva de probleme. Poti posta acolo, nu are rost sa existe mai multe topicuri pentru o problema

[•sima_cotizo]

Problema are deja un topic in arhiva de probleme. Poti posta acolo, nu are rost sa existe mai multe topicuri pentru o problema

Fixed

[•Mishu91]

Am incercat sa rezolv pb Kss (conform solutiei postate de voi) , dar totusi iau doar 40 pct (pe restul testelor-incorect). Imi este destul de greu sa fac debbuging in lipsa unui test pe care sa crape implementarea mea.Daca aveti niste teste mai mari (cu tot cu rezultate) v-as fi recunoscatoare.

Sursa :

Cod:

void prel(char *sir,int lu,unsigned long long k)
{
	int x;
	//sol-vectorul in care constr solutia
	//sir-sirul initial de carcatere
	//lu-lungimea sirului
	//initializari
	sol[0]=0;
	for (int i=1; i<=26; i++)
		next[i][lu+1]=0;
	for (int i=lu; i>0; i--)
	{
		x=sir[i]-'a'+1;
		next[x][i]=i;
		for (int j=1; j<x; j++)
			next[j][i]=next[j][i+1];
		for (int j=x+1; j<=26; j++)
			next[j][i]=next[j][i+1];
	}
	for (int i=lu; i>=1; i--)
	{
		din[i]=1;
		for (int j=1; j<=26; j++)
			din[i]+=din[next[j][i+1]];
	}
	//sfarsit initializari
	int p,e=1,q=1;
	//e-caracterul pe care incerc sa-l pun in solutie
	while (1)
	{
	p=next[e][q];  // p - poz de pe care incerc sa iau caracterul din sirul initial pt a-l pune in sol
	// q - pozitia (din sirul initial) imediat de dupa ultimul caracter pus in solutie
	while (din[p]<k)
	{
 		k=k-din[p];
	    e++;
		if ((e>26))
		{
			g<<-1<<endl;
			return;
		}
		p=next[e][q];
	}
	sol[0]++;//tin nr de caractere din solutie
	sol[sol[0]]='a'+e-1;
	e=1;
	k--;
	if (!k)
	{
		afis();//afiseaza solutia
		return;
	}
//	q=next[e][q];
   // q++;
	q=p+1;
	}
}

Vezi că valorile din dinamică pot depăși limita maximă a long long-ului, prin urmare ai grijă ca aceste valori să nu devină negative.

[•girl_style]

Salut si multumesc pentru raspuns.Am gasit ca limita unsigned long long-ului este ULLONG_MAX=18446744073709551615 , asa ca de fiecare data calculez sirul astfel (si banuiesc ca este corect pt ca ULLONG_MAX>k cerut de pb),dar tot nu iau toate testele.

Cod:

for (int i=lu; i>=1; i--)
	{
		din[i]=1;
		for (int j=1; j<=26; j++)
			if ((din[i]+din[next[j][i+1]])>(ULLONG_MAX))
				din[i]=ULLONG_MAX;
			else
				din[i]=din[i]+din[next[j][i+1]];
	}

 Ma gandesc ca poate pe compilatorul folosit de voi long long-ul are o limita mai mica decat 10¹⁸.

[•Mishu91]

Daca atat din[ i ] si din[next[ j ][ i+1 ]] sunt egale cu ULLONG _MAX atunci suma lor va fi negativa, prin urmare mai mica decat acea constanta. Prin urmare pune in loc de acel ULLONG_MAX k+1 sau 2⁶¹ (eu am preferat a doua varianta).

[•OneStepCloser]

eu am o alta metoda care functioneaza pe teste mici
o sa incerc sa o explic mai jos:
de exemplu daca trebuie sa aflu a 11 a solutie din sirul abcd:

     a
     ab
     abc
     abcd
     abd
     ac
     acd
^   ad                - sfarsitul grupei 1 (2^3 termeni)
|   |b
|   |b  ^   |c
|   |b  |    |cd     -11 (daca pozitia literei in grupa curenta =2^k (in cazul multimii formata din elementul "d" k=0) => ca este ultima litera)
|   |b  |    |d       - sfarsitul grupei 2(2^2 termeni)
|    c
|    cd -etc
|    d

k=ordinul submultimii
se poate observa ca in total sunt 2^4 submultimi -1(submultimea vida) fapt ce reise din Binomul lui Newton
apoi incerc sa aflu cea mai mica putere x astfel incat 2^4 - 2^x<k pentru a afla din ce grupa de submultimi face parte prima litera
apoi intru in grupa marcata cu "|" pentru a afla urmatoarea litera si tot asa
problema este ca pe testul dat 2^k .. iese chiar si din long long iar metoda nu mai este viabila (k fiind 12345)

[•repp4radu]

Salut!

Am rezolvat problema ca si in solutia oficiala, O(Sigma * N) pt fiecare test, insa iau TLE pe 6 teste.

Ce as mai putea optimiza, avand in vedere ca TLE-urile obtinute nu sunt de la complexitate?

[•a_h1926]

Ceau!
Eu m-am folosit de niste sume partiale. Practic, atunci cand calculezi DP, in loc sa adun DP-ul corespunzator urmatorului caracter pentru fiecare caracter in parte, tin minte o variabila Sum in care retin acea valoare. Dupa ce am calculat DP (printr-o simpla atribuire), variabila Sum se modifica, pentru ca scad DP-ul caracterului curent care era adunat la Sum de dinainte, si adun DP-ul curent. Astfel, numarul de calcule efectuate se injumatateste.
Sper sa te ajute!

[•repp4radu]

Salut!

Am scos 100 pana la urma. Pe langa problema mentionata de tine, mai aveam si un if in care intram de prea multe ori (testam pt fiecare caracter, desi era doar o singura posibilitate => 25 de teste facute aiurea pt fiecare element al sirului).

[•Ionut228]

Imi poate explica si mie cineva de ce daca declar o matrice A[30][1000] iau TLE, iar daca singura modificare facuta e sa declar matricea invers, adica A[1000][30] timpul de executie scade foarte mult?

[•klamathix]

Poți găsi detalii aici la pontul #3.

[•Ionut228]

Ok, multumesc pentru raspuns.