h1(#nave). 'Solutia':warm-up-2020/solutii/nave problemei 'Nave Interdimensionale':problema/nave_interdimensionale

 
Pentru primele <tex> 4 </tex> subtaskuri vezi "soluţia":moisil-2015/solutii#Naveplanare problemei "naveplanare":https://www.infoarena.ro/problema/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<tex> cnt[k]</tex> pentru <tex> k \in \mathds{N} </tex> numărul de nave care trec dinspre poziţia <tex>k</tex>spre poziţia <tex>k+1</tex>. Dacă <tex> cnt[k] </tex> este negativ, el va reprezenta numărul de nave care trec dinspre poziţia <tex>k+1 </tex>spre poziţia <tex>k </tex>înmulţit cu <tex> -1</tex>.
 
Observăm acum că costul aferent mişcării unei nave din <tex> x </tex> în <tex> y </tex> cu <tex> x \le y </tex> va fi numărul de valori <tex> cnt </tex> mai mari sau egale cu <tex> 0 </tex> minus numărul de valori <tex> cnt </tex> strict mai mici decât <tex> 0 </tex> în intervalul <tex> [x,y-1] </tex>.
 
De ce? Pentru că dacă <tex> cnt[k] </tex> este mai mare sau egal decât <tex> 0 </tex>, înseamnă că trebuie să consumăm o secundă pentru a mişca nava între <tex> k </tex> şi <tex> k+1 </tex>. Dacă <tex> cnt[k] </tex> este mai mic decât <tex> 0 </tex>, 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 <tex> k+1 </tex> spre <tex> k </tex> şi vom obţine acelaşi rezultat.
 
Există mai multe metode în <tex> O(</tex>Valoarea Maximă pe care o poate lua o coordonată<tex>) </tex> de a găsi mişcarea cea mai ieftină. Trebuie apoi să updatăm valorile din <tex> cnt </tex> ş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 <tex>  O(Vmax *  K)  </tex>

private

protected