UVA - 12627 Erratic Expansion

Observation

From row8 to row1, We can find an interesting fact : if we assign id 1 ~ 8 to row 8 ~ row 1, respectfully. Let’s say the red balloon in id i is bal[i]. We can get a interesting formula bal[i] = bal[i/2]*2.

Also, $\sum^{2^n}bal[i]$ can be respresent as $3^{n-1}$.

Intuition

We can also see $\sum^{M}bal[i]$ in a very different way that can provide time complexity to O(log(n)): Use $\sum^{2^n}bal[i] = 3^{n-1}$

That is, compute $\sum^{M}bal[i] = \sum^{2^{x_1}}bal[i] + \sum^{2^{x_2}}bal[i] + … + \sum^{2^{x_k}}bal[i]$, where $M=2^{x_1}+2^{x_2}+…+2^{x_k}$.

Sample Code

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

#define ll long long
#define INF 99999999

int main()
{
    vector<ll> dp(31, 1);
    for (int i = 1; i <= 30; i++)
        dp[i] = dp[i - 1] * 3;
    int n, tt = 0;
    cin >> n;
    while (n--)
    {
        ll k, a, b;
        cin >> k >> a >> b;
        a = (ll)(1 << k) - a + 1;
        b = (ll)(1 << k) - b;
        ll a1 = 0, b1 = 0, t = 1;
        for (int i = 30; i >= 0; i--)
        {
            if ((a >> i) & 1)
            {
                a1 += dp[i] * t;
                t = t << 1;
            }
        }
        t = 1;
        for (int i = 30; i >= 0; i--)
        {
            if ((b >> i) & 1)
            {
                b1 += dp[i] * t;
                t = t << 1;
            }
        }
        cout << "Case " << ++tt << ": " << (a1 - b1) << endl;
    }
}