Codeforces 451D - Count Good Substring & 451E - Devu and Flowers

451D - Count Good Substring

Problem Statement:
451D - Count Good Substring

Solution:
Simple \(O(N^2)\) check will be too slow, so there must be a better way, and indeed we have an
(O(N)\) solution that makes use of several observations. Firstly, if we compress the given string, you will always end up with an alternating sequence of 'a' and 'b's. This means that if a substring of our choice starts and ends with the same letter, it is definitely is a good palindrome. Secondly, a substring [i..j] will have an odd length if parity of i and j are the same, otherwise it will have an even length.



Using these two observations, we can iterate from left to right keeping track on 'a' and 'b' that is placed on even or odd index, and incrementally update our count, as demonstrated on the following code.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;

string s;
long long cnt[2][2];

int main(){
    cin >> s;
    int N = s.size();
    long long odd=0,even=0;
    int cur = 0, next;
    for(int i=0;i<N;++i){
        next = (cur+1)%2;
        odd += cnt[s[i]-'0'][cur];
        even += cnt[s[i]-'0'][next];
        odd++;
        cnt[s[i]-'0'][cur]++;
        cur = next;
    }
    cout << even << " " << odd << endl;
    return 0;
}

451E - Devu and Flowers

Problem Statement:
451E - Devu and Flowers

Solution:
This problem demonstrates the power of exclusion-inclusion principle. Let \(a_i \geq 0\) be the number of flowers taken from i-th box, such that \(\sum a_i = s\). If we do not have any restrictions on \(a_i\), we can distribute \(s\) flowers into \(n\) containers in \({ {s+n-1} \choose {n-1} }\) ways. However, in this problem we are given that \(a_i \leq f_i\). So what we can do:
for k = 0 to n, calculate how many ways can k boxes have more than f flowers, for all combination of k boxes. Call this value C(k).
Then using this results, we can come up with the final number of ways by using the inclusion-exclusion principle, as C(0) - C(1) + C(2) - C(3) + ...

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int n;
long long s;
long long f[23];
long long MOD = (long long)1e9 + 7LL;
long long d[23];
/* extended euclid
ax+by = 1 = bx'+qy'
q = a%b = a - (a/b)*b
bx' + (a-(a/b)*b)y' = b(x'-(a/b)y') + a(y')
y <- x'-(a/b)y'
x <- y'
*/

void euclid(long long a, long long b, long long *p){
    if(a < b)swap(a,b);
    if(b==0){
        p[0] = 1;
        p[1] = 0;
        return;
    }
    euclid(b, a%b, p);
    long long x = p[0] - (a/b)*p[1];
    long long y = p[1];
    p[1] = x; p[0] = y;
}

int main(){
    for(int i=1;i<=20;++i){
        long long p[2];
        euclid(MOD,i, p);
        d[i] = p[1];
    }
    scanf("%d",&n);
    cin >> s;
    for(int i=0;i<n;++i){
        cin >> f[i];
    }
    int sz = 1<<n;
    long long ans = 0;
    for(int i=0;i<sz;++i){
        int cnt = 0;
        int tmp = i;
        long long sum = 0;
        for(int k=0;k<n;++k){
            if(tmp&1){
                ++cnt;
                sum += f[k]+1LL;
            }
            tmp >>= 1;
        }
        if(sum > s)continue;
        long long ret = s - sum + n - 1;
        ret %= MOD;
        long long cur = 1;
        for(int k=1;k<n;++k){
            cur *= ret;
            cur %= MOD;
            cur *= d[k];
            cur %= MOD;
            --ret;
        }
        if(cnt%2==0)ans += cur;
        else ans -= cur;
        ans %= MOD;
    }
    if(ans < 0) ans += MOD;
    printf("%d\n", (int) ans);
    return 0;
}