# Candies

See the original problem on HackerRank.

## Solutions

This problem can be solved with a greedy approach.

First of all, we distribute one candy to every child.

Then we can iterate adjacent children from left to right: if one is higher than the other but has less chandies, we give her a candy more.

Similarly, we do the same from right to left.

Here is a C++ implementation:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14  int N; cin >> N; vector v, candies; v.reserve(N); candies.resize(N, 1); copy_n(istream_iterator(cin), N, back_inserter(v)); for (auto i=1; iv[i-1] && candies[i]<=candies[i-1]) candies[i] = candies[i-1]+1; } for (auto i=N-1; i>0; --i) { if (v[i-1]>v[i] && candies[i-1]<=candies[i]) candies[i-1] = candies[i]+1; } cout << accumulate(begin(candies), end(candies), 0); 

In another approach we can distinguish 4 cases:

• valley: $$rating_ {i-1} \geq rating_ i \leq rating_ {i+1}$$
• rise: $$rating_ {i-1} < rating_ i \leq rating_ {i+1}$$
• fall: $$rating_ {i-1} \geq rating_ i > rating_ {i+1}$$
• peak: $$rating_ {i-1} < rating_ i > rating_ {i+1}$$

We can distribute candies this way:

• valleys get 1 candy
• rises get one more the previous child
• falls get one more the next child
• peaks get one more the maximum between her neighbors

The order of distribution counts:

• valleys
• rises, left to right
• falls, right to left
• peaks

Here is a C++ implementation:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34  int N; cin >> N; vector v(N+2), candies(N+2); v.front() = INT_MAX; copy_n(istream_iterator(cin), N, next(begin(v))); v.back() = INT_MAX; // valleys for (auto i = 1; i < N+1; ++i) { if (v[i] <= v[i - 1] && v[i] <= v[i + 1]) candies[i] = 1; } // rises for (auto i = 1; i < N+1; ++i) { if (v[i] > v[i - 1] && v[i] <= v[i + 1]) candies[i] = candies[i-1] + 1; } // falls for (auto i = N-1; i > 0; --i) { if (v[i] <= v[i - 1] && v[i] > v[i + 1]) candies[i] = candies[i + 1] + 1; } // peaks for (auto i = 1; i < N+1; ++i) { if (v[i] > v[i - 1] && v[i] > v[i + 1]) candies[i] = 1 + max(candies[i-1], candies[i+1]); } cout << accumulate(begin(candies), end(candies), 0ull); 
We've worked on this challenge in these gyms: modena