170 Subsir 2

[•fireatmyself]

Spunem ca un subsir B=(bi1,bi2...biN) este crescator maximal daca ai1 ≤ ai2 ≤ ... ≤ aiK si nu exista nici un x astfel incat: sa existe j < K, ij < x < ij+1 si aij ≤ ax ≤ aij+1, sau 1 ≤ x < i1 si ax ≤ ai1 sau iK < x ≤ N si aiK <= a

pentru exemplul lui wefgef:
8 6 3 9 10 3 2 5 1 3 7 5 2 8 4 10.

subsiruri crescatoare care nu sunt maximale sunt
8 6 3 9 10 3 2 5 1 3 7 5 2 8 4 10 (se mai poate extinde cu 9 si cu ultimul 10)
8 6 3 9 10 3 2 5 1 3 7 5 2 8 4 10 (se mai poate extinde cu ultimul 10)
8 6 3 9 10 3 2 5 1 3 7 5 2 8 4 10 (se mai poate extinde cu 7, 8, 10, sau cu 5, 8, 10).

daca din exemplele de mai sus consideram intr-o secventa si numerele boldite si numerele subliniate, vei avea subsiruri crescatoare maximale.

[•amadaeus]

Aha , am inteles, multumesc, dar cum ramane cu cel mai scurt subsir crescator maximal , asta ce inseamna?

Pe scurt, un subsir crescator este maximal daca nu mai poate fi extins. Trebuie sa determini cel mai scurt astfel de subsir. Un exemplu concludent este cel dat de Marius acum cateva posturi:

Cod:

subsir2.in 
12
19 17 -14 17 -6 21 19 8 -17 19 15 -22 

subsir2.out 
1
12

Aici, subsirul format de al doisprezecelea element (-22) este maximal (nu mai poate fi extins) si este cel mai scurt.

In alta ordine de idei, cred ca ar trebui modificati doi indici in restrictiile problemei, mai exact acolo unde apare B=(bi1,bi2...biN) modificat in B=(bi1,bi2...biK) 

[•wefgef]

Dintre toate subsirurile crescatoare maximale il alegi pe cel de lungime minima.

[•ciprianf]

Wow...am inteles...multumesc tuturor

LE:

tot nu-mi iese aceasta problema. m-am uitat si pe sol oficiale , am facut ca acolo si tot nu e bine...

Cod:

l[n]=1;
	for(i=n-1;i>=1;i--){
		min=l[i]=INF;
		for(j=i+1;j<=n;j++){
				if(v[j]>=v[i] && l[j]<l[i] && v[j]<min){
					l[i]=l[j];
					min=v[j];
					p[i]=j;
				}
				if(v[j]>=v[i]) 
					ok[j]=1;
		}
		if(l[i]==INF) l[i]=0;
		l[i]++;
	}
min=INF;
	for(i=1;i<=n;i++)
		if(l[i]<min && !ok[i]){
			min=l[i];
			poz=i;
		}
....

l(i) = lungimea minima a unui subsir cresc maximal care incepe de pe pozitia i
p() = poz(pt reconstituire)
ok(i) = 1 daca subsirul care incepe de pe poz i poate fi lipit cu cineva din stanga, si 0 in caz contrar.

Va puteti da seama unde am gresit? Multumesc anticipat

[•fireatmyself]

nu cred ca e buna conditia asta

Cod:

 if(v[j]>=v[i] && l[j]<l[i] && v[j]<min) 

scoate l[ j ] < l[ i ]. daca se indeplineste conditia (fara l), reactualizei min si apoi vezi daca solutia curenta iti imbunatasete solutia calculata anterior, adica:

Cod:

if (l[j]+1 < l[i]) {
l[i] = l[j]+1;
p[i] = j; }

ai grija ca in caz de egalitate reactualizezi p[ i ] cu minimul dintre val lui si j.

[•ciprianf]

Intai vreau sa nu mai iau wa, apoi vad eu cum fac cu sirul lexicografic, asta ar trebui sa-mi iasa....am modificat putin sursa dar tot nu iese

Cod:

for(i=n-1;i>=1;i--){
		min=l[i]=INF;
		for(j=i+1;j<=n;j++){
				if(v[j]>=v[i] && v[j]<min){
						l[i]=l[j];
						min=v[j];
						p[i]=j;
					}
				if(v[j]>=v[i]) 
					ok[j]=1;
		}
		if(l[i]==INF) l[i]=0;
		l[i]++;
	}

daca gasesc un v[j]<min nici nu ma mai intereseaza ce lungime are l(j),il iau automat pe ala pt ca e cel bun. Fie urmatoarele 2 cazuri:
........7 3 4 9 9 10......      - presupunem ca v(i)=7; cand caut un j minim il gases pe primul 9 care e mai lung dar e corect, apoi daca l-as lua pe al 2lea 9 il iau pe acesta in considerare , si ar veni subsirul" 7 9 10" dar este gresit pt ca poate fi extins cu primul 9.

.......7 2 3 9 11 13 9       - v(i)=7. acum e corect sa-l iau tot pe primul 9(subsirul format ar fi 7 9 9)
=> nu ma intereseaza daca gasesc un alt v(j)==min

...dupa lupte seculare tot nu mi-a iesit ...imi mai poti da niste indicii?

[•fireatmyself]

tot nu e bine. am zis ca in if-ul:

Cod:

if(v[j]>=v[i] && v[j]<min)

reactualizezi doar minimul.

trebuie sa fie ceva de genul

Cod:

if (V[j] >= V[i] && V[j] < min)
{
        min = V[j];
        if (l[i] > l[j]+1)
        {
              l[i] = l[j]+1;
              p[i] = j;
        }
}

de ce nu faci un debug pe un test care nu-ti merge. vezi la ce i nu iti da cum ar trebui.

[•ciprianf]

nu-mi iese deloc lungimea minima lexicografica

Cod:

# for(i=n-1;i>=1;i--){  
#         min=l[i]=INF;  
#         for(j=i+1;j<=n;j++){  
#                 if(v[j]>=v[i] && v[j]<min){  
#                         min=v[j];  
#                         if(l[j]+1<l[i]){  
#                             l[i]=l[j]+1;  
#                             p[i]=j;  
#                         }  
#                         else if(l[j]+1==l[i])  
#                             if(v[j]<v[p[i]])  
#                                 p[i]=j;  
#                     }  
#                 if(v[j]>=v[i])   
#                     ok[j]=1;  
#         }  
#         if(l[i]==INF) l[i]=1; 

unde gresesc?

[•wefgef]

Te-ai uitat peste articolul cu solutii?

[•ciprianf]

m-am uitat, am facut ca acolo si tot nu iese

[•wefgef]

Inseamna ca nu ai facut ca acolo

[•ciprianf]

poate am inteles eu gresit ce zice acolo....
LE: am rezolvat-o pana la urma

[•maria_d]

imi poate spune cineva la ce se refera la problema asta cu lungime minima?....eu observ ca e subsirul de lungime maxima

[•theprdv]

un subsir crescator maximal e acelasi cu cel mai scurt subsir crescator maximal? sau care e diferenta intre un subsir crescator maximal si unul cel mai scurt crescator maximal?

[•SebiSebi]

Un subsir crescator este maximal daca nu mai poti adauga elemente la el care sa pastreze invariantul de monotonie. In seventa 2 1 2 3 4, subsirul 1 3 4 nu este maximal deoarece se poate extinde la 1 2 3 4. Acum din multimea subsirurilor crescatoare maximale tu trebuie sa il gasesti pe cel de lungime minima si minim lexicografic.

[•tziplea_stefan]

Ma chinui de ceva vreme pe problema asta si am obtinut doar 99p, ca pe testul 6 solutia mea nu e minima lexicografica. Imi poate da va rog cineva un test sa ma prind ce gresesc? Aici e sursa mea: http://www.infoarena.ro/job_detail/2022631