Solutii Concursul National de Soft Grigore Moisil Lugoj 2014

Cerc5

Pentru primul joc, este necesara determinarea subsirului crescator de lungime maxima.

Pentru al doilea joc, se urmareste in O(K) pozitia poz pe care ajunge jucatorul 1 dupa efectuarea celor K mutari. Apoi, pe o tehnica similara aplicata invers se gasesc pozitiile de start ale lui poz - 1 si poz + 1.

Perfect2

Pentru prima cerinta este necesara determinarea minimurilor si maximelor pentru coordonata x, respectiv y.

Pentru a doua cerinta, fie DX = abs(A¹.x - A[i].x) si DY = abs(A¹.y - A[i].y). Segmentul este perfect daca niciun punct laticeal nu se afla pe segment, lucru adevarat daca si numai daca cmmdc(DX, DY) = 1.

Android

Problema se rezolva cu programare dinamica. Ne vom construi un tablou bidimensional cu urmatoarea semnificatie: dp[conf][i] = numarul de posibilitati de a ajunge in nodul i, avand vizitate toate nodurile corespunzatoare bitilor de 1 din conf.

dp[conf][i] = sum(dp[conf - (1 << i)][j]), astfel incat toate celelalte puncte dintre i si j sa fie deja vizitate.

Pentru 100 de puncte, este necesara o precalculare a punctelor dintre i si j. Complexitate finala O((N * M)^{2 * 2}(N * M))

Matperm2

Se observa ca din punctul de vedere al pozitiilor, la fiecare pas va avea acelasi efect. Astfel, putem obtine matricea dupa primul set de operatii si sa o transformam intr-o permutare de lungime N * M. Rezultatul ar fi permutarea compusa de P ori. Se pot obtine 70 de puncte cu ridicare la putere in timp logaritmic. Pentru 100 de puncte este necesara observatia ca ciclurile din permutare sunt independente intre ele. Astfel, problema se poate rezolva printr-o singura parcurgere a permutarii. Complexitate finala O(N * M).