Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2020-09-01 09:52:58.
Revizia anterioară Revizia următoare

Solutii Autumn WarmUp 2020

Solutia problemei Nave Interdimensionale

Pentru primele $4$ subtaskuri vezi soluţia problemei naveplanare

Pentru 100 de puncte vom folosi un greedy în care mutăm navele pe rând pentru a obţine o linie/coloană (liniile şi coloanele sunt de fapt independente) nouă pe care se află cel puţin o navă.

Fie $cnt[k]$ pentru $k \in \mathds{N}$ numărul de nave care trec dinspre poziţia $k$ spre poziţia $k+1$ . Dacă $cnt[k]$ este negativ, el va reprezenta numărul de nave care trec dinspre poziţia $k+1$ spre poziţia $k$ înmulţit cu $-1$ .

Observăm acum că costul aferent mişcării unei nave din $x$ în $y$ cu $x \le y$ va fi numărul de valori $cnt$ mai mari sau egale cu $0$ minus numărul de valori $cnt$ strict mai mici decât $0$ în intervalul $[x,y-1]$ .

De ce? Pentru că dacă $cnt[k]$ este mai mare sau egal decât $0$ , înseamnă că trebuie să consumăm o secundă pentru a mişca nava între $k$ şi $k+1$ . Dacă $cnt[k]$ este mai mic decât $0$ , am putea economisi o secundă: în loc să mişcăm nava asta spre dreapta, vom opri una dintre navele care se mişcă dinspre $k+1$ spre $k$ şi vom obţine acelaşi rezultat.

Există mai multe metode în $O($ Valoarea Maximă pe care o poate lua o coordonată $)$ de a găsi mişcarea cea mai ieftină. Trebuie apoi să updatăm valorile din $cnt$ şi să reluăm algoritmul până când numărul de linii care conţin cel puţin o navă este cel dorit.
Complexitatea finală este $O(Vmax * K)$

Solutia problemei Defrisare

Subtaskul 1

Cum $N \le 20$ putem să folosim metoda $Backtracking$ pentru a fixa direcţia în care va cădea fiecare copac.

Subtaskul 2

Arborele are forma unui vector.
Putem să ne folosim de programarea dinamică pentru a calcula numarul optim de operaţii necesare pentru fiecare nod $X$ dacă acesta este orientat spre stânga sau spre dreapta.

$DP[Nod][0] =$ numarul minim de operatii necesare pentru ca toti copacii aflati in stanga nodului $Nod$ sa pice dacă acesta cade spre stânga.
$DP[Nod][1] =$ numarul minim de operatii necesare pentru ca toti copacii aflati in stanga nodului $Nod$ sa pice dacă acesta cade spre dreapta.

Iniţial $DP[Nod][0] = DP[Nod][1] = min(DP[X][0], \hspace{0.1cm} DP[X][1]) + 1$ presupunând ca niciun copac nu are înălţimea mai mare ca $L1$ .
Dacă $H[X] > L1$ înseamnă că pot să tai copacul $X$ astfel încât să pice pe copacul curent, caz în care updatez $DP[Nod][1]:$ $DP[Nod][1] = min(DP[Nod][1], \hspace{0.1cm} DP[X][1])$

Dacă $H[Nod] > L1$ înseamnă că pot să tai copacul curent astfel încât să pice pe copacul $X$ , caz în care updatez $DP[Nod][0]:$ $DP[Nod][0] = min(DP[Nod][0], \hspace{0.1cm} DP[X][0])$

Subtaskul 3

Pentru acest subtask există $3$ cazuri:
$1.$ Există două noduri $X$ şi $Y$ legate de radacină prin muchii de lungimi $L1$ , respectiv $L2$ astfel încât $H[x] > L1$ şi $H[radacina] > L2$ . Răspunsul este $N - 2$ .

$2.$ Există un nod $X$ legat de radacină printr-o muchie de lungime $L1$ astfel încât $H[radacina] > L1$ sau $H[X] > L1$ . Răspunsul este $N - 1$ .
$3.$ Nu există nicio muchie a cărei lungimi este mai mică decât înălţimea unuia dintre copacii pe care îi leagă. Răspunsul este $N$ .

Subtaskul 4

Pentru a rezolva acest subtask vom folosi o abordare similară cu cea de la subtaskul $2$ .
Definim:
$DP[Nod][0] =$ numărul minim de operaţii necesare pentru a rezolva subarborele nodului $Nod$ dacă acesta cade spre unul dintre fii şi nu este doborât de alt fiu.
$Nod$ poate să nu atingă niciun alt copac.

$DP[Nod][1] =$ numărul minim de operaţii necesare pentru a rezolva subarborele nodului $Nod$ dacă acesta cade spre unul dintre fii şi este doborât de alt fiu
$DP[Nod][2] =$ numărul minim de operaţii necesare pentru a rezolva subarborele nodului $Nod$ dacă acesta cade spre radacină.
$Nod$ poate să nu fie atins de niciun alt copac.

$BEST[Nod] = min(DP[Nod][0], \hspace{0.1cm} DP[Nod][1], \hspace{0.1cm} DP[Nod][2])$

Rădăcina poate să fie orice nod cu grad mai mic sau egal cu $2$ .

Să presupunem că ne aflăm în nodul $Nod$ cu fii $X$ şi $Y$ de care se leagă prin muchiile de lungime $LX$ respectiv $LY$ .

Iniţializăm $DP[Nod][0], \hspace{0.1cm} DP[Nod][1], \hspace{0.1cm} DP[Nod][2]$ cu $1 + BEST[X] + BEST[Y]$ caz în care tai copacul curent fără să afecteze/ să fie afectat de subarborii lui $X$ şi $Y$ .

Dacă $Nod$ poate să doboare copacul $X$ atunci updatez $DP[Nod][0] : DP[Nod][0] = min(DP[Nod][0], \hspace{0.1cm} DP[X][0] + BEST[Y])$ . Analog pentru $Y$ .
Dacă $X$ poate să doboare copacul curent atunci updatez $DP[Nod][2] : DP[Nod][2] = min(DP[Nod][2], \hspace{0.1cm} DP[X][2] + BEST[Y])$ . Analog pentru $Y$ .
Dacă $X$ poate sa doboare copacul curent şi $Nod$ poate să doboare copacul $Y$ atunci updatez $DP[Nod][1] : DP[Nod][1] = min(DP[Nod][1], \hspace{0.1cm} DP[X][2] + DP[Y][0] - 1)$ . Deoarece unesc două lanţuri numarul de operaţii necesare se micşorează cu 1. Analog pentru cazul $Y -> Nod -> X$ .

Subtaskul 5

Soluţia se bazeaza pe acelaşi $DP$ ca la subtaskul 4.
Pentru fiecare nod o să avem nevoie de o variabilă în care reţinem $\sum_{fiu \in Nod} BEST[fiu]$ .

$DP[Nod][0]$ şi $DP[Nod][2]$ se calculează similar.
Pentru a calcula $DP[Nod][1]$ încercăm să cuplăm nodul curent cu fiecare fiu $X$ pe rând considerând că $X$ este doborât de copacul curent.
Avem însă nevoie să ştim ce fiu e optim să considerăm că doboară copacul $Nod$ .
Să presupunem că exista doi fii $X$ şi $Y$ care pot să cadă spre nodul actual. Considerăm că $X$ este mai bun ca $Y$ dacă $DP[X][2] - BEST[X] < DP[Y][2] - BEST[Y]$ . Astfel avem nevoie doar de primele două cele mai bune noduri care pot fi determinate printr-o singură parcurgere a fiilor nodului actual.

Solutia problemei Cuantictiori

$"$ Se asigură că se poate demonstra că numărul de progresii geometrice de lungime $k$ care au prima valoare egală cu $n$ este egal cu cel mai mare număr natural $X$ cu proprietatea că $X^k$ este divizor al lui $N$ . $"$
Pentru demonstraţie vedeţi soluţia problemei nambartiori.

Fie $gcd_{exp}(x)=\$ cel mai mare divizor comun al exponenţilor din descompunerea în factori primi a lui $x$ .

Vom demonstra mai întai că dacă $gcd_{exp}(x)=\ 1$ , atunci $x^y \in \N$ cu $y\in \mathds{Q}$ numai dacă $y$ se află de asemenea şi în $\mathds{N}$ . (Lema 1)

Fie $b\in \mathds{N}$ astfel încât $b=\ x^y$ şi $p$ şi $q \in \mathds{N}$ cu proprietatea că $(p,q)=\ 1$ , astfel încât $\frac{p}{q}=\ y$ .

Atunci $b =\ x^{\frac{p}{q}}$ şi deci $b^q =\ x^p$ .

Dacă $e$ şi $f$ sunt exponenţii factorului prim $P$ din descompunerea în factori primi a numerelor $b$ şi respectiv $x$ , reiese că: $e*q =\ f*p$ .

Ştim că $(p,q)=\ 1$ , deci $e$ va trebui să fie divizibil cu $p$ şi $f$ va trebui să fie divizibil cu $q$ .

Ştiind că acest lucru se aplică pentru orice număr prim $P$ , putem deci spune că toţi exponenţii din descompunerea în factori primi a numărului $x$ vor fi divizibili cu $q$ .

Deci cel mai mare divizor comun al exponenţilor din descompunerea în factori primi a numărului $x$ va fi divizibil cu $q$ .

Din moment ce $gcd_{exp}(x)=\ 1$ , va trebui ca şi $q$ să fie egal cu $1$ .

Atunci $y=\ \frac{p}{q} =\ \frac{p}{1} =\ p \in \mathds{N}$ , ceea ce trebuia demonstrat.
Dacă $n$ este primul termen, $q$ este raţia şi progresia cuantică are lungimea $k$ , condiţia de existenţă este următoarea:
$n^{q^{i}}$ este natural pentru oricare $i \in \{ 0, 1, 2, .... k-1 \}$ .

Fie $m \in \mathds{N}$ astfel încât $m^{gcd_{exp}(n)}=\ n$ . Intuitiv, $gcd_{exp}(m) =\ 1$ . Înlocuind mai sus, obţinem:

$m^{gcd_{exp}(n)*q^{i}}$ este natural pentru oricare $i \in \{ 0, 1, 2, .... k-1 \}$ .

Folosing Lema 1, obţinem că:

$gcd_{exp}(n)*q^{i}$ este natural pentru oricare $i \in \{ 0, 1, 2, .... k-1 \}$ .

Observăm astfel că am ajuns la problema nambartiori, doar că aplicata valorii $gcd_{exp}(n)$ .

Subtaskul 2

Putem să trecem prin fiecare numar, să-i calculam $gcd_{exp}$ -ul si să-i aplicam functia din nambartiori ca apoi să-l adaugam la rezultat.

Subtaskul 3

Observăm că un numar $n$ ne interesează doar dacă $gcd_{exp}(n)>=2$ . Asta înseamnă că în loc să trecem prin toate numerele pana la $10^{12}$ , putem pur şi simplu să mergem prin bazele acestor numere până în $10^6$ . Prin baze ne referim la numerele $n \in \mathds{N}$ cu proprietatea că $gcd_{exp}(n)=\ 1$ .