HackerEarth Byteland Trip problem solution

In this HackerEarth Byteland Trip problem solution Chintu is a member of the Lolympics committee and is assigned the task of dropping the players from the one stadium to another. There are total N stadiums in Byteland. There is at least one path between any two stadiums.

Each stadium has a Dominos outlet near it. Chintu loves pizza and will not drive the bus until and unless he gets one when he’s hungry. A trip from one stadium to another can be completed by buying atmost X pizzas for Chintu. He eats pizza at the beginning of each trip which is also counted as one of the X pizzas. Calculate the total minimum distance that Chintu can cover after eating a single pizza i.e. the distance after which Chintu gets hungry and throws tantrums.

Chintu can buy at most one pizza from one stadium.

HackerEarth Byteland Trip problem solution.

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000000007
#define ll long long int
#define pb push_back
#define mk make_pair
ll power(ll a, ll b) {
ll x = 1, y = a;
    while(b > 0) {
        if(b%2 == 1) {
            x=(x*y);
            if(x>mod) x%=mod;
        }
        y = (y*y);
        if(y>mod) y%=mod;
        b /= 2;
    }
    return x;
}
ll dist[102][102];
ll dup[102][102];
int main() 
{
  ios_base::sync_with_stdio(0); cin.tie(0);
  ll n,x,m,u,v,w,i,j,k;
  cin>>n>>x>>m;
  for(i = 1; i <= n; i++) {
    for(j = 1; j <= n; j++) {
      dist[i][j] = mod;
    }
    dist[i][i] = 0;
  }
  while(m--) {
    cin>>u>>v>>w;
    dist[u][v] = dist[v][u] = w;
  }
  // Floyd Warshall
  for(k = 1; k <= n; k++) {
    for(i = 1; i <= n; i++) {
      for(j = 1; j <= n; j++) {
        dist[i][j] = min(dist[i][j],dist[k][j]+dist[i][k]);
      }
    }
  }
  ll l,r,mid,res,maxi;
  l = 1;
  r = mod;
  res = 1;
  while(l <= r) {
    mid = (l+r)/2LL;
    maxi = 0LL;
    for(i = 1; i <= n; i++) {
      for(j = 1; j <= n; j++) {
        dup[i][j] = (dist[i][j]<=mid)?1LL:mod;
      }
    }
    //Floyd Warshall
    for(k = 1; k <= n; k++) {
      for(i = 1; i <= n; i++) {
        for(j = 1; j <= n; j++) {
          dup[i][j] = min(dup[i][j],dup[k][j]+dup[i][k]);
        }
      }
    }
    for(i = 1; i <= n; i++) {
      for(j = 1; j <= n; j++) {
        maxi = max(maxi,dup[i][j]);
      }
    }
    if(maxi <= x) {
      res = mid;
      r = mid-1LL;
    }
    else {
      l = mid+1LL;
    }
  }
  cout<<res<<endl;
  return 0;
}

Second solution

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
#include <memory.h>
#include <cassert>
  
using namespace std;

#define pb push_back
#define mp make_pair
#define F first
#define S second

const int N = 111;
const int M = 100500;
const int INF = (int)1e9;

int n, x, m;
int best[N];
long long rem[N];
vector< pair<int, int> > g[N];

bool go(int ver, long long value) {
  priority_queue< pair< int, pair<long long, int> > > pq;
  for (int i = 1; i <= n; i++) {
    best[i] = INF;
    rem[i] = 0LL;
  }
  best[ver] = 0;
  pq.push(mp(0, mp(0LL, ver)));
  while (!pq.empty()) {
    int ver = pq.top().S.S;
    long long canGo = pq.top().S.F;
    int dist = -pq.top().F;
    pq.pop();
    if (best[ver] < dist) continue;
    if (best[ver] == dist && rem[ver] > canGo) {
      continue;
    }
    for (int i = 0; i < (int)g[ver].size(); i++) {
      int to = g[ver][i].F;
      int cost = g[ver][i].S;
      if (cost <= 1LL * canGo) {
        long long new_can = canGo - 1LL * cost;
        int new_dist = dist;
        if (best[to] > dist) {
          best[to] = new_dist;
          rem[to] = new_can;
          pq.push(mp(-best[to], mp(rem[to], to)));
        } else if (best[to] == dist && rem[to] < new_can) {
          rem[to] = new_can;
          pq.push(mp(-best[to], mp(rem[to], to)));
        }
      } else {
        int new_dist = dist + 1;
        long long new_can = canGo + value - 1LL * cost;
        if (new_can < 0LL) {
          continue;
        }
        if (best[to] > dist) {
          best[to] = new_dist;
          rem[to] = new_can;
          pq.push(mp(-best[to], mp(rem[to], to)));
        } else if (best[to] == dist && rem[to] < new_can) {
          rem[to] = new_can;
          pq.push(mp(-best[to], mp(rem[to], to)));
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) if (best[i] > x) return false;
  return true;
}

bool can(long long value) {
  for (int i = 1; i <= n; i++) if (!go(i, value)) return false;
  return true;
}

int main() {
  scanf("%d%d%d", &n, &x, &m);
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    g[u].pb(mp(v, w));
    g[v].pb(mp(u, w));
  }
  long long le = 0LL;
  long long ri = (long long)1e15 + 1LL;
  can(30LL);
  while (le < ri) {
    long long mid = (le + ri) / 2LL;
    if (can(mid)) {
      ri = mid;
    } else {
      le = mid + 1;
    }
  }
  cout << le << endl;
  return 0;
}

HackerEarth Byteland Trip problem solution

HackerEarth Byteland Trip problem solution.

Second solution

Leave a Reply

Pages

Practice