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<long long> 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<long long> 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<s.size(); ++i)
    {
        if (s[i] == 'p')
            cost += c[i];
        else
            cost += c2[i];
    }
}

cout << cost;

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::vector<int>>();

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 
comments powered by Disqus