SPOJ Problem M00PAIR

0 0 Pairs

Explanation:

This problem ask us to to find number of pair of consecutive zeros after 'n' steps. If you want to try the problem, I would give you one hint, it's a dynamic programming problem. Good luck!

Let's go through few values of n and the number of pair of consecutive zeros first to find out the dp pattern. 

n = 0.
pattern: 1(pattern0), no. of pairs: 0(output1)
Well, with one value, we won't be able to find out anything. Let's move to higher values.

n = 1.
pattern: 01(pattern1), no. of pairs: 0(output2)
Let's check for another value of n.

n = 2.
pattern: 10-01(pattern2), no. of pairs: 1(output2)
Here, the no. of pair gets incremented by 1, okay. Let's see what we can find in the pattern. We can see, that 01 at the end, is a pattern for n=1. Also, 1 at the beginning for n=2, is a pattern for n=0.
You can have similar observation for n=1.
So far, we found that, output2 will include sum of output1 and output0 as they are part of pattern for n=2. But, output2 = 1 != (output1 + output0). Let's move to next value and we will come back to this point.

n = 3.
pattern: 01-10-10-01(pattern3), no. of pairs: 1(output3)
Following pattern found above, we can see that, yes, pattern2 is part of pattern3. Now, 01(pattern1) at the beginning is also a part of pattern3, and last thing, 1(pattern0), is also a part of pattern3.
So, basically, we divided the whole pattern as shown below.
01 => (pattern1)
1 => (pattern0)
0
10-01 => (pattern2)
So, we can say that, output3 = output2 + output1 + output0, which is equal to 1 this time, and woah, formula worked.
We will come back to the point why the formula didn't work for n=2.

n = 4.
pattern: 10-01-01-10-01-10-10-01(pattern4), no. of pairs: 3(output4)
Let's straightaway divide the pattern.
10-01 => (pattern2)
01 => (pattern1)
1 => (pattern0)
0
01-10-10-01 => (pattern3)
Here, if we calculate (output0 + output1 + output2 + output3), we get 2, but output4 is 3. Now, where does this one more pattern comes into the picture. Okay, let's take a closer look at the pattern. One pair comes from pattern2, second comes from pattern3. The third one also comes from pattern3, but not completely from it. Hope you were able to find it by now. If not, you can give it a look, again.
Okay, there is a zero in our pattern which doesn't belong to any of the patterns defined above. This zero and the first zero in pattern3 add one more pair to the number of pairs. And now, you can scroll up and see if this was the same case for n=2.
Thus, we can say that, for some cases,
output(n) = output(n-1) + output(n-2) + ... + output1 + output0
and for some cases,
output(n) = output(n-1) + output(n-2) + ... + output1 + output0 + 1

So far, we have seen the latter case for n=2 and n=4.

n = 5.
pattern: 01-10-10-01-10-01-01-10-10-01-01-10-01-10-10-01(pattern5), no. of pairs: 5
Let's divide the pattern, as we have been doing.
01-10-10-01 => (patter3)
10-01 => (pattern2)
01 => (pattern1)
1 => (pattern0)
0
10-01-01-10-01-10-10-01 => (pattern4)
Here, we don't see that extra pair of zero adding up. Thus, we can say that, ouptut5 = output4 + output3 + output2 + output1 + output0, which is equal to 5 and thus the formula works.

Moving ahead, here is the pseudocode for above problem.

output(n) = output(n-1) + output(n-2) + ... + output1 + output0
if n is a multiple of 2.
   add 1 to output(n)

I will leave it to you to prove that we need to add 1 for patterns of even n's.

Simple, so far, there is one more twist to the problem. As you will move ahead, the value of output(n) overflows and won't fit into any basic data type for C++. So, just use string to store the sum.

Below is the solution provided. Happy coding!

Solution:

#include<cstdio>
#include<iostream>
#include<string>
#include<cstdlib>
#include<queue>
#include<stack>
#include<utility>
#include<string>
#include<cstring>
#include<set>
#include<cmath>
#include<vector>
#include<fstream>
#include<map>
#include<list>
#include<algorithm>

typedef long long int LLD;
typedef unsigned long long int LLU;

using namespace std;

string add(string a, string b){
    //  return a + b
    stack<int> st;
    string res = "";
    int i = a.length() - 1, j = b.length() - 1, carry = 0, sum;
    while(i >= 0 && j >= 0){
        sum = (a[i] - 48) + (b[j] - 48) + carry;
        st.push(sum % 10);
        carry = sum / 10;
        i--;j--;
    }
    while(i >= 0){
        sum = (a[i] - 48) + carry;
        st.push(sum % 10);
        carry = sum / 10;
        i--;
    }
    while(j >= 0){
        sum = (b[j] - 48) + carry;
        st.push(sum % 10);
        carry = sum / 10;
        j--;
    }
    while(carry){
        st.push(carry % 10);
        carry /= 10;
    }
    while(!st.empty()){
        res.append(1, st.top() + 48);
        st.pop();
    }
    return res;
}

int main(){

    string res[1000], total[1000];
    int n;
    /*  res[n] will store the result for nth step.
        total[n] will store the sum of res[0], res[1], ..., res[n-1], res[n] */
    res[0] = res[1] = total[0] = total[1] = "0";
    for(int i=2;i<1000;i++){
        res[i] = total[i-1];
        if(i % 2 == 0)
            res[i] = add(res[i], "1");
        total[i] = add(total[i-1], res[i]);
    }
    while(scanf("%d", &n) != EOF)
        cout << res[n] << endl;
    return 0;
}

Any suggestions are welcome.