Tot nu mi se pare ok, de unde ar fi trebuit sa stiu eu ca mai trebuie sa optimizez solutia mea sau sa o las asa, avand in vedere ca aveam OK pe ambele teste de feedback?

Daca solutia oficiala la Triopalindrom este N ^ 2, atunci limita de timp e cam stransa am N ^ 2 pur si a luat TLE pe 2 teste....

Mai sunt 2 zile din concursul de pe codechef

La problema Collar am avut complexitatea O(N * nr_divizori), dar nu am reușit sa scap de TLE. Folosesc deque implementat de mana. A luat cineva 100 cu deque?

Si eu am facut cu deque, aceeasi complexitate, 764 ms maxim

http://www.infoarena.ro/monthly-2014/format

La monthly, ca sa iei punctele pentru o problema, trebuie sa treci toate testele.

[70]

Nu stiu, pe mine nu ma ajuta cu nimic sa stiu ca m-am chinuit jumate de concurs sa gasesc o idee buna (am gasit ceva ce parea ok, dar ori nu era ok, ori am gresit implementarea, habar n-am) si altii au luat 100 cu un brut optimizat, mai ales ca "optimizarea" aducea 70 de puncte in plus asta in conditiile in care, chiar si 10 puncte pot face diferenta la final

Oricum eu doar mi-am expus punctul de vedere. Exceptand bulaneala asta la kami, mie mi-a placut runda

Daca la vreun pas, suma curenta > valmax, atunci sol = 0.

Ne-am dat seama si noi in timpul concursului. In arhiva nu o sa mai ia 100.

Daca a luat 100 in concurs, degeaba nu mai ia in arhiva, cel putin din punctul meu de vedere )

Problemele au fost dragute, cu exceptia faptului ca la Kami se ia 100 cu o rezolvare de 2 lei, adica brut optimizat

KMP, ca sa vezi pentru fiecare cuvant din dictionar unde se potriveste in sirul mare + bitset, ca sa poti tine minte potrivirile si sa intre in memorie


LE: Eu am Match[ i ][ j ] - 1 daca exista vreun cuvant in dictionar care se potriveste pe subsecventa [i...j] in sirul mare, de aceea am nevoie de bitset.

Poti, spre exemplu, sa faci un graf, unde muchia X - Y din input e Y - X in graful tau (ti se spune ca X poate primi alimente de la Y daca exista drum de la X la Y, dar in continuare vom pleca de la nodul care distribuie spre nodurile care primesc).
Parcurgi nodurile crescator dupa cost, iar daca esti la nodul i si i e nevizitat, inseamna ca nu poate primi alimente de la niciun nod cu cost mai mic si Ans[ i ] = cost_initial[ i ]. Faci un dfs din i si marchezi nodurile nevizitate cu costul initial al lui i, nodurile parcurse in dfs neavand asociat un cost mai mic decat cost_initial[ i ]

Incearca sa muti forul cu j inaintea celui cu i. Daca configuratia la care esti nu il contine pe j, faci N pasi degeaba, cand il fixezi pe i 

Felicitari! 

app..am observat o sursa izbitoarea cu a ta a unui tip care trimite probleme la rmvc . ar trebui sa postezi de pe contul tau 

Dar cum ai vazut sursa, din moment ce n-ai rezolvat problema? 

In realitate, nici nu aveam pretentia ca testele initiale sa fie finale . Nu am putut produce teste suficient de bune pana in ziua concursului asa ca am decis sa lasam niste teste dummy, printre care unul rezonabil de mare pentru feedback, iar apoi sa le schimbam. Testul de feedback a ramas acelasi, iar celelalte au fost facute dupa ideile initiale (dar pe care nu am apucat sa le implementam cu succes pana la concurs). Subliniez ca testele n-au fost facute pe baza surselor implementate in concurs, pe care de-altfel nici nu le-am citit.

Erau multe punctaje de 90 fiindca aveam teste de jucarie. Suntem constienti ca a fost o miscare mai neortodoxa, dar din punctul nostru de vedere concurentii n-au fost afectati deloc, iar testele in final au iesit bine. In orice caz, vom incerca sa nu ajungem intr-o asemenea situatie in viitor.

Ok

S-au schimbat testele la aceasta problema in timpul concursului / dupa concurs?
In aceasta poza (este pe facebook, pe pagina infoarena), din cate vad, sunt multe punctaje de 90 la parb...


LE: Mda, au fost schimbate pe 8 iunie.

Esti sigur ca merge in O(N + M) worst case? Ce solutie ai?
Dupa cum se vede, si sursa mea merge bine pe restul testelor, doar ca pe cele bune merge foarte prost.  

Ce complexitate ai? Eu am luat TLE pe aceleasi teste in concurs, complexitatea parea ok, dar nu era.

Operatiile se executa in ordinea din input?

Mie mi se pare cam neclar enuntul. Cred ca ar merge cateva explicatii legate de exemplu...

Prin "se sterge o operatie de insert / erase din structura" se intelege ca facem operatia inversa celei care o stergem?

In enunt scrie "Structura de date accepta operatii de insert(time, val)", dar la date de intrare, pentru orice operatie de insert time = -inf. Cum am putea raspunde la query-uri daca intotdeauna time = -inf? 

Legat de feedback: parerea mea este ca ar trebui sa avem feedback, daca se poate chiar complet (pe toate testele). Aceasta este o parere subiectiva, bineinteles, deoarece am pierdut multe puncte anul acesta la ONI:
1. La problema amici am facut un brut pentru cazurile mici si alta rezolvare pt restul cazurilor, in speranta ca poate mai ciupesc cateva puncte, rezultatul fiind 0 cu MLE pe toate testele. Nu mi-ar fi trecut prin cap ca daca tin de 2 ori graful iau MLE pana si pe testele mici. Daca aveam feedback, scoteam cealalta rezolvare si mai luam cateva puncte pe brut.
2. La problema bemo am citit gresit enuntul, drumurile trebuiau sortate individual, apoi lexicografic, iar eu le-am sortat doar lexicografic, 0 puncte din nou. Daca aveam feedback, imi dadeam seama ca ceva nu e ok in rezolvarea mea si poate ma prindeam ca, de fapt, am rezolvat alta problema.
3. La problema spnzr, ca multi altii, am uitat sa citesc acel 1. Nu cred ca luam foarte multe puncte, dar cateva tot luam.

Legat de selectia lotului, dupa parerea mea e nevoie de 2 zile de baraj.

Nici mie nu-mi merg acele feature-uri, desi aseara mergeau foarte bine. Am incercat si de pe firefox, si de pe chrome, am dat si ctrl + f5, am dat si restart la pc si nimic. 

Din cate vad, il modifici pe n in for-ul acela. Fa ceva de genul: a = i * i; b = n * n - a;