In exemplu:
i1ti1i1tddd
Nu trebuie sa vina 1111?

in exemplu nu trebuia sa fie 3 in loc de 4?

Cate cuvinte poate avea un text?

La exemplu, exista pod intre
1 3
1 2
2 4
deci trebuie sa avem arhipelagul 1 2 3 4, nu?

Am implementat-o si am luat 100, dar in timpul concursului nu am luat cazul cu cel mai lung subsir crescator .

Daca aveam k1>1 si k2>1 atunci o secventa descrescatoare/crescatoare poate sa fie reprezentata de primul si ultimul element si alte elemente din mijlocul secventei. Atunci parcurgem sirul si pur si simplu, verificam fiecare secventa crescatoare si adunam min(k1,lungimea_secventei_crescatoare), la fel si la secventele descrescatoare. Evident trebuie sa avem grija sa nu adunam un element de 2 ori. Cum am zis mai sus, daca k1=1 sau k2=1 trebuie sa calculam cel mai lung subsir crescator/descrescator. Daca nu intelegi mai explic.

Dupa mine concert2 avea complexitate maxima de O(N*logN). Daca k1>1 si k2>1 atunci chiar intra in O(N), iar daca unul dintre ele era 1 atunci era cel mai lung subsir crescator. Multumesc lui Andrei Heidelbacher pentru observatia de mai sus, acel greedy nu e corect daca k1=1 sau k2=1.

la concert2  eu am gasit o solutie de O(n) dar nu stiu de ce nu mi-a dat pe testul 4. daca vreti va descriu ideea.

Solutia ta este un greedy incorect.

Pentru K1 = N si K2 = 1, problema se reduce la a determina subsirul crescator de lungime maxima si nu poate fi rezolvata intr-o complexitate mai mica de O(N * logN).
Pe testul

Cod:

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

raspunsul oferit de solutia ta este 7, iar raspunsul corect este 5.

Edit: problema determinarii subsirului crescator de lungime maxima este celebra in literatura de specialitate si puteti citi mai multe aici si aici.

Multumesc pentru ca m-ai lamurit. Astept solutiile oficiale. Nu m-am gandit la acest caz.

la concert2  eu am gasit o solutie de O(n) dar nu stiu de ce nu mi-a dat pe testul 4. daca vreti va descriu ideea.

Au fost interesante problemele. Din pacate am retrimis bancomat de 2 ori crezand ca 2^31 nu intra in int . Altfel aveam cam 23 de puncte in plus.
Care era al patrulea test de la concert2 ?

avem ca:
p₂=6
k₂=1
p₃=1
k₃=5
deci exemplul ar trebui sa fie:
6
0
6