TopCoder SRM 379 Div 1 Medium (TheAirTripDivOne)

The problems of latest TopCoder SRM 488 were set by Vasyl. The set was nice and a bit on the harder side. So, I was looking for the problems Vasyl set previously. I've found this one.

This problem is actually pretty straightforward. You just need to binary search on the safety parameter and for a particular value of safety, you have to determine if it is possible to make a series of trips within specified time to reach city n by waiting at least safety minutes between flights. This is essentially an shortest path problem on weighted graph which can be solved by Dijkstra's algorithm. We won't even need an efficient implementation as number of nodes and edges are within 500.



You can check a more detailed analysis here. Btw, you need to be careful to avoid overflow. Safe practice would be to just use long long.

Source code -

/*
Problem Name : TheAirTripDivOne
Problem Number : TopCoder SRM 479 Div 1 Medium
Link : http://www.topcoder.com/stat?c=problem_statement&pm=11030
Problem Type : Shortest Path, Binary Search
Difficulty : 5.5 / 10
Interest : 5 / 10
Complexity : O(VE)
Date : November 23, 2010
*/
#include<string>
#include<vector>
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;

#define rep(i,n) for(i=0;i<(n);i++)
#define MAXN 477
#define INF 1023456789

struct Flight {
 int A,B,F,T,P;
};

vector<Flight> fl;
int d[MAXN+2];
bool flag[MAXN+2];

struct TheAirTripDivOne{
 int n;
 int time;
 vector<string> parse(const string& s,const string& delim=" ") {
  vector<string>res;
  string t;
  for(int i=0;i!=s.size();i++) {
   if(delim.find(s[i]) != string::npos) {
    if(!t.empty()) {
     res.push_back(t);
     t="";
    }
   }
   else t+=s[i];
  }
  if(!t.empty()) res.push_back(t);
  return res;
 }

 long long get_next_flight(long long F,long long P, long long cur, long long safety, bool is_first) {
  if(is_first) safety = 1;
  long long x = (cur + safety - F + P - 1) / P;
  if(x < 0) x = 0;
  return F + x * P;
 }

 bool possible(int safety) {
  int i,j,mn,mnd;
  long long next;
  for(i=1;i<=n;i++) d[i] = INF;
  memset(flag,0,sizeof(flag));
  d[1] = 0;
  for(i=1;i<n;i++) {
   mnd = INF;
   for(j=1;j<=n;j++) if(!flag[j]) {
    if(d[j] < mnd) { mn = j; mnd = d[j]; }
   }
   if(mnd == INF) break;
   rep(j,(int)fl.size()) if(fl[j].A == mn) {
    next = get_next_flight(fl[j].F, fl[j].P, mnd, safety, (i == 1));
    if(d[fl[j].B] > next + fl[j].T) d[fl[j].B] = next + fl[j].T;
   }
   flag[mn] = true;
  }
  return (d[n] <= time);
 }

 int find(int n, vector <string> flights, int time) {
  int i;
  this->n = n;
  this->time = time;
  string s = "";
  rep(i, (int)flights.size()) s += flights[i];
  vector<string> vs = parse(s);
  fl.clear();
  vector<string> t;
  Flight f;
  rep(i, (int)vs.size()) {
   t = parse(vs[i],",");
   f.A = atoi(t[0].c_str());
   f.B = atoi(t[1].c_str());
   f.F = atoi(t[2].c_str());
   f.T = atoi(t[3].c_str());
   f.P = atoi(t[4].c_str());
   fl.push_back(f);
  }

  int lo = 1, hi = 1000000000, mid;
  while(hi-lo >= 5) {
   mid = (lo+hi)>>1;
   if(possible(mid)) lo = mid;
   else hi = mid-1;
  }
  for(i=hi;i>=lo;i--) {
   if(possible(i)) return i;
  }
  return -1;
 }
};