Solutia problemei Rollercoaster
Subtask 1 (20 de puncte) - N ≤ 15
Pentru acest subtask se pot genera si verifica toate configuratiile de roller-coastere.
Complexitate timp: O(2N*N)
Complexitate spatiu: O(N)
Subtask 2 (20 + 20 de puncte) - N ≤ 1000
Pentru acest subtask este nevoie sa ne gandim la solutii de programare dinamica.
Prima idee care ne vine este:
dp[i] = coeficientul maxim de distractie al unui roller-coaster si se termina cu turnul i
Relatia de recurenta va fi:
dp0 = 0
dp[i] = max {dp[j] + cmmdc (a[j], a[i])| 0 <= j < i}
In acelasi timp mai tinem si:
cnt[i] = numarul de roller-coastere care au coeficient maxim de distractie si se termina cu turnul i
Complexitate timp: O(N2)
Complexitate spatiu: O(N)
Subtask 3 (20 + 20 + 60 de puncte) - N ≤ 250.000
Pentru punctaj maxim este nevoie sa exploatam operatia de cmmdc.
Vom crea o alta dinamica care nu tine cont de indicii turnurilor, dar va tine cont de divizorii inaltimilor.
dp[d] = coeficientul maxim de distractie al unui roller-coaster si se termina cu un turn cu inaltimea multiplu de d
Recurenta nu este foarte grea. Vom avea pentru fiecare turn i o variabila auxiliara best:
best = max{dp[d] + d| d este divizor al inaltimii turnului i}
Dupa vom actualiza dp-urile folosindu-ne de best:
dp[d] max= best unde d este divisor al inaltimii turnului i
Adaugarea vectorului cnt pentru aflarea numarului de solutii (cnt[d] = numarul de roller-coastere care au coeficient maxim de distractie si se termina cu un turn cu inaltime multiplu de d) se va face ca la solutia de 40p.
Complexitate timp: O(N*sqrt(MAXVAL))
Complexitate spatiu: O(MAXVAL + N)