170 Subsir 2

[ditzone]

Aici puteţi discuta despre problema Subsir 2.

[•wefgef]

care e complexitatea oficiala la problema asta?

[ditzone]

O(n^2) era suficient pentru a obtine punctaj maxim... Va aprea articolul cu solutii in curand (in seara asta sau maine).

[•Marius]

Ce sa inteleg prin "TEST 4   ...[0.00s]...   Lungime corecta!" ?  In rest scrie "Ciaules Bulan!" care cred ca sunt rezolvate corect.     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 ?  

[u-92]

fiecare test are 5 puncte, daca ai determinat lungimea corect ai 40% din 5, adica 2

[•cristy]

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

[•Marius]

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   .

[•cristy]

ms...am facut suta...problema ta e de la implementare...nu e nimic special...mai incearca sa scrii sursa o data

[•Coty]

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...) ca iau cateva puncte (45)... dar pentru primele 12 teste zice "Nu e bine"

[u-92]

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

[•Coty]

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

[•Bluedrop_demon]

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 ?

[•flo_demon]

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 : 

[•devilkind]

testele nu se fac publice. Nu e subsir crescator , e subsir crescator maximal, vezi poate nu ai inteles bine problema.

[•cos_min]

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 )

[•devilkind]

tre sa fie minim lexicografic

[•cos_min]

Minim lexicografic din pct de vedere al val. folosite? Sau a pozitiilor ?

[•devilkind]

Solutia data este minima lexicografic din punct de vedere al valorilor elementelor subsirului.

[•cos_min]

Pai atunci de ce nu ii raspunsul meu ??

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

[•pauldb]

Pentru ca se ia lexicografic dupa pozitii.

[•Stigma]

ceva special la primele 10 teste? 

[•fireatmyself]

iti merg toate testele de mai sus?

[•ciprianf]

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

[•wefgef]

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.

[•ciprianf]

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