BitCell

Am dat peste urmatoarea problema de pe campion.edu.ro:

predecesor


Timp maxim de execuţie/test: 0.5 secunde
Memorie totală disponibilă/stivă: 16MB/1 MB


Considerăm un şir de N numere naturale distincte a1, a2, ..., aN. Pentru fiecare termen ai definim predecesorul său, dacă există, ca fiind cel mai din dreapta termen aj, cu j < i şi aj < ai. De exemplu, pentru şirul 8, 12, 2, 4, 3, 10, 9, 7, 5, 6, numărul 8 este predecesorul lui 12, 3 este predecesorul lui 5, 10 nu este predecesorul niciunui număr, la fel 4 nu este predecesor pentru alt număr, 2 nu are predecesor.

Cerinţă

Scrieţi un program care determină câte numere din şir nu sunt predecesori ai niciunui alt număr.
Date de intrare

Fişierul de intrare predecesor.in conţine pe prima linie numărul natural N reprezentând numărul de termeni ai şirului. Pe următoarea linie se găsesc, separaţi prin câte un spaţiu, termenii a1, a2, ..., aN ai şirului.

Date de ieşire

Fişierul de ieşire predecesor.out va conţine o singura linie pe care va fi scris un singur număr natural reprezentând numărul de termeni ai şirului care nu sunt predecesori ai niciunui alt număr.
Restricţii

3 <= N <= 500 000
1 <= ai <= 1 000 000 000, pentru orice 1 <= i <= N
Exemplu

predecesor.in predecesor.out
10 6
8 12 2 4 3 10 9 7 5 6

Problema este la enunt. In primul rand predecesorul unui numar nu se afla in dreapta acestuia daca analizam conform axei numerelor ci in stanga. In al doilea rand, daca se afla in dreapta, dupa cum spune in enunt, indicele j nu are cum sa fie mai mic decat i (unde i este indicele termenului caruia ii cautam predecesorul).
Acum sa trecem la exemplele din enunt. Primele 3 sunt corecte doar luand in calcul rationamentul corect ce defineste notiunea de predecesor, nu cel din enunt. Mai exact, inlocuind cuvantul "dreapta" cu cuvantul "stanga" in enuntul problemei. Al 4-lea exemplu este gresit. De ce? Pentru ca 4 este predecesorul lui 10.
In exemplul problemei se afla in fisierul de intrare acelasi sir utilizat si exemplificat "corect" in enunt. Problema este in fisierul de iesire. 6 numere nu sunt predecesori niciunui alt numar? Eu am gasit doar 5: 6, 7, 9, 10, 12. Probabil al 6-lea este acel 4.
Ce spuneti de asta? Am rationat incorect?

Cred că atunci când zice că e cel mai din dreapta se referă la predecesor, adică să fie cât mai aproape de numărul ales.
Și în legătură cu 4 acela eu cred că nu e predecesorul lui 10, deoarece 3 mai aproape de 10.

Da, dar spune ca 3 este predecesorul lui 5. O asemenea afirmatie imi sugereaza o "detasare" de la regula. Vreau sa spun ca, atunci cand l-a luat pe 3 ca fiind predecesorul lui 5, adica sarind peste 3 numere (10, 9, 7) pe acelasi sistem il putem lua pe 4 ca fiind predecesor lui 10. Daca nu e corect, il luam pe 4 predecesor lui 9 sau lui 7. Rationamentul e simplu. Consideram 4 ca fiind valoarea termenului cu indicele 4 conform sirului. Valorile 10, 9 si 7 apartin termenilor sirului cu indicii 6, 7 respectiv 8. Pentru oricare dintre acesti termeni, indicele termenului care contine valoarea 4 este intotdeauna mai mic decat indicii termenilor care contin valorile enumerate mai sus. Iar valorile termenilor sunt intotdeauna mai mici. 4<7; 4<9; 4<10. Cele 2 conditii fiind indeplinite, rezulta ca exista in sir numere al caror predecesor este termenul cu valoarea 4.

---

L.E. (-- 17 Jul 2011, 16:09 --)

Ok, dar atunci de ce spune ca 3 este predecesorul lui 5? 3 nu este aproape de 5.

Nu cred că m-ai înțeles... Când a luat exemplul acela cu 3 e predecesor lui 5, el a vrut să arate că 5 are predecesor, pentru că nu poate să îl aibă pe 7,9,10 și a ajuns la 3 care îndeplinește condițiile problemei adică este mai mic decât 5 și are și indicele mai mic. Deci el nu vrea să arate în enunț că 3 este predecesor , ci că 5 are predecesor, că se nimerește ca 3 să fie predecesorul și a lui 10,9,7,5 ,it's pure coincidence.

Da, inteleg ce vrei sa spui. Oricum, situatia e interpretabila.

Mie mi se pare destul de clar enunțul. Ce nu e clar?

Pai pentru mine nu e clar ce spune in primele 2 randuri ale enuntului.
Spune asa: "Pentru fiecare termen ai definim predecesorul său, dacă există, ca fiind cel mai din dreapta termen aj, cu j < i şi aj < ai." Numarul caruia ii definim predecesorul este a indice i.
Reiau: Pentru fiecare termen (ai) ii definim predecesorul sau, daca exista, ca fiind (predecesorul) cel mai din dreapta termen aj, cu j<i si aj<ai.
Pai cum poate sa fie predecesorul unui numar "cel mai din dreapta" termen fata de acel numar? Dupa cum am mai spus, daca e in dreapta, indicele lui nu are cum sa fie mai mare decat cel al termenului respectiv.
Asta nu e clar in cazul meu.

Cosmine... Enunțul spune că predecesorul este un număr al cărui indice este j. Este normal ca j<i, pentru că indici sunt crescători. În enunț mai e condiția ca aj<ai, deci predecesorul se află înaintea lui ai și e mai mic decât acesta. Și revenim unde ai zis tu că nu înțelegi: în exemplu acela din enunț, 5 are trei numere înaintea lui care sunt mai mici decât el :"2,4,3", dar predecesor este doar 3 pentru că el este cel mai din dreapta din tot șirul acesta , este cel mai aproape de 5, care și îndeplinește condițiile problemei.

Da...abia acum am inteles. Probabil nu sunt obisnuit cu problemele...

Oricum problema e destul de dificilă...

Dupa toate aceste "sfortari" legate de enunt, am reusit intr-un final sa aduc rezolvarea la o forma ce se incadreaza in parametrii stabiliti de problema. O sa postez sursa si descrierea rationamentului in caz ca exista useri interesati de problema.

Ideea de rezolvare a fost eliminarea tuturor predecesorilor numerelor din sir. Cu alte cuvinte, daca un termen este predecesorul altuia, il elimin din sir, atribuindu-i valoarea 0 (nu e chiar eliminare, ci inlocuire cu 0). Dupa aceasta "eliminare", in sir raman doar termenii care nu sunt predecesori ai altor termeni dar si acele zerouri cu care am inlocuit valorile predecesorilor. Prin simpla numarare a valorilor diferite de zero ramase in vector se determina numarul cautat.
Sursa are 916, 15 KB iar timpul de executie pentru exemplul problemei este de 0,063 secunde gratie lui Code::Blocks. Nu am avut timp sa testez programul si pe alte date de intrare mai mari ca marime. O sa incerc maine.
Multumesc Ciresel pentru explicatii.
Bafta.

Dar ce faci când ai numere egale în șir? De exemplu:

4 5 5 6

4 < 5 => 4 predecesor pentru 5 -> îi atribui valoarea 0;
5 < 5 => 5 nu e predecesor pentru 5 -> îl lăsam așa;
5 < 6 => 5 e predecesor pentru 6 -> îi atribui valoarea 0;
La sfârșit o să ai doar pe 5 și pe 6. Dar oare 5( primul ) nu e predecesor pentru 6?

Da...ai dreptate. O sa verific.