I am trying to solve a question given on Codeforces involving dynamic programming with 3D arrays.
F. Trucks and Cities
There are \$n\$ cities along the road, which can be represented as a straight line. The \$i\$-th city is situated at the distance of \$a_i\$ kilometers from the origin. All cities are situated in the same direction from the origin. There are \$m\$ trucks travelling from one city to another.
Each truck can be described by \$4\$ integers: starting city \$s_i\$, finishing city \$f_i\$, fuel consumption \$c_i\$ and number of possible refuelings \$r_i\$. The \$i\$-th truck will spend \$c_i\$ litres of fuel per one kilometer.
When a truck arrives in some city, it can be refueled (but refueling is impossible in the middle of nowhere). The \$i\$-th truck can be refueled at most \$r_i\$ times. Each refueling makes truck's gas-tank full. All trucks start with full gas-tank.
All trucks will have gas-tanks of the same size \$V\$ litres. You should find minimum possible \$V\$ such that all trucks can reach their destinations without refueling more times than allowed.
Input
First line contains two integers \$n\$ and \$m\$ (\$2 ≤ n ≤ 400\$, \$1 ≤ m ≤ 250000\$) — the number of cities and trucks.
The second line contains \$n\$ integers \$a_1,a_2,…,a_n\$ (\$1 ≤ a_i ≤ 10^9\$, \$a_i < a_i + 1\$) — positions of cities in the ascending order.
Next \$m\$ lines contains \$4\$ integers each. The \$i\$-th line contains integers \$s_i, f_i, c_i, r_i\$ (\$1 ≤ s_i < f_i ≤ n\$, \$1 ≤ c_i ≤ 10^9\$, \$0 ≤ r_i ≤ n\$) — the description of the \$i\$-th truck.
Output
Print the only integer — minimum possible size of gas-tanks \$V\$ such that all trucks can reach their destinations.
Requirements
time limit per test — 2 seconds memory limit per test — 256 megabytes input — standard input output — standard output
Here is my code:
#include<iostream>
#include<vector>
using namespace std;
int mat[403][403][403];
//mat[current_location][final_location][refuel_count_left]
vector<int> city;
int fun(int s,int f, int r){
if(s==f){
return mat[s][f][r] = 0;
}
if(mat[s][f][r]!=0){
return mat[s][f][r];
}
if(s+1==f || r==0){
return mat[s][f][r] = city[f]-city[s];
}
int opt = city[s] + (city[f]-city[s])/(r+1);
int pos = lower_bound(city.begin()+s,city.begin()+f+1,opt) - city.begin();
mat[s][f][r] = max(fun(pos,f,r-1), city[pos] - city[s]);
//cout<<"s=" <<s<<" f="<<f<<" r="<<r<<" mat"<<mat[s][f][r]<<endl;
return mat[s][f][r];
}
int main(){
long long ans=0;
int no_cities,no_vehicle;
cin>>no_cities>>no_vehicle;
city.push_back(0);
for(int i=1;i<=no_cities;++i){
int b;cin>>b;
city.push_back(b);
}
for(int i=0;i<no_vehicle;++i){
int start,finish,costperkm,refuel_count;
cin>>start>>finish>>costperkm>>refuel_count;
long long vol_curr_vehicle = (long long)fun(start,finish,refuel_count)* (long long)costperkm;
//cout<<jj<<" ";
ans = max(ans,vol_curr_vehicle);
}
printf("%lld",ans);
return 0;
}
I've used a 3D array named mat
which stores the different DP states.
- 1st Dimension - index of starting location
- 2nd Dimension - index of final location to reach
- 3rd Dimension - No. of refueling left
The 𝑖th element in the city
array represents that the 𝑖th city is situated at the distance of ai kilometers from the origin.
Explanation for the code:
The fun(s,f,r)
function takes in 3 arguments representing the current position as s, finish position as f
and refuel_count_left
as r
.
The problem can be understood as dividing the array city
into r+1 segments
with the starting index as s
and ending index as f
.
That is, dividing city[s...f] into r+1 segments. This division should be in such a manner that from all segment max(city[ending index of current segment] - city[starting index of current segment]) is minimised.
Inside the function fun(s,f,r)
which computes and returns mat[s][f][r], the base cases are when:
s==f
then return 0; because dividing city[s...f] into r+1 segments is just no segment.mat[s][f][r]!=0
when mat[s][f][r] has already been computed then return it.s+1==f || r==0
then return city[f] - city[s]. which mean that either we have no refuling left then we have to reach the final position from the starting position. Or when we are just before the final position then we just directly reach the final position without refueling.
If none of the above match then we have to find the position of a element opt
which is equal to city[s] + (city[f]-city[s])/(r+1)
. i.e. - There will be one segment present to the left opt(a[s...p]
) and r segments to the right of opt (a[p....f]
).
a[s...p]
is the first segment out of the r+1 segments and a[p...f] contain the rest r segments out of the r+1 segments.**pos
is the first position that I've described.mat[s][f][r]
is maximum offun(pos,f,r-1)
andcity[pos] - city[s]
. wherefun(pos,f,r-1)
mean thatcity[s...pos]
is the first of the r segments andcity[pos...f]
are the restr-1
segments and so now we are going to compute forcity[pos...f]
withr=r-1
refuelings left.
So, I'm finding the maximum of the difference between the last and first elements of the segments and equating that to mat[s][f][r]
.
Here is the right answer.
I realized the my code took 1481 ms of time for execution.
What is way that I can use to reduce the time complexity or the time taken by code during execution?
mat
3-D array. What part didn't you understand? \$\endgroup\$ – ajaysinghnegi Feb 17 '19 at 6:04