# Tasty Meal

See the original problem on HackerRank.

To solve the problem we can easily observe that swapping the first c with the last p minimizes the tastiness.

The answer is $$0$$ when either:

• there are not p
• there are not c
• the last p is before the first c

For example:

 1  pppccc 

Instead, if neither of the conditions above occur, we swap the first occurrence of c with the last occurrence of p and we proceed with computing the tastiness.

The tastiness is calculated by running two loops: one forward and the other backwards. Here is the idea in C++:

  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  string s; cin >> s; auto firstC = s.find_first_of('c'); auto lastP = s.find_last_of('p'); auto cost = 0ll; if (firstC != string::npos && lastP != string::npos && firstC < lastP) { swap(s[firstC], s[lastP]); auto cnt = 0; for (auto i : s) { if (i == 'c') cnt++; else cost += cnt; } cnt = 0; for (int i=s.size()-1; i>=0; i--) { if (s[i] == 'p') cnt++; else cost += cnt; } } cout << cost; 

The solution is linear and does not allocate extra space.

### Playing with patterns

Can we replace loops with common functions?

Yes we can!

The first pattern we can think of is reduce. Here is the idea:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23  string s; cin >> s; auto firstC = s.find_first_of('c'); auto lastP = s.find_last_of('p'); auto cost = 0ll; if (firstC != string::npos && lastP != string::npos && firstC < lastP) { swap(s[firstC], s[lastP]); cost += accumulate(begin(s), end(s), make_pair(0ll,0ll), [](auto res, auto curr){ return curr == 'c' ? make_pair(res.first, res.second + 1) : make_pair(res.first+res.second, res.second); }).first; cost += accumulate(rbegin(s), rend(s), make_pair(0ll,0ll), [](auto res, auto curr){ return curr == 'p' ? make_pair(res.first, res.second + 1) : make_pair(res.first+res.second, res.second); }).first; } cout << cost; 

Clearly, we can refactor the code in order to ditch duplication. This is left as an exercise.

A second approach consists in the combination of other two patterns: map and prefix sum:

  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  string s; cin >> s; auto firstC = s.find_first_of('c'); auto lastP = s.find_last_of('p'); auto cost = 0ll; if (firstC != string::npos && lastP != string::npos && firstC < lastP) { swap(s[firstC], s[lastP]); vector c(s.begin(), s.end()); transform(begin(c), end(c), begin(c), [](auto i) { return (char)i == 'c'; }); partial_sum(begin(c), end(c), begin(c)); vector c2(s.begin(), s.end()); transform(begin(c2), end(c2), begin(c2), [](auto i) { return (char)i == 'p'; }); partial_sum(rbegin(c2), rend(c2), rbegin(c2)); for (auto i=0u; i

c and c2 are used to count respectively the number of c on the left and the number of p on the right.

Note that c2 is not simply c reversed. You can be deceived by this example:

 1  pccppc 

After the swap:

 1  ppcpcc 

In this case, c and c2 are actually duals:

 1 2  c: 0 0 1 2 2 3 c2: 3 2 2 1 0 0 

However, this is just because they have the same number of occurrences.

On ther other hand, this example (suppose it’s already swapped):

 1  pppcpc 

Leads to very different c and c2:

 1 2  c: 0 0 0 1 1 2 c2: 4 3 2 1 1 0 

The core part of this solution can be rewritten with C++ ranges:

  1 2 3 4 5 6 7 8 9 10 11  auto c = views::transform(s, [](auto c) { return (int)(c == 'c'); }) | views::partial_sum; auto c2 = views::transform(s, [](auto c) { return (int)(c == 'p'); }) | views::reverse | views::partial_sum | ranges::to>(); std::cout << ranges::accumulate( views::zip(s, c, c2 | views::reverse) | views::transform([](auto p) { return std::get<0>(p) == 'p' ? std::get<1>(p) : std::get<2>(p); }), 0); 

Clearly, in this case we pay an extra vector (needed because we can’t apply view::reverse on view::partial_sum directly since this one does not produce a bidirectional range).

We've worked on this challenge in these gyms: modena