Salut,
trebuie să fac vreo optimizare netrivială la îmulțirea permutărilor (în afară de exponențiere în timp logaritmic)? Am încercat mai multe variante, iar toate îmi dau TLE doar la ultimele două teste. Am încercat atât să găsesc perioada, cât și să implementez un algoritm eficient pentru cache, dar speedup-ul e nesemnificativ, ultimele două teste rămânâd cu TLE. Am cronometrat diferitele faze ale programului și bottleneck-ul se pare că e îmulțirea permutărilor.

Da am citit. Imi dau acum seama, ca probabilitatea de a ajunge din 2 in 0 nu e 1/3 * 1/3, ci e mai mare, pentru ca poti merge din 2 in 1, apoi din 1 in 2 si tot asa. Pentru un a_i probabilitatea de a ajunge la 0 va fi de forma 1/3 * a_{i - 1} + 2/3 * a_{i + 1}.

Eu cred ca am putea modela scenariul cu probabilitati de trecere. In cazul in care avem o singura conditie, ele sunt de fapt probabilitati conditionale, unde probabilitatea evenimentului al doilea depinde de cea a primului eveniment. Cu alte cuvinte, primul eveniment influenteaza decursul celui de-al doilea.

La probabilitatile de trecere insa, putem considera oricat de multe evenimente, si nu doar doua, ca la cele conditionale. Voi da un scurt exemplu cu bile sa clarific probabilitatile de trecere. Cei ce sunt familiarizati cu acest subiect pot sari peste exemplu.

Avem 4 bile: 1 rosie si 3 negre. Cand scoatem o bila ii notam culoarea si o punem inapoi cu inca o bila de aceeasi culoare. Ne intereseaza probabilitatea ca a doua bila scoasa sa fie rosie. Daca scoatem prima oara una rosie o sa avem inainte de a doua tragere 2 rosii si 3 negre, iar daca scoatem una neagra o sa avem 1 rosie si 4 negre. Prima oara tragem una rosie cu probabilitate 1/4 si cu prob. 3/4 una neagra. A doua oara tragem cu prob. 2/5 una rosie (daca prima a fost rosie), respectiv cu 1/5 una rosie (daca prima a fost neagra). Adica, daca am nimerit cu probabilitatea 1/4 una rosie si implicit in urna o sa fie la a doua tragere 2 rosii si 3 negre, vom avea 2/5 probabilitate sa nimerim una rosie, deci in total 1/4 * 2/5. La fel in cazul in care tragem prima neagra, unde vom avea o probabilitate de 3/4 * 1/5 ca a doua sa fie rosie. Cu alte cuvinte avem o probabilitate de 1/4 ca a doua probabilitate sa fie 2/5 (prima rosie) si o probabilitate de 3/4 ca a doua probabilitate sa fie de 1/5. Apoi le insumam si obtinem probabilitatea totala ca a doua bila trasa sa fie rosie de 1/4 * 2/5 + 3/4 * 1/5. Putem extinde acest experiment pe oricat de multe trageri. De exemplu putem spune ca, daca a doua bila trasa a fost rosie, mai adaugam doua negre si daca a doua a fost neagra, putem scoate una rosie, sau orice altceva. Probabilitatea se calculeaza analog prin insumarea produselor fiecaror probabilitati. Nu intru in detalii tehnice aici. Vom folosi exact aceasta idee, pentru a modela scenariul din problema.

Am pus aici un document, in care am scris calculele in LaTeX impreuna cu explicatia, ca altfel nu se intelegeau prea multe. Pe aceeasi idee intuitiva vad ca au mers si unsilviu si balakraz94, amandoi avand probabilitatea ca furnica sa cada la fel ca si mine de 3/7. quicksand are si el aceeasi probabilitate. El face cumva cu probabilitati conditionale, dar nu m-am uitat prea atent.

Se considera memorie neconstanta la un algoritm recursiv? Ma refer aici la stiva in care urca si coboara recurenta, care depinde totusi de N.

Vroiam sa incep un topic pe acesta tema, dar vad ca exista deja unul foarte bun.
Sunt interesat si eu de reviste GInfo. Sa le tiparesc e sec, nu arata ca cele originale, plus ca ai alt sentiment sa tii revista originala in mana, e mai mult o chestie de colectionar. Nu stie cineva, daca se poate face vreo comanda, sau daca exista vreo editie de colectie (asemanator cu gazeta matematica, unde au aparut cateva sute de exemplare acum vreu cativa ani intr-un volum imens). De ce nu se mai tipareste GInfo?

Pe linux am lucrat si imi merge perfect. M-am folosit de evaluatorul lui sandyxp si de testele oficiale de la oji.
Da, de fiecare data cand am coborat am pus 0 pe acel nivel, si citesc cu fgets, si am fost atent si la '\n'-uri.

L.E: S-a rezolvat. Problema a fost ca eu citeam cu fgets sirul de intrare. Cand am citit caracter cu caracter a mers. Dubios, oare ce-o fi avand fgets?

mi-am evaluat programul cu testele de la oji, si imi intra lejer in timp sub 4ms si memorie sub 16kb pe toate testele. aici vad ca imi da tle pe toate, desi restrictiile datelor de intrare sunt aceleasi ca la oji. gresesc eu undeva si nu-mi dau seama?

o..  pardon.. ma gandeam ca incepe din 1

pentru acelasi exemplu, daca bea bautura energizanta pe prima treapta, poate sa mearga 2*2=4 trepte, adica ajunge de pe 1 pe 5, si de acolo mai da un pas fara sa bea nimic si ajunge in 6. adica 2 pasi si 2 lei. de ce nu e corect?

mersi mult

de ceva vreme nu mai pot afisa poze pe pagina de profil. inainte mergea bine cu macro-ul ! ! intre link-ul pozei, dar de vreo doua luni nu mai merge, imi afiseaza "Imaginile trebuie neaparat sa fie atasamente ale unei pagini." am dat copy-paste la link-ul pozei si tot asa.
am vazut ca ati facut niste modificari la site, si de atunci apare problema asta.
imi poate spune cineva ce sa fac?

nu m-am uitat peste solutiile oficiale. a fost prima varianta care mi-a venit in cap, am implementat-o si a mers. poate ajuta totusi pe cineva si o asemenea abordare.

merge foarte bine, dupa ciur, un arbore indexat binar sau unul de intervale pentru interogare

sigla ar trebui sa contina culorile si "formatul" infoarena, pentru a deveni mai apoi simbolul unui concurs de marca, a carui sigla poate fi imediat asociata cu site-ul.
eu as zice ca printre cele mai potrivite, ar fi sigla lui Vlad Dumitriu, pentru acel verde care te duce gandul imediat la infoarena si care se potriveste foarte bine cu gri-ul, de la "Algoritmiada". in plus si acel "O" in care sunt scrise complexitati, cifre binare etc. arata amploarea concursului, si ca se codeaza la greu
2009 are la fel un font, care duce cu gandul spre calculatoare/programare
si eu as fi de parere, ca sigla sa nu se schimbe de la an la an ci sa devina un "brand" 
L.E. http://infoarena.ro/utilizator/vlad_d?action=download&file=logo.jpg&safe_only=false

am facut mai multe solutii, cea care necesita cea mai putina memorie foloseste 1000 KB unde folosesc o matrice de 1000*1000 de tip byte (in fpc), ca sa retin 0 si 1 pentru fetita/tip de floare
nu imi dau seama cum sa retin datele cu mai putina memorie sau de o solutie care sa nu foloseasca deloc matrice.
imi puteti da vreo indicatie?

[sau egal]

da, am inteles enuntul si mai sus am dat un exemplu de la mine pentru ca intr-un sir crescator o valoare poate sa fie de mai multe ori.
in testele 5 si 7 o valoare apare de doua ori, programul meu afisand pozitia mai mare pentru ultimul caz al problemei, desi teoretic ambele pozitii sunt corecte (enunt: mai mic sau egal/mai mare sau egal)

[sau egal]

in enunt se cere afisarea numarului cel mai mic mai mare sau egal si cel mai mare mai mic sau egal ca x. asta inseamna ca pentru sirul 5 9 12 12 12 17 23 si x=12 se pot afisa oricare dintre pozitiile 3, 4, 5 pentru ca 12 se afla pe toate acele pozitii, adica 12=12. care pozitie trebuie afisata?

[acela]

@robby : in sala in care am fost eu a sesizat un elev de cls 10 ca euntul este gresit dar profesorii i-au zis ca sunt de la inspectorat si nu au cum sa fie gresite.. in final elevul a insistat , s-a dat un telefon si problema sa rezolvat . totul a durat cam 40-50 minute . asta s-a intamplat in braila

vad ca in alte judete s-a miscat lumea..
eu i-am zis ca e gresit enuntul.. dar nimeni de la clasa a 10-a n-a mai zis nimic, decat o fata care a stat 2 calc-uri in dreapta mea confirmand doar cu jumatate de voce ca exemplul e gresit. apoi domnul acela s-a uitat neputincios la noi.. si a plecat.. a zis sa facem ce credem.
orice om normal se ia dupa enunt, ca e cel mai putin probabil ca acela sa fie gresit
brasoveni! sa facem ceva!
am inteles ca toti au busit acolo din cauza enuntului. o posibila solutie ar fi rescrierea evaluatorului pentru problema asa cum e ea, gresita.. ca doar e tot o problema. un semn schibat nu prea schimba rationamentul cu mult, iar apoi se face reevaluarea surselor.. ar fi cea mai buna solutie.
ce credeti?

la modul serios acum. stie cineva o solutie practica pentru incidentul cu problema "piata" de la a 10-a? contestatie/alte chestii.. in brasov a fost chiar dezastru dupa cum am zis si mai devreme..
ar fi fruoms sa-si dea si altii cu parerea ce-ar putea face cei din brasov in situatia asta (poate si cei din alte judete, nu stiu daca s-a mai intamplat undeva greseala asta).
stiti cumva de ce s-a intamplat, cum (sau cand) s-a observat greseala si s-a corectat?
cateva sugestii practice de ce s-ar mai putea face acum..
am vazut ca majoritatea din voi isi cunosc deja punctajele. ati rescris problema acasa si ati testat-o in evaluator, sau ati aflat punctajele oficiale?

[stanga]

ce s-a intamplat la a 10-a a fost bataie de joc...sa ni se aduca dupa mai bn de jumate de ora enuntul corect la a 2-a problema...

sunt din brasov si am vazut si eu ca la problema a 2-a de la clasa a 10-a (piata) exemplul nu corespunde cu enuntul. in enunt se facea clar o permutare la stanga pe cand exemplul arata o permutare la dreapta a elementelor de pe fiecare linie.
mai mult, am si zis supraveghetoarelor ca acolo nu e ceva in ordine si ele au chemat pe altcineva (nu stiu daca era de specialitate, pentru ca am dat in brasov judeteana, nu cunosc persoana. eu sunt din fagaras).
acea persoana care a venit a zis ca nu are dreptul sa-mi zica nimic, ca asa au venit subiectele de la minister si sa mai citesc odata, poate nu am inteles.
am incercat sa vad care varianta dintre exemplu si ennunt e cea buna, dar aplicand exemplul pe o permutare la stanga (ca in problema) iesea suma tot 51 pentru valorile

Cod:

6
2 3
6 5

persoana a zis sa ma iau dupa enunt daca am nelamuriri. asa am si facut, am rezolvat problema (singura, pentru ca la probl. 1 habar n-am avut) si cand ajung acasa si citesc subiectele de pe http://ssv.ploiesti.ro/oni2008/judete.php vad ca e alt enunt (acela corect, care corespunde si exemplului)
ce as putea face? sa depun contestatia luni? vad ca acest incident nu s-a intamplat doar in brasov din citatul de mai sus.

[algoritmul clasic]

cred ca da. in ginfo la "Algoritmul lui Lee, Teorie si aplicatii" scrie asa: "Incercam sa aratam prin exemple
cum se efectueaza trecerea de algoritmul clasic de parcurgere în latime, la prelucrarea dinamica a nodurilor unui graf, folosind de fiecare data structura de date de tip coada"
la asta m-am referit. adica clasicul pe care se bazeaza iesirea cea mai scurta dintr-un labirint de exemplu. pe a 10-a la oji am vazut ca s-a dat in fiecare an ceva cu Lee iar in solutile oficiale scrie de multe ori "aplicand algoritmul lui Lee". unde gasesc acest algoritm "standard".

unde pot gasi algoritmul lui Lee clasic. am gasit pe ginfo un articol, dar e pe grafuri.
exista algoritmul clasic de parcurgere a unei matrici in vreo carte sau pe net undeva?

uitate pe lista de anul trecut de la oni: http://oni2007.around25.ro/index.php?uid=11.

mersi de link. am gasit acolo site-ul cu rhide, mi l-am luat si e totul ok 

am instalat g++ pe opensuse 10.2 cu updateru. problema e ca nu pot sa intru in el, adica in "ecranu albastru" unde scriu codul, doar sa folosesc compilatorul pe un fisier care il creez "manual" cu extensia cpp. am inteles ca e ceva cu rhide. poate explica cineva mai detaliat?

inca ceva.. am instalat gcc pe linux printr-un fel de update de la "install software" si e aceeasi problema ca mai inainte ca nu stiu cum sa intru in el. in /usr/bin sunt mai multe chestii legate de el, adica gcc, g++, c++, cpp. am incercat la fel sa le scot cu konsola, da nu merge cum imi mergea la fpc (vezi raspunsul de mai sus).
imi poate spune cineva ce sa fac?