infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: ditzone din Ianuarie 21, 2006, 17:05:59


Titlul: 170 Subsir 2
Scris de: ditzone din Ianuarie 21, 2006, 17:05:59
Aici puteţi discuta despre problema Subsir 2 (http://infoarena.ro/problema/subsir2).

Titlul: 170 Subsir 2
Scris de: Andrei Grigorean din Ianuarie 21, 2006, 22:28:06
care e complexitatea oficiala la problema asta?

Titlul: 170 Subsir 2
Scris de: ditzone din Ianuarie 21, 2006, 22:31:44
O(n^2) era suficient pentru a obtine punctaj maxim... Va aprea articolul cu solutii in curand (in seara asta sau maine).

Titlul: 170 Subsir 2
Scris de: Marius Stroe din Ianuarie 31, 2006, 00:10:58
Ce sa inteleg prin "TEST 4   ...[0.00s]...   Lungime corecta!" ?  In rest scrie "Ciaules Bulan!" care cred ca sunt rezolvate corect.  :P   In problema se zice ca:
"Pentru fiecare test se va acorda 40% din punctaj pentru determinarea corecta a lungimii subsirului, inca 40% pentru determinarea unei solutii corecte, si inca 20% daca solutia determinata este minima din punct de vedere lexicografic."  Cum pot sa iau 97 de puncte ?  :o

Titlul: 170 Subsir 2
Scris de: u-92 din Ianuarie 31, 2006, 00:20:58
fiecare test are 5 puncte, daca ai determinat lungimea corect ai 40% din 5, adica 2 :)

Titlul: 170 Subsir 2
Scris de: Rus Cristian din Februarie 03, 2006, 09:52:54
scuze ca pun prostii pe aici, am vazut solutia oficiala...dar daca puteti, va rog sa imi spuneti daca urmatoarele rezultate sunt corecte:

Cod:

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

subsir2.out
2
1 6


si

Cod:

subsir2.in
16
-15 11 10 -14 7 13 7 -3 -1 -20 6 16 -25 -19 17 23 

subsir2.out
5
1 4 11 12 15



si eventual sa dati nishte teste naspa...ca iau 54 de pct...si nu stiu ce am gresit...am facut un generator si toate cazurile incercate imi ies...pls...save me

Titlul: 170 Subsir 2
Scris de: Marius Stroe din Februarie 03, 2006, 10:34:29
Mie imi da asa:

Cod:

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

subsir2.out 
1
12


si

Cod:

subsir2.in 
16 
-15 11 10 -14 7 13 7 -3 -1 -20 6 16 -25 -19 17 23 

subsir2.out 
4
13 14 15 16


Trebuie sa iti spun ca programul meu ia numai 97 de puncte  :) .

Titlul: 170 Subsir 2
Scris de: Rus Cristian din Februarie 03, 2006, 12:09:25
ms...am facut suta...problema ta e de la implementare...nu e nimic special...mai incearca sa scrii sursa o data

Titlul: 170 Subsir 2
Scris de: Sima Mihai Cotizo -vechi din Februarie 14, 2006, 22:53:06
am si eu o mica... mare problema
(ca sa nu zica nimeni nimica, am citit si rezolvarea oficiala, dar...)
eu fac asa: pentru fiecare i=1,n caut un j in 1,i-1 care sa aiba a>=a[j] (a - vectorul de numere citite) si numarul de "predecesori" ai lui j sa fie cel mai mare... un "predecesor" la mine e un numar care apare in actualul subsir... adica daca v<=v[j]+1 atunci reactualizez v... si afisez elementul maxim din v

ce nu e bine? (in afara de explicatia rezolvarii...:P) ca iau cateva puncte (45)... dar pentru primele 12 teste zice "Nu e bine"

Titlul: 170 Subsir 2
Scris de: u-92 din Februarie 14, 2006, 23:04:56
dar daca tot ai citit solutia oficiala de ce nu aplici acelasi algoritm? e clar ca algoritmul tau e gresit daca ia doar 45 puncte.. incearca testul asta:
Cod:
30
72 -91 62 49 28 55 -9 1 17 10 -24 -53 63 32 75 38 -25 -21 59 -28 -18 -60 10 62 96 -87 6 13 -17 50

Cod:
3 
2 4 30

Titlul: 170 Subsir 2
Scris de: Sima Mihai Cotizo -vechi din Februarie 14, 2006, 23:19:35
mie imi da ... 9 ?!?
Cod:

9
2 7 8 10 14 16 19 24 25

da, in mod evident e gresit... :-'
si totusi, ca sa fiu sincer, nu prea am inteles de unde anume sa caut (in sursa oficiala) si... ma intrebam daca ma puteti ajuta sa vad unde gresesc eu...

Titlul: Răspuns: 170 Subsir 2
Scris de: Pandia Gheorghe din Aprilie 05, 2007, 10:37:58
Mie mi se pare ciudat enuntul la aceasta problema. (Ma refer la observatii) Adica pana la urma cine e a si cine b. Pe undeva am impresia ca se confunda unu cu altul si nu imi dau seama unde ar trebui sa pun eu "b" si unde "a".

De altfel solutia oficiala nu prea are treaba cu rubrica de observatii, sau cel putin nu asa cum le-am inteles eu. Imi clarifica si mie cineva va rog ?

Titlul: Răspuns: 170 Subsir 2
Scris de: Bunau Florin din Aprilie 06, 2007, 17:27:46
Au patit cumvan ceva testele?
Am implementat un subsir crescator in n log n, si iau ciaoles bulane de la 12 la 20.
Dar pe celelalalte teste 0 puncte. Solutia mea inca nu garanteaza ca solutia e si minima lexicografic, dar e imposibil sa nu returneze corect lungimea celui mai lung subsir crescator, pe care macar cat scrie parca 20% sau 40% ar trebuii sa iau. So my Q is WTF? puteti posta pls primul test sau unul din testele 1-12, care e mai scurt s avad care e faza, e imposibil sa nu gasesc lungimea corect.

Offtopic :  :banana:

Titlul: Răspuns: 170 Subsir 2
Scris de: Savin Tiberiu din Aprilie 06, 2007, 18:38:42
testele nu se fac publice. Nu e subsir crescator , e subsir crescator maximal, vezi poate nu ai inteles bine problema.

Titlul: Răspuns: 170 Subsir 2
Scris de: Bondane Cosmin din Mai 19, 2007, 10:29:16
Citat din mesajul lui: u-92 din Februarie 14, 2006, 23:04:56
dar daca tot ai citit solutia oficiala de ce nu aplici acelasi algoritm? e clar ca algoritmul tau e gresit daca ia doar 45 puncte.. incearca testul asta:
Cod:
30
72 -91 62 49 28 55 -9 1 17 10 -24 -53 63 32 75 38 -25 -21 59 -28 -18 -60 10 62 96 -87 6 13 -17 50
Cod:
3 
2 4 30

Raspunsul nu ar trebui sa fie
3
2 29 30 ?

Ori nu am inteles eu cum trebuie determinat sirul. ( eu iau 76 pcte, cu wa pt sir )

Titlul: Răspuns: 170 Subsir 2
Scris de: Savin Tiberiu din Mai 21, 2007, 09:06:49
tre sa fie minim lexicografic :P

Titlul: Răspuns: 170 Subsir 2
Scris de: Bondane Cosmin din Mai 21, 2007, 13:35:02
Minim lexicografic din pct de vedere al val. folosite? Sau a pozitiilor ?

Titlul: Răspuns: 170 Subsir 2
Scris de: Savin Tiberiu din Mai 21, 2007, 14:04:16
Citat
Solutia data este minima lexicografic din punct de vedere al valorilor elementelor subsirului.

Titlul: Răspuns: 170 Subsir 2
Scris de: Bondane Cosmin din Mai 21, 2007, 15:58:58
Pai atunci de ce nu ii raspunsul meu ??

raspunsul meu : -91 -17 50
cealalalt raspuns : -91 49 50

Titlul: Răspuns: 170 Subsir 2
Scris de: Paul-Dan Baltescu din Mai 21, 2007, 16:45:01
Pentru ca se ia lexicografic dupa pozitii.

Titlul: Răspuns: 170 Subsir 2
Scris de: Simina Pitur din Aprilie 16, 2008, 08:54:09
ceva special la primele 10 teste?  :'(

Titlul: Răspuns: 170 Subsir 2
Scris de: Bogdan-Alexandru Stoica din Aprilie 16, 2008, 09:52:00
iti merg toate testele de mai sus?

Titlul: Răspuns: 170 Subsir 2
Scris de: Farcasanu Alexandru Ciprian din Aprilie 18, 2008, 18:13:55
Nu prea inteleg cerinta problemei si nici explicatiile de la restrictii..care este diferenta intre un subsir crescator si un subsir crescator maximal ? si ce conditie trebuie sa respecte un subsir crescator maximal ca sa fie mai mic decat altul ?   multumesc anticipat

Titlul: Răspuns: 170 Subsir 2
Scris de: Andrei Grigorean din Aprilie 18, 2008, 18:43:53
Un subsir crescator este un subsir in care elementele de pe pozitii consecutive sunt in ordine crescatoare.

8 6 3 9 10 3 2 5 1 3  7 5 2 8 4 10.

Elementele boldate formeaza un subsir crescator.

Un subsir crescator se numeste maximal daca nu poate fi extins - Nu exista alt subsir crescator care sa "il contina". In exemplu de mai sus subsirul nu este maximal deoarece

8 6 3 9 10 3 2 5 1 3  7 5 2 8 4 10

contine subsirul nostru.

Titlul: Răspuns: 170 Subsir 2
Scris de: Farcasanu Alexandru Ciprian din Aprilie 18, 2008, 18:50:20
Aha , am inteles, multumesc, dar cum ramane cu cel mai scurt subsir crescator maximal , asta ce inseamna?

Titlul: Răspuns: 170 Subsir 2
Scris de: Bogdan-Alexandru Stoica din Aprilie 18, 2008, 18:59:00
Citat
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.

Titlul: Răspuns: 170 Subsir 2
Scris de: Lucian Boca din Aprilie 18, 2008, 20:01:53
Citat din mesajul lui: Farcasanu Ciprian din Aprilie 18, 2008, 18:50:20
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)  :wink:

Titlul: Răspuns: 170 Subsir 2
Scris de: Andrei Grigorean din Aprilie 18, 2008, 21:22:16
Dintre toate subsirurile crescatoare maximale il alegi pe cel de lungime minima.

Titlul: Răspuns: 170 Subsir 2
Scris de: Farcasanu Alexandru Ciprian din Aprilie 19, 2008, 07:29:57
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

Titlul: Răspuns: 170 Subsir 2
Scris de: Bogdan-Alexandru Stoica din Aprilie 21, 2008, 12:06:08
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.

Titlul: Răspuns: 170 Subsir 2
Scris de: Farcasanu Alexandru Ciprian din Aprilie 22, 2008, 08:34:02
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?:D

Titlul: Răspuns: 170 Subsir 2
Scris de: Bogdan-Alexandru Stoica din Aprilie 22, 2008, 09:19:31
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.

Titlul: Răspuns: 170 Subsir 2
Scris de: Farcasanu Alexandru Ciprian din Aprilie 23, 2008, 10:19:34
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?:D

Titlul: Răspuns: 170 Subsir 2
Scris de: Andrei Grigorean din Aprilie 23, 2008, 10:38:27
Te-ai uitat peste articolul cu solutii (http://infoarena.ro/preoni-2006/runda-3/solutii)?

Titlul: Răspuns: 170 Subsir 2
Scris de: Farcasanu Alexandru Ciprian din Aprilie 23, 2008, 19:53:50
m-am uitat, am facut ca acolo si tot nu iese

Titlul: Răspuns: 170 Subsir 2
Scris de: Andrei Grigorean din Aprilie 23, 2008, 19:59:27
Inseamna ca nu ai facut ca acolo ;)

Titlul: Răspuns: 170 Subsir 2
Scris de: Farcasanu Alexandru Ciprian din Aprilie 23, 2008, 20:47:43
poate am inteles eu gresit ce zice acolo....
LE: am rezolvat-o pana la urma

Titlul: Răspuns: 170 Subsir 2
Scris de: contu meu din Iulie 09, 2008, 15:16:16
imi poate spune cineva la ce se refera la problema asta cu lungime minima?....eu observ ca e subsirul de lungime maxima

Titlul: Răspuns: 170 Subsir 2
Scris de: theprdv din Ianuarie 24, 2015, 14:49:52
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? :poc:

Titlul: Răspuns: 170 Subsir 2
Scris de: Pirtoaca George Sebastian din Ianuarie 24, 2015, 17:00:19
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.

Titlul: Răspuns: 170 Subsir 2
Scris de: Tiplea Stefan din Septembrie 16, 2017, 19:34:00
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


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines