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)