Candies · Coding Gym

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<int> v, candies; v.reserve(N); candies.resize(N, 1);
copy_n(istream_iterator<int>(cin), N, back_inserter(v));
for (auto i=1; i<N; ++i)
{
    if (v[i]>v[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<unsigned long long> v(N+2), candies(N+2);
v.front() = INT_MAX;
copy_n(istream_iterator<int>(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);

greedy