Hi, I would like some help debugging my program to Kattis: Lane Switching (from ACPC 2017). My solution is the same as the intended one, but the code fails on all the test cases beyond the first two (and those test cases aren’t visible). I’ve looked over my code several times and I can’t find anything wrong; it works for all my hand-generated test cases as well. Could someone please help me debug it? Thanks
Problem Info
Kattis: Lane switching
https://open.kattis.com/problems/laneswitching
(This is also the second-to-last problem in the first section of USACO Guide Silver DFS)
My Work (includes comments in code)
Basically, I did the intend solution: I represent empty intervals as nodes, and adjacent intervals are connected with an edge if the ACM car can fit through; each edge is associated with the max safety factor that can be achieved if we go through it. Then, binary search on max safety factor we can have; to test if we can have safety factor >=k, dfs and only traverse edges associated with >=k.
My code on replit is here: Kattis Lane Switching (1) - Replit
(but for convenience, I also copy/pasted it here; the horizontal scrolling might be a bit annoying)
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <math.h>
using namespace std;
using ll=long long;
int N, M, R, SI;
vector<pair<pair<int, int>, int>> TIns;
map<pair<pair<int, int>, int>, int> ind; //index of each empty interval in TIns
vector<pair<int, int>> Ins[100]; //list of empty intervals in lane i: {start, end}
int visited[20000]; //visited[i]=0 if interval I is unvisited; 1 otherwise
vector<pair<int, double>> adj[20000]; //{node, safety factor}
bool ge(double d1, double d2){ //true if d1<=d2; deals with double precision issues
if (d1-d2>= -0.01) return true;
else return false;
}
void dfs(int x, double minSF){ //dfs, where we ensure the safety factor is >=minSF. (Note: we dfs on the indices of the empty intervals rather than the empty intervals themselves, to make things easier)
if (visited[x]==1) return;
visited[x]=1;
for (pair<int, double> p: adj[x]){ //traverses an edge if that edge is associated with safety factor >=minSF
if (ge(p.second, minSF)) dfs(p.first, minSF);
}
return;
}
bool test(double minSF){ //tests if the car can cross with safety factor >=minSF
for (int i=0; i<TIns.size(); i++) visited[i]=0;
dfs(SI, minSF);
for (pair<int, int> p: Ins[N-1]){
int i=ind[{p, N-1}];
if (visited[i]==1) return true;
}
return false;
}
int main() {
// ifstream cin("file.in");
cin>>N>>M>>R;
int acm[3], car[M][3]; //{lane, length, position}
vector<pair<int, int>> laneC[N]; //laneC[i]= list of intervals filled by cars in lane [i]; {start, end}
cin>>acm[0]>>acm[1]>>acm[2]; //first car is acm car
for (int i=1; i<M; i++){ //other cars take up space in intervals
cin>>car[i][0]>>car[i][1]>>car[i][2];
laneC[car[i][0]].push_back({car[i][2], car[i][2]+car[i][1]});
}
//sorts the "filled by car" intervals in each lane
for (int i=0; i<N; i++){
if (laneC[i].size()>0) sort(laneC[i].begin(), laneC[i].end());
}
//in each lane i: add all the empty intervals in it to Ins[i] (these intervals are in order)
for (int i=0; i<N; i++){
if (laneC[i].size()==0) Ins[i].push_back({0, R});
else{
if (laneC[i][0].first>0) Ins[i].push_back({0, laneC[i][0].first});
for (int j=0; j<laneC[i].size()-1; j++){
Ins[i].push_back({laneC[i][j].second, laneC[i][j+1].first});
if (laneC[i][j].second==laneC[i][j+1].first) Ins[i].pop_back();
}
if (laneC[i].back().second<R) Ins[i].push_back({laneC[i].back().second, R});
}
//add all these empty intervals to TIns:
for (pair<int, int> p: Ins[i]) TIns.push_back({p, i});
}
//map each empty interval to its corresponding index in TIns, then find the index of the empty interval that ACM car is in
for (int i=0; i<TIns.size(); i++){
ind[TIns[i]]=i;
if (TIns[i].second==0){
if (acm[2]<=TIns[i].first.first && acm[1]+acm[2]<=TIns[i].first.second) SI=i;
}
}
//iterates through all pairs of intervals in adjacent lanes
for (int i=0; i<N-1; i++){
for (pair<int, int> i1: Ins[i]){
for (pair<int, int> i2: Ins[i+1]){
int a1=i1.first, a2=i1.second, b1=i2.first, b2=i2.second;
//intervals are {a1, a2} and {b1, b2}
//if they overlap and can fit the ACM car in: make an edge between the indices of these two intervals, associated with the max safety factor we can have when the car goes through
if (max(a1, b1)<=min(a2, b2)){
int d=min(a2, b2)-max(a1, b1), carL=acm[1];
if (d>=carL){
int p=ind[{i1, i}], q=ind[{i2, i+1}];
double maxSF=(double)(d-carL)/2.0;
adj[p].push_back({q, maxSF});
adj[q].push_back({p, maxSF});
}
}
}
}
}
//binary search on k to test if having safety factor >= k works
int lo=0, hi=2*R;
lo--;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
double k=(double)(mid)/2.0;
if (test(k)) {
lo = mid;
} else {
hi = mid - 1;
}
}
if (lo==-1) cout<<"IMPOSSIBLE";
else cout<<(double)(lo)/2.0;
}