Oversized Pancake Flipper

This is the first problem in code jam qualification round 2017. The summery of the problem is as below. There are few number of pancakes which has one side made of chocolate chips (called as “happy side” )and a blank side. They are arranged in a single row in a random sides facing up. You have one pancakes flipper which flips exactly K consecutive pancakes.(NOT less than that or more than that) You need to find out the minimum number of times you need to use the flipper to leave all the pancakes happy side up or state there is no way to do it. For detailed version of this problem, one can refer this link. This contest is open for practice. I encourage you to solve it first before reading this solution.

Solution

Consider the below example given. —+-++- 3

The capacity of Pancake Flipper is 3. Your ultimate goal is to keep all the pancakes facing upside. i.e, (++++++++) with minimum number of attempts. If not possible then state, IMPOSSIBLE. One solution to this is,

1. Start from the first pancake.
2. Check if it facing black side upwards. i.e, Check if it is ‘-’.
3. If yes, then flip 3 consecutive pancakes. (3 because it is the capacity of pancake flipper)
4. Then check the next (has to increase by one )pancake.
5. Then go step 2 and repeat it for total number of pancakes. Also make sure it is not less than that of capacity of pancake flipper.
6. Once the step 5 is done, check whether all the pancakes remain happy side upwards. If yes print the number times you flipped as solution. If no, then we have no way to do it. So state IMPOSSIBLE.

Below are few sample solutions based on above steps.

Case 1:

—+-++- 3

Step 1 : +++ +-++-

Step 2 : ++++ +–-

Step 3 : +++++ +++

After final stage, it is ++++++++. And bolded text indicates the state, after being flipped. So here all the cakes are facing happy sides upwards. And we have used flipper for 3 times. So the solution is 3.

Case 2 :

-+-+- 4

Step 1 : +-+-

Step 2 is not possible. Now the second cake remains blank side upwards. ( + - + -). But we have left with only 3 cakes which is less than 4. (the capacity of pancake flipper). Now we are at the end. When we checked if all the cakes are facing happy side upwards, we get NO as answer. So the solution is IMPOSSIBLE.

The implementation of this solution in C++ is as below.

#include<iostream>
#include<string.h>
#include <bits/stdc++.h>
using namespace std;

main()
{
int No_Of_Trial;
cin >> No_Of_Trial;
for(int Trial= 1;Trial<=No_Of_Trial;Trial++)
{
//Get the pancake positions
string pancake;
cin>>pancake;

// Number of pancakes in current trial
int n = pancake.size();

//Get the Pancake Flipper's capacity
int k;
cin>>k;

//Final solution
int Number_Of_Flips = 0;

for(int i=0;i+k <= n;i++)
{
if(pancake[i] == '-')
{

for(int j=i;j< i+k;j++)
{
pancake[j] = (pancake[j] == '+') ? '-' : '+'; //Flip the pancake
}
Number_Of_Flips++;

}
}
//Now we have flipped pancakes. Check which trials are full of happy faces;
//if all are happy faces, then print the number of flips as solution
//otherwise print "IMPOSSIBLE"

bool All_Happyside = true;
for (int i = 0; i < n; i++)
{
All_Happyside = (pancake[i] == '+');
if(All_Happyside == false)
break;
}
printf("Case #%d: ", Trial);
if (All_Happyside)
printf("%d\n", Number_Of_Flips);
else
printf("IMPOSSIBLE\n");

}

return 0;
}