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 kspre 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)