Are cineva un test mai consistent, va rog?

Eu am luat 70. Iese de 100 si fara observatia ca ruscacul si vectorul v trebuie facute pana la (N+1)/2 ? Sau e alta chichita?

Salut! Eu iau un TLE pe testul 9. Am facut dinamica pe arbore, folosind doua DFS-uri. Arborele l-am tinut cu liste de adiacenta (vector <int> G[MAXN+1]). Cum as putea sa rezolv chestia asta? Spicuind comentariile m-am convins ca solutia mea este cea optima. E frustrant . Vreun sfat?

Va rog, ar putea posta cineva o mica explicatie a relatiei de reucrenta? d[ i][j] = diferenta maximace poate fi obtinuta in dreptunghiul incadrat de pozitia (1,1) si (i,j). Eu asa m-am gandit, dar nu ma prind cum sa continui. Am vazutca intr-adevar, si altii au facut asa. Mi-ar prinde bine un hint. multumesc in avans!

Ahhh, fir-ar. Multumesc! A facut cineva dinamica? eu am incercat sa fac un d[i,j] = nr. minim de sarituri pentru a elimina testoasele i, i+1....j. Aparent insa...nu aveam suficienta memorie pentru o matrice de 100000x10000. Am trimis sursa cu o matrice de 10000x1000 si a luat 3 teste..acum ma uit putin mai atent, deoarece am alta idee.

Va rog, are cineva un exemplu pentru care raspunsul nu este 1 sau 2 ? Poate este o intrebare tampita, dar eu chiar n-am putut gasi un caz in care sa am un raspuns mai mare ca 2 

Am si eu o intrebare...unde dau click sa ma inregistrez pentru runda 8? Mi-am facut curaj sa particip dar nu m-am prins cum sa ma inscriu

120 10 2 1 37 1 40 5 60 4 78 19 31 9 12 14 63 1 19 17 76 16 20 92 15 25 7 105 13 102 13 50 10 73 9 61 11 13 7 14 11 53 8 63 6 96 4 20 7 77 3 60 10 69 1 87 5 51 6 42 9 67 5

E o chestie ciudata. Sursa mea ia 100 pe Infoarena. Dar testul de mai sus este ultimul test de pe .Campion, la aceeasi problema.  Raspunsul considerat corect de Infoarena este: 20 31. Pe .Campion cel considerat corect este 20 38. Pana la urma cum sta treaba? Implementarea mea aici este o dinamica inainte. Solutia oficiala a problemei presupunea crearea unui graf si aplicarea algoritmului lui Dijkstra pe el, asta ca fapt divers, fiind din punctul meu de vedere irelevant deoarece o implementare corespunzatoare a uneia din cele doua solutii trebuie sa dea rezultatul corect.

Deci, cine greseste, .Campion sau Infoarena?

Are cineva vreo idee care m-ar putea sa trec si eu de 30 de puncte? Am WA pe al 4-lea test si TLE pe restul. De TLE-uri voi incerca sa rezolv cu unele metode specificate pe aici. Dar acel WA ce poate fi? Toate testele pe care le-am gasit in comentarii au dat raspunsurile corecte. Am avut grija sa calculez si modulo 66013. Putin ajutor, va rog? 

Salut! Mă lupt și eu cu dinamica în ultima vreme. Îmi poate spune cineva dacă definiția următoarei funcții conduce la o soluție a problemei ?  t(i,j) = timpul minim necesar pentru a ajunge la cota i , plecând cu j bani din cota 1

Nu sunt convins dacă am respectat sau nu principiile PD. Aș fi recunoscător dacă cineva ar putea să mă lămurească. 

Salut! Am o înțelegere intuitivă a algoritmilor ce sunt construiți folosind tehnica greedy, însă când vine vorba de demonstrarea corectitudini mă cam poticnesc pentru că nu înțeleg in totalitate principiile pe care se fac demonstrațiile. Am găsit pe internet diverse articole dar nu am reușit sa ma conving în totalitate.

Ați putea să-mi sugerați voi, din experiența voastră, alte resurse ? Articole, cărți, etc..

Ar putea da cineva un mic hint ? Citirea solutiei oficiale nu prea m-a ajutat .  .

Dar pe exemplul al doilea, alegand  o secventa formata dintr-un singur 1 si pozitionand-o intre secventa de 1 de lungime 3 si cea de lungime 4, nu se obtine o secventa de lungime 8?

Este aceasta alegere valida?

Sa presupunem ca pornesti cu suma X, 0 < X < M, ceea ce inseamna ca mai arunci cel putin o moneda. Sa analizam cele doua cazuri posibile:
1. obtii cap si castigi 1 cu probabilitate 50%. Din suma X, ajungi in suma X + 1 cu probabilitate 50%, deci la probabilitatea sa castigi pornind de la X aduni 0.5 * probabilitatea sa castigi pornind de la X + 1.
2. obtii pajura si pierzi 1 cu probabilitate 50%. Din suma X, ajungi in suma X - 1 cu probabilitate 50%, deci la probabilitatea sa castigi pornind de la X aduni 0.5 * probabilitatea sa castigi pornind de la X - 1.
De aici, deducem recurenta A[X] = 0.5 * A[X - 1] + 0.5 * A[X + 1] = (A[X - 1] + A[X + 1]) / 2.

Ahaaaaa.   . Intelesesem si eu ca de la suma X ajungi cu probabilitate egala, la suma X+1, sau X-1. Dar nu vedeam clar recurenta. Nu ma prinsesem ca datorita faptului ca si din X+1 si X-1 se poate ajunge in X, tot cu o prbabilitate de 50% este logic sa adunam la X 0.5*probabilitatea de a castiga pronind de la X-1, si 0.5*probabilitatea de a castiga pornind de la X+1.

Multumesc mult pentru clarificare!!   . As mai avea o intrebare: sa zicem ca vreau sa pun creionul pe hartie si sa calculez niste valori, daca iau de exemplu X=2 si M=5, nu vad cum as putea aplica recurenta, pentru ca pentru a calcula termenul curent trebuie sa am calculat termenul dinainte, si termenul de dupa. Deci, cum se aplica recurenta, cu creionul ?


EDIT: Intr-adevar recurenta e mai "tricky" de aplicat. Dar am reusit sa formulez ipoteza de inductie. Pentru cine are probleme recomand sa citeasca explicatiile lui Adrian Diaconu .

Merci din nou pentru ajutor!

In enunt este specificat ca te opresti in momentul in care obtii suma M. Daca pornesti direct cu M, atunci te opresti fara sa arunci nicio moneda. Astfel, probabilitatea sa ajungi la suma de M bani pornind cu M bani este 1 (adica 100%).

Multumesc pentru raspuns! AM editat insa intreabrea  . Voiam sa spun realtia 2. Aceasta nu stiu de unde vine... . Relatiile 1 si 3 le-am inteles, se observa usor. Insa la relatia nr. 2 am intr-adevar probleme. Scuze din nou.  . Ai putea sa ma ajuti cu relatia 2 ?

Fie un M fixat. Notam A[ i ] probabilitatea de a castiga pornind cu suma i.
Avem urmatoarele relatii:

(1) A[ 0 ] =0
(2) A[ i ] = 1/2 * (A[ i-1 ] + A[ i+1 ])
(3) A[M] = 1

Ar putea cineva sa imi spuna de unde vine relatia 2?  . Nu am reusit sa imi dau seama. O scurta explicatie, cineva, va rog ? 

Ahaa. Merci frumos! 

Ati putea da un mic indiciu despre cum se evita repetitiile? .

Cred ca diferenta dintre timpi este data de apelul functiei max in interiorul for-urilor.

Daca eliminam o subsecventa, trebuie sa decalam elementele spre stanga? Ceea ce vreau sa spun este: pe exemplul nostru ,daca eliminam prima seventa (intre indicii 2 si 5), spatiul gol lasa de aceasta va fi ocupat de elementele aflate dupa pozitia 5? Vom mai putea avea o seceventa de lungime mai mare ca 1 care sa il cuprinda si pe 6, sau nu?

Merci mult! Am inteles cum se face. La asta nu m-am ganidt. Totusi, varianta mea, adica adaptarea problemei de Knapsack, nu ar trebui sa poata lua 100 ?

Salut! Am facut si eu o dinamica O(n*(suma tuturor elementelor)/2) . Am optimizat, utilizand doar o linie de matrice. Cu toate acestea pic testul 7 si 10. Ce as mai putea face? Nu am nicio idee, am stat sa ma gandesc 3 ore. Cred ca am optimizat cat se putea sursa.  Ajutati-ma si pe mine, va rog!

In mod sigur nu gandesc bine, dar nu stiu de ce. Inegalitatea triunghiului afirma ca suma a doua laturi este mai mare ca cea de a treia. Dar de ce este suficient sa verificam daca:

if (a[k]<=a+a[j])

si nu trebuie sa luam in cnsiderare si celalate cazuri: a[j]<=a[k]+a si a[<=a[j]+a[k]. Imi scapa ceva... . Ar putea cineva sa ma lamureasca si pe mine? 


EDIT: Mi-am dat seama ))))

Unde se gaseste articolul cu explicatiile necesare?

Ok, am mai lucrat la problema. Am reusit sa iau 45 de puncte, iar la restul testelor sa obtin doar wrong answer, fara TLE-uri sau "killed by signal". Este ok daca am folosit ideea de la problema determinarii dreptunghiului de arie maxima dintr-o histograma? Sau m-am complicat?