Problem Info
Bronze 2017 - Why Did the Cow Cross the Road II
Question
My code outputs the expected answer when running the sample case locally, but throws a runtime error/memory limit exceeded error in the official USACO analysis mode:
Upon further troubleshooting and trying it on the usaco.guide IDE, it throws the following error:
What I’ve Tried
- Enabling
-fsanitize=undefined,addressflag in my compiler options - Using lldb to debug
I wasn’t able to reproduce the error seen above locally with any of these methods.
My Work
/*
USACO Bronze 2017: Why Did the Cow Cross the Road II
https://www.usaco.org/index.php?page=viewproblem2&cpid=712
*/
#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
// Returns true if a character is in a string, false if it isn't
bool isInString(char character, std::string str) {
if (std::find(str.begin(), str.end(), character) == str.end()) {
return false;
}
return true;
}
void nextCow(std::string &roadTotal, int &answer) {
// Store the letter of the first cow in currentCow
char currentCow = *roadTotal.begin();
// Delete its letter (since we don't need it anymore)
roadTotal.erase(roadTotal.begin());
// For each cow afterwards until currentCow strikes again, count the number of occurances
std::string roadSegment = "";
for (auto it = roadTotal.begin(); it < roadTotal.end(); it++) {
// Check if we've reached currentCow, if so, tally up the double-occurances by counting the length of roadSegment. Then, break out of the loop
if (*it == currentCow) {
answer += roadSegment.size();
roadTotal.erase(it);
break;
}
// If we haven't reached currentCow, check if the current iterator is in roadSegment
if (isInString(*it, roadSegment)) {
// If so, that's a double occurance: erase the one in roadSegment so that it doesn't get tallied up later
roadSegment.erase(std::find(roadSegment.begin(), roadSegment.end(), *it));
} else {
// If not, append it to roadSegment
roadSegment.push_back(*it);
}
}
}
int main() {
// For USACO contests before 2020
std::ifstream fin("circlecross.in");
std::ofstream fout("circlecross.out");
// Read the input
std::string roadTotal;
fin >> roadTotal;
// For each cow, determines the number of cows that cross its path
int answer = 0;
for (int i = 0; i <= 26; i++) {
nextCow(roadTotal, answer);
}
// Output the answer
fout << answer << "\n";
return 0;
}
To determine the number of path crossings other cows make with cow i, I looked at the segment in between the entrance and exit of i. For each cow present in the segment, we can determine whether it crosses paths with cow i by counting the number of occurrences in the segment. If a particular cow only occurs once in the segment, we can deem that it crosses paths with cow i, since its entrance and exit are on either side of cow i's path. Conversely, if a cow occurs twice in the segment, we can deem that it doesn’t cross paths with cow i, since its entrance and exit are both on one side of cow i's path. By using this logic on each of the cows and remove the entrances and exits of a cow after we’ve counted all of its path crossings, I found the total number of crossings.