My Hackerrank Solution of Square-Ten Tree

click here to the problem description.

We can divide this “tree traversal” into two halves: one half is from L value to the minimum value of same digit count of R value, i.e. R = 1234, minimum value is 1000, they have same digit count. This step we keep counting each level of the tree. The other half is the same, it is counting from the minimum, or say it as middle number, to R value. this step is also a pass of single direction. At each level we could simply cut the string as the tree count of each level.

Some tricks like 1000 - 32 = 1 + 999 - 32 = 1 + 9[9-3=6][9-2=7] (number with all 9 minus other number does not carry), middle number is 1 concatenate length of [R - 1] 0s are used to avoid big number operations, which is a performance hit.

In some cases, the middle number is at the middle of the same tree level, which will cause the count of the same level split into two halves of level counter. So I need merge them to get the right answer and since I store count number as string, this merging step demand a big number adding operation.

Python 3 Solution, 25% timeout

# Enter your code here. Read input from STDIN. Print output to STDOUT
import math
l = input()
r = input()
if len(l) == len(r) :
    if l == r :
        print(1)
        print(0, 1)
        exit()
    while l[0] == r[0]:
        l = l[1:]
        r = r[1:]
a = [0] * 30
b = [0] * 30

#ir = int(r)
mid = '1' + '0' * (len(r) - 1)


if len(mid) == len(l) and mid != l:
    r = str(int(r[0]) - int(l[0])) + r[1:]
    l = l[1:]
#print(mid)
il = int(l)
imid = int(mid)

level = 0
diff = str(imid - il + 1)
pow = .5

while diff != '0' and diff != '' :

    a[level] = int(diff[-math.ceil(pow):])
    diff = diff[:-math.ceil(pow)]
    # print(cut, diff, level)
    pow = pow * 2
    level += 1

level = 0
diff = str(int(r[0]) - int(mid[0])) + r[1:]#str(ir - mid)
pow = .5
while diff != '0' and diff != '' :
    b[level] = int(diff[-math.ceil(pow):])#diff % cut
    diff = diff[:-math.ceil(pow)]
    pow = pow * 2
    level += 1

for i in reversed(range(20)) :
    if 0 != a[i] and 0 != b[i] :
        a[i] += b[i]
        b[i] = 0
        break
    elif 0 != a[i] or 0 != b[i] :
        break
n = 0

for i in range(20) :
    if 0 != a[i] :
        n += 1
    if 0 != b[i]:
        n += 1
print(n)
for i in range(20) :
    if 0 != a[i] :
        print(i, a[i])
for i in reversed(range(20)) :
    if 0 != b[i] :
        print(i, b[i])

I used to rely Python’s big number feature, but it is getting too slow dealing with number of length 1e6, also, string operations are too slow to break the time limit. Then I implemented the same logic in C++, and it passed without obscure wrong answer. From several big secs to milisecs, Python sucks.

C++ Solution, passed all testcases

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

void zreduce(string& s) {
    int i = 0;
    while (i < s.size() && '0' == s[i])
        i++;
    if (i == s.size())
        s = "0";
    else
        s = s.substr(i);
}
string add(const string& a, const string& b) {
    auto maxlen = a.size() > b.size() ? a.size() : b.size();
    string sum(maxlen + 1, '0');

    int i = a.size() - 1;
    int j = b.size() - 1;
    auto k = sum.size();
    char carry = 0;
    while (k--) {
        auto ac = i >= 0 ? a[i] : '0';
        auto bc = j >= 0 ? b[j] : '0';
        auto half = carry + ac + bc - '0';
        //cout << i << ' '<< j << endl;
        if (half > '9') {
            carry = 1;
            half -= 10;
        } else
            carry = 0;
        sum[k] = half;

        i--;
        j--;
    }
    //cout << sum << endl;
    zreduce(sum);
    return sum;
}
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */

    string l, r;
    cin >> l >> r;
    //cout << l.size() << ' ' << r.size() << endl;
    if (l.size() == r.size()) {
        int i = 0;
        for (; i < l.size() && l[i] == r[i]; i++)
            ;
        if (i == l.size()) {
            cout << "1\n0 1\n";
            return 0;
        }
        l = l.substr(i);
        r = r.substr(i);
        r[0] -= (l[0] - '0');
        l[0] = '0';
        zreduce(l);
    }


    string mid(r.size(), '0');

    vector<pair<string, int> > a, b;
    mid[0] = '1';

    string diff(r.size() - 1, '9');
    //cout << diff << endl;
    for (int i = l.size() - 1, j = diff.size() - 1; i >= 0; i--, j--)
        diff[j] -= (l[i] - '0');

    diff = add(diff, "2");
    //cout << diff << endl;
    auto pow = .5;
    int level = 0;
    while ("" != diff) {
        auto len = diff.size() > ceil(pow) ? ceil(pow) : diff.size();
        auto s = diff.substr(diff.size() - len, ceil(len));
        zreduce(s);
        if ("0" != s)
            a.push_back(make_pair(s, level));
        diff = diff.substr(0, diff.size() - len);
        pow *= 2;
        level++;
    }

    diff = r;
    diff[0]--;
    zreduce(diff);
    //cout << diff << endl;
    pow = .5;
    level = 0;
    while ("" != diff) {
        auto len = diff.size() > ceil(pow) ? ceil(pow) : diff.size();
        auto s = diff.substr(diff.size() - len, ceil(len));
        zreduce(s);
        if ("0" != s)
            b.push_back(make_pair(s, level));
        diff = diff.substr(0, diff.size() - len);
        pow *= 2;
        level++;
    }

    if (a.size() > 0 && b.size() > 0 && a[a.size() - 1].second == b[b.size() - 1].second) {
        //cout << a[a.size() - 1].first << endl << b[b.size() - 1].first << endl;
        a[a.size() - 1].first = add(a[a.size() - 1].first, b[b.size() - 1].first);
        b.pop_back();
    }
    cout << a.size() + b.size() << '\n';
    for (auto i : a) {
        cout << i.second << ' ' << i.first << '\n';
    }

    for (int i = b.size(); i--; ) {
        cout << b[i].second << ' ' << b[i].first << '\n';
    }
    return 0;
}