Solutions – Code Jam Qualification Round 2017

Contest Page: Qualification Round 2017

Know more about contest at blog post: Google Code Jam 2017

NOTE:

  • It is highly advised to try the problems on your own
  • Hints are provided below the solutions
  • The solution provided are written by me during the contest
  • Both, Small and Large test cases produced correct answer

Problem A. Oversized Pancake Flipper

#include<iostream>
using namespace std;
int main()
{
    freopen("A-large.in", "r", stdin);
    freopen("A-large.out", "w", stdout);
    int t, tt, ans, k, i, j;
    string s;
    cin >> t;
    for(tt=1; tt<=t; ++tt)
    {
        cin >> s >> k;
        ans = 0;
        for(i=s.length()-1; i>=0; --i) //Step 1
        {
            if(s[i]=='-' && i-k+1 >= 0) //Step 2
            {
                ++ans; // step 2.2
                for(j=0; j<k; ++j) //Flip (Step 2.1)
                    s[i-j] = s[i-j] == '-' ? '+' : '-';
            }
        }
        cout << "Case #" << tt << ": ";
        if(s.find('-') != string::npos) //Step 3.1
            cout << "IMPOSSIBLE" << endl;
        else //Step 3.2
            cout << ans << endl;
    }
    return 0;
}

Hint:

  1. Traverse from right side, Intialise counter variable to zero
  2. If ‘-‘ found and k pancakes(including the current one) are available on left side
    1. Flip the k pancakes(including the current one)
    2. Increment Counter
  3. Check if ‘-‘ is present in current string
    1. If yes, print “IMPOSSIBLE”
    2. Else print the counter value

Problem B. Tidy Numbers

#include<iostream>
#include<string>
using namespace std;
void print(int, string);
int main(){
    freopen("B-large-practice.in", "r", stdin);
    freopen("B-large-practice.out", "w", stdout);
    int t, tt, i;
    string s;
    cin >> t;
    for(tt=1; tt<=t; ++tt)
    {
        cin >> s;
        while(true)
        {
            for(i=0; i<s.length()-1; ++i) //Traverse (Step 1)
            {
                if(s[i+1] < s[i])
                    break;
            }
            if(i<s.length()-1) //Step 2
            {
                s[i] = s[i] - 1; //Step 2.1
                for(++i; i<s.length(); ++i) //Step 2.2
                    s[i] = '9';
            }
            else //Step 3
                break;
        }    
        print(tt, s);
    }
     return 0;
}
void print(int tt, string s)
{
    int i;
    cout << "Case #" << tt << ": ";
    for(i=0; i<s.length() && s[i]=='0'; ++i); //to ignore leading 0s
    for(; i<s.length(); ++i)
        cout << s[i];
    cout << endl;
}

Hint:

  1. Traverse for the left side, till the non-decreasing order is followed.
  2. If the decreasing order is found
    1. decrement the last digit following the non-decreasing property
    2. Replace all the digits on the right side by 9
    3. Go to Step 1
  3. Else the number is the required answer

 

That’s it for now! Found an error, have an issue. Wait for nobody, leave us a comment below.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s