Hi, so I was working on the Rest Stops Question from the 2018 February Silver Set, and my code is failing on all test cases but the sample test case. However, I’m unsure as to how my algorithm is failing when I can’t seem to be able to generate a test case on my own that my code will obtain the wrong answer for.
My algorithm is as follows:
-
Process the input and create a dictionary in which the reward corresponds to the rightmost rest stop index that has that reward. Also create a vector that contains all the different possible rewards
-
Sort the previous vector in descending order.
-
Iterate through the vector from the beginning, and for each reward value, if its index of occurrence is greater than where Bessie previously stopped, add to the total reward value the reward obtained from staying the maximum amount before Farmer John catches up(basically the lead that Bessie accumulated traveling from the previous rest stop(or starting point) to the current rest stop.
-
Do this until you go through the entire vector.
My code is as follows:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include<vector>
#include <cmath>
#include <array>
#include<map>
#include<set>
#include <fstream>
#include <unordered_map>
using namespace std;
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
int main() {
// setIO("reststops");
int length, stops, john, bessie; cin >> length >> stops >> john >> bessie;
int spare_time = (john-bessie)*length;
map<int, int> reward_to_stop;
vector<int> rewards;
for(int i = 0; i < stops; i++) {
int pt, reward; cin >> pt >> reward;
if(reward_to_stop.find(reward) != reward_to_stop.end()) {
reward_to_stop[reward] = max(pt, reward_to_stop[reward]);
}
else {
reward_to_stop[reward] = pt;
}
rewards.push_back(reward);
}
sort(rewards.begin(), rewards.end(), greater<int>());
int prev_stop = 0; int total_reward = 0; int i = 0;
while(i < rewards.size()) {
int target_reward = rewards[i];
int cur_stop = reward_to_stop[target_reward];
if(cur_stop > prev_stop) {
int time_taken = (john-bessie)*(cur_stop-prev_stop);
spare_time -= time_taken;
int reward_obtained = time_taken*target_reward;
total_reward += reward_obtained;
prev_stop = cur_stop;
}
i++;
}
cout << total_reward;
}
I looked at the external solution but the methodology behind the external solution was pretty much the same as what I had already written, so I would appreciate if anyone could help point me in the right direction(why my code might be erroring out, any test cases that I should try and debug through).
Thanks in advance 