/* https://www.hackerrank.com/contests/rookierank/challenges/counting-valleys */ #include #include #include #include using namespace std; bool isZero(int test){return test==0;} int main() { int n; cin >> n; // The Us and Ds. string journey; cin >> journey; /* Using the input, create a vector that functions as the function D(t), where D is the depth and t is the time-step. */ vector depth; int totalDepth = 0; depth.push_back(totalDepth); for (auto iter = journey.begin(); iter < journey.end(); iter++) { char mander = *iter; if (mander == 'D') totalDepth--; else if (mander == 'U') totalDepth++; depth.push_back(totalDepth); } /* The number of valleys will be the times that D(t) dips below 0 and then returns. D(t) is a continuous function, so any region between t1 and t2 such that D(t1)=0 and D(t2)=0 is either a hill or a valley, if there is no point t3 in between t1 and t2 such D(t3)=0. To see if the region is a valley, evaluate D at an arbitrary point in between t1 and t2. If that point is negative, the region is a valley. */ // Find all points such that D(t)==0. // http://stackoverflow.com/a/25846323/5415895 vector zeros; vector::iterator iter = depth.begin(); while ((iter = find_if(iter, depth.end(), isZero)) != depth.end()) { // Add the distance to iter from the beginning of the vector. int dist = distance(depth.begin(), iter); zeros.push_back(dist); iter++; } int valleys = 0; for (int i = 0; i < zeros.size()-1; i++) { // Get a point between i and i+1. int between = (zeros[i] + zeros[i+1])/2; if (depth[between] < 0) valleys++; } cout << valleys; return 0; }