Tasty Meal · Coding Gym

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 measuring the tastiness.

To count the tastiness, we can just run two loops: one forward and one 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 patterns?

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, refactoring is possible to remove code duplication. Left as an exercise.

A second approach consists in the combination of 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)); // cakes on the right (dual: pies on the left)

    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.

This core part of this solution can be rewritten with C++20 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, we pay an extra vector.