MINCAP - Editorial

PROBLEM LINK:

Contest

Setter: nitjchapter
Tester: nitjchapter
Editorialist: nitjchapter

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Binary search, Dynamic Programming

PROBLEM:

Consider a hypothetical city on a 2D Cartesian-coordinate where one unit represents a distance of 1 kilometre. The city is spread over |x|≤ 1000 and |y|≤ 1000. There are various gas pumps located inside the city. Jim wants to visit his home town located at (ex,ey) in his car. The car consumes 1 litre gas per kilometre. Initially Jim is located at origin(0,0) with his car’s gas tank full. There are no obstacles in the city and he can cross any point(even the points where gas pumps are located) with his car. But he is constrained to drive parallel to either of the coordinate axes and hence the shortest distance between any two locations is Manhattan distance. If Jim leaves a gas pump, he cannot revisit it unless he has visited some other gas pump/pumps. Each gas pump has limited supply pi at a time. It can supply pi again if Jim revisit it. That is, each gas pump is refilled to its maximum supply pi

every time Jim leaves the pump.

Obviously, each time Jim reaches a gas pump he wants his gas tank to be refilled to its maximum capacity. But he cannot carry with him gas more than the tank capacity. Also he can take any route any number of times and there is no restriction on how long he takes to visit his home town.

You have to find the minimum capacity of the gas tank in the car that will allow him to reach his home town.

EXPLANATION:

We can binary search on the answer in the interval (1,2001). Let’s assume if Jim can reach his home town with minimum capacity of x litres of gas. Lets create a 2-D array ‘A’(whose indices represent all the data points) which keeps the record of largest amount of gas it had(including the gas collected from this coordinate also) in its last visit. Initialise all the indices in the array to -1 except the origin point which stores x.

We will only visit those points where:

  1. We have more (or equal to) litres of gas than required.
  2. It strictly increases the value at its index in the array A. Otherwise, we may get trapped in a cycle and get TLE.

If for any x, the value in the array A for home town is greater than -1 then it shall be the candidate for our answer.

TIME COMPLEXITY:

O(2000*nlogn)
The logn factor is produced by the binary search. At worst case we might be visiting every location atmost 2000 times.

SPACE COMPLEXITY:

O(n^2)

If you want to compensate time complexity for space complexity then use a map instead of a 2-D array A. In this case

TIME COMPLEXITY:

O(2000n(logn^2))

SPACE COMPLEXITY:

O(n)

SOLUTION:

Editorialist’s Solution

#include<bits/stdc++.h>
#define int long long
#define go(i,n) for (int i=1;i<=n;i++)
#define range(i,n) for (int i=0;i<n;i++)
#define endl '\n'
#define pb push_back
#define pi pair<int,int>
#define vi vector<int>
#define vpi vector<pi>
#define all(vv) vv.begin(),vv.end()
#define allr(vv) vv.rbegin(),vv.rend()
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define gcd __gcd
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
const int mod = 1e9+7;
const long long inf = 1e18;
const double prec = 1e-13;
const double pie = 3.141592653589793;
const int sz = 2e5+2;
using namespace std;

class triad{
    public:
        int one,two,three;
};

int bada(int gg,int hh){ if (gg>hh) return gg; return hh;}
int chota(int gg,int hh){ if (gg<hh) return gg; return hh;}
int bada(int gg,int hh, int ii){ if (gg>=hh && gg>=ii) return gg; else if (hh>=gg && hh>=ii) return hh; return ii;}
int chota(int gg,int hh, int ii){ if (gg<=hh && gg<=ii) return gg; else if (hh<=gg && hh<=ii) return hh; return ii;}
template<typename T> void print(T hh){for(auto gg=hh.begin();gg!=hh.end();gg++)cout<<*gg<<' ';cout<<endl;}
template<typename T> void print(T hh,int left,int right){for(auto gg=hh.begin()+left;gg!=hh.begin()+right+1;gg++)cout<<*gg<<' ';cout<<endl;}
int binpow(int xx,int yy,int mm){int res = 1;while (yy>0){if (yy&1) res = res * xx % mm;xx = xx * xx % mm;yy >>= 1;}return res;}

bool tests = 0;
int dx[] = {-1,0,0,1}, dy[] = {0,-1,1,0};

bool check(int mid, int ex,int ey, map<pi,int> dp,map<pi,int> points){
    dp[{0, 0}] = mid;
    dp[{ex, ey}] = -1;
    queue<triad> q;
    q.push({0, 0, mid});
    while (!q.empty())
    {
        auto curr = q.front();
        // cout << curr.one << ':' << curr.two << ":" << curr.three << endl;
        q.pop();
        for (auto z : dp)
        {
            if (z.first.first == curr.one && z.first.second == curr.two)
                continue;
            int temp = curr.three - (abs(curr.one - z.first.first) + abs(curr.two - z.first.second));
            if (z.second != mid && temp >= 0 && z.second < temp + points[z.first])
            {
                dp[z.first] = chota(temp + points[z.first], mid);
                q.push({z.first.first, z.first.second, dp[z.first]});
                // cout << "(" << z.first.first << ',' << z.first.second << "):" << dp[z.first] << endl;
            }
        }
    }
    if (dp[{ex,ey}]==-1) return false;
    return true;
}

int bs(int low,int high,int ex,int ey,map<pi,int> &dp ,map<pi,int> &points){
    int ans = -1;
    while (low<=high){
        int mid = (low+high)/2;
        if (check(mid,ex,ey,dp,points)) high = mid-1, ans = mid;
        else low = mid+1;
    }
    return ans;
}

void solve(void){

    int n,ex,ey,x,y,p;
    cin>>n>>ex>>ey;
    map<pi,int> points ,dp;
    points[{ex,ey}] = 0;
    range(i,n){
        cin>>x>>y>>p;
        points[{x,y}] = p;
        dp[{x,y}] = -1;
    }
    
    cout<<bs(1,2005,ex,ey,dp,points)<<endl;
}

void precal(void){
}

int32_t main(){

    fast

    int test=1;
    if (tests) cin>>test;
    precal();
    while (test--) solve();

    return 0;
}