# Oversized Pancake Flipper(Code Jam ’17 Qualification Round)

Last year, the Infinite House of Pancakes introduced a new kind of pancake. It has a happy face made of chocolate chips on one side (the “happy side”), and nothing on the other side (the “blank side”). You are the head cook on duty. The pancakes are cooked in a single row over a hot surface. As part of its infinite efforts to maximize efficiency, the House has recently given you an oversized pancake flipper that flips exactly K consecutive pancakes. That is, in that range of K pancakes, it changes every happy-side pancake to a blank-side pancake, and vice versa; it does not change the left-to-right order of those pancakes. Read Full Problem Statement.

Above problem can be well understood by taking an example of set of Coins instead of pancakes, where ‘+’ = ‘H’ and ‘-‘ = ‘T’. So problem statement goes like this.

“You are given a sequence of coins with either Head (H) will be faced up or Tail (T). Meanwhile you are asked to choose K consecutive coins and flip them i.e, H will end up T and vice versa. Now your overall objective is to obtain a sequence having all Heads (H) facing up and determine minimum number of flips to achieve it IF possible.”

Remember coins are not arranged in Cyclic manner.

**Example 1:**

TTTHTHHT 3

Here K = 3, one of the way to convert all of them facing H is

Flip first 3 coins -> HHH HTHHT

Flip last 3 coins -> HHHHT TTH

Flip remaining 3 coins -> HHHH HHH H

Hence we can achieve this in minimum of 3 steps.

**Example 2:**

THTHT 4

Here K = 4, we can’t convert above sequence in desired one.

**Naive approach \(O(2^n)\)**

One possible way is to recur to every possible combination and find minimum steps to obtain a sequence having all Heads (H). One important thing is to observe that maximum number of flips to convert a sequence into desired one is the length of sequence i.e, it is impossible to convert a sequence having all Heads if it is not possible to achieve in less than the length of sequence.

This approach works fine for a sequence of small length. Now lets discuss a clever approach.

**Optimal approach \(O( (n-K)*K )\)**

Lets understand this approach using **Example 1:**

Since we know that above sequence can be obtained in minimum of 3 steps. Lets try to achieve using a new method.

** Original Sequence:- TTTHTHHT **

First step :- **HHH**HTHHT

Second step:- HHHH**HTT**T

Third step:- HHHHH**HHH** :- **Required Sequence**

What we observed from above steps that we will start moving from very first coin and check whether it is Tail (T) or Head (H), depending on which we will do following steps

- If it is Tail (T), flip K coins including it also and increment
**COUNTER**. - If it is Head (H) leave it as it is and move forward.

At last if sequence consists of all Heads (H) then print value of counter or else print “Impossible”.

#include <bits/stdc++.h> using namespace std; int main() { int test; // Test cases cin>>test; for(int T=1;T<=test;T++) { string s; int n,k,counter=0; cin>>s; // Input sequence cin>>k; // Input consecutive flipping number n=s.size(); for(int i=0;i<=n-k;i++) { if(s[i]=='T') { for(int j=i;j<i+k;j++) // Flipping Sequences H <-> T s[j] = 'T' + 'H' - s[j]; counter++; } } if(s == string(n,'H')) // If all Heads appeared in sequence cout<<counter<<endl; else cout<<"IMPOSSIBLE"<<endl; } return 0; }

This article is contributed by Ravi Kant. If you like eLgo Academy and would like to contribute, you can mail your article to admin@elgoacademy.org. See your article appearing on the eLgo Academy page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.