Editorial for GemTD
Submitting an official solution before solving the problem yourself is a bannable offence.
English
Turkish Below
The problem can be solved by using 2 steps.
At first we need to find which cells have been traversed by the enemy and how many times they are traversed. To find this we will just find the shortest path between checkpoints by using djikstra's shortest path algorithm and save the traversed set the traversed cells with corresponding points. After using Dijkstra 4 times(between 5 checkpoints) the 2D point grid can be created from these traversed cells.
Note: If a point is traversed 3 times its bombardment point should be \(\mathbf{3\times K}\).
You can learn about this algorithm from the link here: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
The Kadane algorithm finds the list that gives the highest point (let's call it maxList) in a 1D array in O(N) steps as follows:
- We start the algorithm by initializing the
best resultto the first element of the array and thecurrent resultto max({first element of the array} ,0).- So when no better result is found, the result of the algorithm is found as the first element of the array.
- Then, by traversing the remaining elements of the array, we update the 'current result' at each step and update the 'best result' when we find a better result than the `best result' found so far, and find the sublist with the highest score in this list in N steps, as follows:
- If the result we have is positive, we add the
current resultto the current element of the array. - If negative, the
current resultbecomes the current element of the array.
- If the result we have is positive, we add the
To solve the problem, if we set the left and right borders of our 2D point Grid for every number from 0 to N, and keep the sum of the elements of each row within these ranges in an array, we find the maxList of this array with the kadane algorithm. This way our solution finds the maximum point rectangle when its left and right limits are set. While determining the Left and Right borders, we can move the right border 1 unit to the right and update our array in O(N) steps for each left and right value. Also for every Left and Right values it will get O(N) steps to find the maxList using kadane algorihm. Because of these, the solution will work in \(\mathbf{O(N^2)\times(O(N)+O(N))}\) or \(\mathbf{O(N^3)}\) complexity for short.
Türkçe
Bu soruyu 2 adımda çözeceğiz.
İlk önce düşmanın hangi hücrelerden geçtiğini ve bu noktalardan kaç kez geçtiğimi bulmamız gerekiyor. Bunu bulmak için, dijkstra'nın shortest path algoritmasını checkpointler arasında kullanarak checkpointler arasındaki en kısa yolu bulacağız ve geçilen hücreleri gridimizde puanlayacağız. Dijkstra'yı 4 kez kullandıktan sonra (5 checkpoint arasında) bu geçilmiş hücrelerden 2D gridi oluşturulabilir.
Not: Bir noktadan 3 kez geçiliyorsa, bu noktayı bombalamak \(\mathbf{3\times K}\) olması gerektiğini unutmayın.
Djikstra'yla ilgili bilgi edinmek isterseniz şu linke göz atabilirsiniz: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
- Adımdaysa 2D puan gridimizdeki en yüksek puanı verecek dikdörtgeni bulmamız gerekiyor(Bu dikdörtgene maxRECT diyelim). maxRECT'i bulmak için kadane algoritmasından yararlanacağız.
Kadane algoritması 1D array(arr diye isimlendirelim) içerisindeki en yüksek puanlı sıralı listeyi(bu listeye maxList diyelim) O(N) adımda şu şekilde bulur:
En iyi sonucuarrayin ilk elemanınacurrent sonucuda max({arrayin ilk elemanı} ,0)'a eşitleyerek algoritmayı başlatırız.- Böylece daha iyi bir sonuç bulunmadığında sonucumuz arrayin ilk elemanı olarak bulunur.
- Daha sonra arrayin geri kalan elemanlarını gezerek her adımda
current sonucumuzuupdateleyipen iyi sonucumuzdandaha iyi bir sonuç bulduğumuzdaen iyi sonucumuzuupdateleyerek N adımda bu listedeki en yüksek puanı veren sublist'i şu şekilde buluruz:- Eğer elimizdeki sonuç pozitifse
current sonucuarrayin şu anki elemanını ekleriz. - Eğer negatifse
current sonucuarrayin şu anki elemanı olur.
- Eğer elimizdeki sonuç pozitifse
Soruyu çözmek için 2D lik point Gridimizin sol ve sağ sınırlararını 0 dan N'e kadar her sayı için deneyip bu aralıklar içindeki her satırın elemanları toplamını bir arrayde tutarsak, kadane algoritmasıyla bu arrayin maxList'ini bularak sağ ve sol sınırları belli olan en büyük dikdörtgeni bulabiliriz. Sol ve Sağ sınırları belirlerken sağ sınırı 1'er birim sağa kaydırarak ve arrayimizi her sol ve sağ değeri için O(N) adımda updateleyebiliriz. Kadane algoritmasını her Sol ve Sağ değeri için update etmekte yine O(N) adım alacağı için çözümümüz \(\mathbf{O(N^2)\times(O(N)+O(N))}\) veya kısaca \(\mathbf{O(N^3)}\) complexity ile bulunur.
Code
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define NUM 5
//
int NEGATIVE,POSITIVE;
struct point{
int x,y;
long cost;
point(int a,int b,long c):x(a),y(b),cost(c){}
point(){}
};
bool operator<(const point& lhs, const point& rhs)
{
return lhs.cost < rhs.cost;
}
bool operator>(const point& lhs, const point& rhs)
{
return lhs.cost > rhs.cost;
}
struct graph{
int N;
vector<point> **adjlist;
pair<int,int> **prev;
int **kadaneArr;
int CheckX[NUM],CheckY[NUM];
graph(int n,int E):N(n){
//--------------allocations-------
adjlist=new vector<point>*[N];
prev=new pair<int,int>*[N];
kadaneArr=new int*[N];
for(int i=0;i<N;i++){
adjlist[i]=new vector<point>[N];
prev[i]=new pair<int,int>[N];
kadaneArr[i]=new int[N];
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
kadaneArr[i][j]=NEGATIVE;
}
}
//--------------------------------
for(int i=0;i<NUM;i++){ // 1 start 3 checkpoints 1 end
cin>>CheckX[i]>>CheckY[i];
CheckX[i]--;
CheckY[i]--;
}
int a,b,c,d,e;
for(int i=0;i<E;i++){ // adding edges
cin>>a>>b>>c>>d>>e;
a--,b--,c--,d--;
adjlist[a][b].push_back({c,d,e});
adjlist[c][d].push_back({a,b,e});
}
}
~graph(){
for(int i=0;i<N;i++){
delete[] adjlist[i];
delete[] prev[i];
delete[] kadaneArr[i];
}
delete[] adjlist;
delete[] prev;
delete[] kadaneArr;
}
long solve(){
kadaneArr[CheckX[0]][CheckY[0]]=POSITIVE;
for(int i=0;i<NUM-1;i++){
djikstra(CheckX[i],CheckY[i],CheckX[i+1],CheckY[i+1]);
addPoints(CheckX[i],CheckY[i],CheckX[i+1],CheckY[i+1]);
}
return kadane2D();
}
void djikstra(int a,int b,int c,int d){
long arr[N][N];
bool visited[N][N];
//-----setting cost array to infinity-------
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
arr[i][j]=LLONG_MAX;
visited[i][j]=false;
}
}
arr[a][b]=0;
//------------------------------------------
priority_queue<point,vector<point>,greater<point>> Q;
Q.push({a,b,0});
while(!Q.empty()){
int x=Q.top().x;
int y=Q.top().y;
long currentCost=arr[x][y];
Q.pop();
if(x==c&&y==d)
return;
if(visited[x][y])continue;
visited[x][y]=true;
for(int i=0;i<adjlist[x][y].size();i++){
int edgeX=adjlist[x][y][i].x;
int edgeY=adjlist[x][y][i].y;
long edgeCost=adjlist[x][y][i].cost;
if(arr[edgeX][edgeY]>arr[x][y]+edgeCost){
arr[edgeX][edgeY]=arr[x][y]+edgeCost;
Q.push({edgeX,edgeY,arr[edgeX][edgeY]});
prev[edgeX][edgeY].first=x;
prev[edgeX][edgeY].second=y;
}
}
}
}
void addPoints(int a,int b,int c,int d){
int x=c,y=d;
while(x!=a||y!=b){
if(kadaneArr[x][y]==NEGATIVE)kadaneArr[x][y]=POSITIVE;
else kadaneArr[x][y]+=POSITIVE;
c=prev[x][y].first;
d=prev[x][y].second;
x=c,y=d;
}
}
long kadane2D(){
long res=0;
int arr[N];
for(int left=0;left<N;left++){
for(int i=0;i<N;i++)arr[i]=0;
for(int right=left;right<N;right++){
for(int i=0;i<N;i++)arr[i]+=kadaneArr[right][i];
res=max(res,kadane(arr));
}
}
return res;
}
long kadane(int *arr){
int current=arr[0],res=max(arr[0],0);
for(int i=1;i<N;i++){
if(current>0)current+=arr[i];
else current=arr[i];
if(current>res)res=current;
}
return res;
}
void print(){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
cout<<kadaneArr[i][j]<<"\t";
}
cout<<endl;
}
}
};
int main(){
int n,E;
cin>>n>>E>>NEGATIVE>>POSITIVE;
//kdCOST is stored in global its the cost of sending
graph g(n,E);
cout<<g.solve()<<endl;
}