# Square-Ten Tree

### Problem Statement :

```The square-ten tree decomposition of an array is defined as follows:

The lowest () level of the square-ten tree consists of single array elements in their natural order.
The  level (starting from ) of the square-ten tree consists of subsequent array subsegments of length  in their natural order. Thus, the  level contains subsegments of length , the  level contains subsegments of length , the  level contains subsegments of length , etc.
In other words, every  level (for every ) of square-ten tree consists of array subsegments indexed as:

Level  consists of array subsegments indexed as .
The image below depicts the bottom-left corner (i.e., the first  array elements) of the table representing a square-ten tree. The levels are numbered from bottom to top:

4x128 square-ten tree table

Given the borders of array subsegment , find its decomposition into a minimal number of nodes of a square-ten tree. In other words, you must find a subsegment sequence  such as  for every , , , where every  belongs to any of the square-ten tree levels and  is minimal amongst all such variants.

Input Format

The first line contains a single integer denoting .
The second line contains a single integer denoting .

Constraints

The numbers in input do not contain leading zeroes.
Output Format

As soon as array indices are too large, you should find a sequence of  square-ten tree level numbers, , meaning that subsegment  belongs to the  level of the square-ten tree.

Print this sequence in the following compressed format:

On the first line, print the value of  (i.e., the compressed sequence block count).
For each of the  subsequent lines, print  space-separated integers,  and  (, ), meaning that the number  appears consequently  times in sequence . Blocks should be listed in the order they appear in the sequence. In other words,  should be equal to ,  should be equal to , etc.
Thus  must be true and  must be true for every . All numbers should be printed without leading zeroes.```

### Solution :

```                            ```Solution in C :

In C++ :

/*
*/

#define _CRT_SECURE_NO_WARNINGS

#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd

#define eps 1e-9
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 256

using namespace std;

const int INF = 1e9;
const int N = 500331;

string st1, st2;

vector<int> levels;
vector<pair<int, string> > ans;

bool not_larger(vector<int> &v1, vector<int> &v2)
{
if (v1.size() != v2.size())
{
return v1.size() < v2.size();
}
for (int i = v1.size() - 1; i >= 0; --i)
{
if (v1[i] != v2[i])
return v1[i] < v2[i];
}
return true;
}

vector<int> get_id(string st)
{
vector<int> res;
reverse(st.begin(), st.end());
for (int i = 0; i < st.size(); i++)
{
res.push_back(st[i] - 48);
}
return res;
}

string eval(vector<int> v)
{
string res;
res.resize(v.size());
for (int i = 0; i < v.size(); i++)
res[i]=(v[i] + 48);
reverse(res.begin(), res.end());
return res;
}

vector<int> get_vec(vector<int> v, int ps)
{
while (v.size() <= ps)
v.push_back(0);
v.push_back(0);
v[ps]++;
int ost = 0;
for (int i = 0; i < v.size(); i++)
{
v[i] += ost;
ost = v[i] / 10;
v[i] %= 10;
}
while (v.size()>1 && v.back() == 0)
v.pop_back();
return v;
}

vector<int> normalize(vector<int> v, int shi)
{
vector<int> res;
for (int i = shi; i < v.size(); i++)
res.push_back(v[i]);
if (res.size() == 0)
res.push_back(0);
return res;
}

vector<int> get_dif(vector<int> a, vector<int> b)
{
while (b.size() < a.size())
b.push_back(0);
int ost = 0;
for (int i = 0; i < a.size(); ++i)
{
a[i] -= b[i];
a[i] -= ost;
if (a[i] < 0)
ost = 1, a[i] += 10;
else
ost = 0;
}
while (a.size()>1 && a.back() == 0)
a.pop_back();
return a;
}

vector<int> renorm(vector<int> v)
{
int ost = 0;
for (int i = 0; i < v.size(); i++)
{
v[i] += ost;
ost = v[i] / 10;
v[i] %= 10;
}
v.push_back(ost);
while (v.size()>1 && v.back() == 0)
v.pop_back();
return v;
}

vector<int> get_next(vector<int> v, int ps)
{
while (v.size() <= ps)
v.push_back(0);
int shit = 0;
for (int i = 0; i < ps; i++)
{
if (v[i] != 0)
shit = 1;
}
if (shit == 0)
{
return renorm(v);
}
//cout << v.size() << "%" << ps << " " << endl;
v[ps]++;
for (int i = 0; i < ps; i++)
v[i] = 0;
return renorm(v);
}

vector<int> get_next2(vector<int> v, int ps)
{
while (v.size() <= ps)
v.push_back(0);
int shit = 0;
for (int i = 0; i < ps; i++)
{
if (v[i] != 0)
shit = 1;
}
shit = 1;
if (shit == 0)
{
return renorm(v);
}
v[ps]++;
for (int i = 0; i < ps; i++)
v[i] = 0;
return renorm(v);
}
vector<int> min1(vector<int> v)
{
int q = 0;
while (v[q] == 0)
{
v[q] = 9;
++q;
}
v[q]--;
while (v.size() > 1 && v.back() == 0)
v.pop_back();
return v;
}

void show(vector<int> v)
{
reverse(v.begin(), v.end());
for (int i = 0; i < v.size(); i++)
cout << v[i];
cout << endl;
}

void norm_suf(vector<int> &v, int suf)
{
while (v.size() < suf)
v.push_back(0);
for (int i = 0; i < suf; i++)
v[i] = 0;
while (v.size()>1 && v.back() == 0)
v.pop_back();
return;
}

{
while (a.size() < b.size())
a.push_back(0);
while (b.size() < a.size())
b.push_back(0);
int ost = 0;
for (int i = 0; i < a.size(); i++)
{
a[i] = a[i] + b[i] + ost;
ost = a[i] / 10;
a[i] %= 10;
}
a.push_back(ost);
while (a.size()>1 && a.back() == 0)
a.pop_back();
return a;
}

vector<pair<int, string> > compress(vector<pair<int, string> > v)
{
vector<pair<int, string> > res;
pair<int, string> cur;
cur = v[0];
for (int i = 1; i < v.size(); i++)
{
if (v[i].first == v[i - 1].first)
{
string temp1 = cur.second;
string temp2 = v[i].second;
vector<int> v1 = get_id(temp1);
vector<int> v2 = get_id(temp2);
cur.second = eval(v1);
}
else
{
res.push_back(cur);
cur = v[i];
}
}
res.push_back(cur);
return res;
}
int main(){
//freopen("fabro.in","r",stdin);
//freopen("fabro.out","w",stdout);
//freopen("F:/in.txt", "r", stdin);
//freopen("F:/output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
//cin.tie(0);

cin >> st1 >> st2;

/*	st1 = "0";
st2 = "1";
for (int i = 1; i <= 1000000; i++)
st2 += "0";
*/
levels.push_back(0);
for (int i = 0; i <= 20; i++)
{
levels.push_back(1 << i);
}

vector<int> v1 = get_id(st1);
v1 = min1(v1);
vector<int> v2 = get_id(st2);

for (int i = 0; i+1 < levels.size(); i++)
{
//cout << i << " " << clock()*1.0 / CLOCKS_PER_SEC << endl;

vector<int> next1 = get_next(v1, levels[i+1]);
vector<int> next2 = v2;
/*cout << "#" << i << endl;
if (i < 5)
{
show(next1);
show(next2);
show(v1);
}*/
if (not_larger(next2, next1))
continue;
vector<int> V = get_dif(next1, v1);
//cout << "@@" << endl;
//show(V);
//cout << "%" << i << " " << clock()*1.0 / CLOCKS_PER_SEC << endl;
V = normalize(V, levels[i]);
//cout << "%" << i << " " << clock()*1.0 / CLOCKS_PER_SEC << endl;

if (V.size() > 1 || V[0] != 0)
{
ans.push_back(make_pair(i, eval(V)));
v1 = next1;
}
v1 = next1;
}
for (int i = levels.size()-2; i >=0; i--)
{
vector<int> next1 = get_next2(v1, levels[i+1]);
vector<int> next2 = v2;

norm_suf(next2, levels[i]);

/*cout << "#" << i << endl;
if (i < 5)
{
show(next1);
show(next2);
show(v1);
}
*/
if (not_larger(next2, next1))
next1 = next2;
if (!not_larger(v1, next1))
continue;

vector<int> V = get_dif(next1, v1);
V = normalize(V, levels[i]);

if (V.size() > 1 || V[0] != 0)
{
ans.push_back(make_pair(i, eval(V)));
v1 = next1;
}
}

vector<int> V = get_dif(v2, v1);

if (V.size()>1 || V[0] != 0)
ans.push_back(make_pair(0, eval(V)));

ans = compress(ans);

cout << ans.size() << endl;

for (int i = 0; i < ans.size(); i++)
{
cout << ans[i].first << " " << ans[i].second << endl;
}

cin.get(); cin.get();
return 0;
}

In C :

#include<stdio.h>

int powtwo(int x)
{
if (x < 0)
return 0;
return 1 << x;
}

void subtract(char *src, char *dst, int start, int end, int borrow)
{
while (start < end)
{
dst[start] += borrow;
borrow = 0;
if (src[start] < dst[start])
{
src[start] += 10;
borrow++;
}
src[start] -= dst[start];
dst[start] = 0;
start++;
}
}

void add(char *src, char *dst, int start, int end)
{
int carry = 0;
while (start < end || carry)
{
src[start] += dst[start] + carry;
dst[start] = 0;
carry = src[start] / 10;
src[start] %= 10;
start++;
}
}

int main()
{
char a[1048577] = {0}, b[1048577] = {0};
int A, B, i, j, k, l, m, n;
short int ansA[25] = {0}, ansB[25] = {0}, countA = 0, countB = 0;
scanf("%s%s", a, b);
for (A = -1; a[++A]; a[A] -= '0');
for (B = -1; b[++B]; b[B] -= '0');
for (i = -1; ++i < A >> 1; a[i] ^= a[A - i - 1] ^= a[i] ^= a[A - i - 1]);
for (i = -1; ++i < B >> 1; b[i] ^= b[B - i - 1] ^= b[i] ^= b[B - i - 1]);
if (A == B)
{
while (A && a[A - 1] == b[B - 1])
a[--A] = b[--B] = 0;
}
else
{
while (A < B)
a[A++] = 0;
}
if (!A)
{
printf("1\n0 1\n");
return 0;
}
n = m = 1;
while (A > n)
{
n <<= 1;
m++;
}
a[0] -= 2;
l = 0;
for (i = -1; ++i < m - 1;)
{
k = powtwo(i) - powtwo(i - 1);
for (j = -1; ++j < k; l++)
{
a[l] = 9 - a[l];
a[l + 1] -= a[l] / 10;
a[l] %= 10;
ansA[i] = ansA[i] || a[l];
ansB[i] = ansB[i] || b[l];
}
countA += ansA[i];
countB += ansB[i];
}
i = powtwo(m - 2);
subtract(b, a, i, A, 1);
for (i--; ++i < A;)
ansB[m - 1] = ansB[m - 1] || b[i];
countB += ansB[--m];
while (!ansA[m] && !ansB[m])
m--;
if (ansA[m] == ansB[m])
{
ansA[m] = 0;
countA--;
add(b, a, powtwo(m - 1), powtwo(m));
}
printf("%d", countA + countB);
for (i = -1; ++i <= m;)
{
if (ansA[i])
{
printf("\n%d ", i);
k = powtwo(i);
j = powtwo(i - 1);
while (!a[--k]);
while (k >= j)
printf("%c", '0' + a[k--]);
}
}
while (m >= 0 && !ansB[m])
m--;
if (m >= 0)
{
printf("\n%d ", m);
k = powtwo(m);
j = powtwo(m - 1);
while (!b[k])
k--;
while (k >= j)
printf("%c", '0' + b[k--]);
while (m--)
{
if (ansB[m])
{
printf("\n%d ", m);
k = powtwo(m);
j = powtwo(m - 1);
while (!b[--k]);
while (k >= j)
printf("%c", '0' + b[k--]);
}
}
}
return 0;
}

In Java :

import java.util.*;

public class Solution {

public static class Group {
public byte[] source;
public int power;

public Group(byte[] source, int power) {
this.source = source;
this.power = power;
}

public void print() {

System.out.print(powerToLevel(power));
System.out.print(" ");

boolean nonZero = false;
for(int i = 0; i < source.length; i++) {
int d = source[i];
if (d != 0) nonZero = true;
if (nonZero) System.out.print(source[i]);
}

System.out.println();
}

}

public static void main(String[] args)
{

List<Group> groups = solve(input[0], input[1]);

//Util.validate(strL, strR, groups);

printGroups(groups);

}

{
try (Scanner in = new Scanner(System.in) ) {
String L = in.nextLine().trim();
String R = in.nextLine().trim();
return new String[]{L, R};
}
}

public static void printGroups(List<Group> groups)
{
System.out.println(groups.size());
for(Group group: groups) {
group.print();
}
}

public static List<Group> solve(String strL, String strR)
{
byte[] L = toArray(strL, strR.length() + 1);
byte[] R = toArray(strR, strR.length() + 1);

subtract1(L);

//System.out.println(Util.toStr(L) + " " + Util.toStr(R));

eraseCommonPrefix(L, R);

int tens = tens(realLength(R));

byte[] upper = findUpper(L, tens);

byte[] dif = new byte[upper.length];
subtract(upper, L, dif);

List<Group> groups = new ArrayList<Group>();

byte[] lower = findLower(R, tens);

byte[] dif2 = new byte[R.length];
subtract(lower, upper, dif2);

addGroup(groups, dif2, 0, R.length - tens, tens);

byte[] dif3 = new byte[R.length];
subtract(R, upper, dif3);

return mergeSimilar(groups);
}

public static int powerToLevel(int p) {

int count = 0;
while(p > 0) {
p /= 2;
count++;
}
return count;

}

public static void addGroupsR(int tens, List<Group> groups, byte[] dif3)
{
int c = tens;
int t = tens;
while(t > 0) {
int tu = Math.max(t/2, 1);
int b = dif3.length - 1 - (c - 1);
int e = dif3.length - 1 - (c - tu) + 1;
c -= tu;
t /= 2;
}
}

public static byte[] findLower(byte[] R, int tens)
{
byte[] lower = new byte[R.length];
System.arraycopy(R, 0, lower, 0, R.length - tens);
return lower;
}

public static void addGroupsL(int tens, byte[] dif, List<Group> groups)
{
int c = 0;
int t = 1;
while(t <= tens) {
int tu = Math.max(t / 2, 1);
int b = dif.length - 1 - (c+tu-1);
int e = dif.length - 1 - (c) + 1;
c += tu;
t *= 2;
}
}

public static void eraseCommonPrefix(byte[] L, byte[] R)
{
assert(L.length == R.length);

for(int i = 0; i < L.length; i++) {
if (L[i] == R[i]) {
L[i] = 0;
R[i] = 0;
} else {
break;
}
}
}

public static byte[] findUpper(byte[] L, int tens)
{
byte[] upper = new byte[L.length + 1];

boolean nonZero = false;
for(int i = 0; i < tens; i++) {
int li = L.length - 1 - i;
if (li >= 0 && L[li] > 0) {
nonZero = true;
}
}

int carry = nonZero ? 1 : 0;
for(int i = tens; i < upper.length; i++) {
byte s = 0;
int lindex = L.length - 1 - i;
if (lindex >= 0) {
s = L[lindex];
}
int sum = s + carry;
upper[upper.length - 1 - i] = (byte)(sum % 10);
carry = sum / 10;
}

return upper;
}

public static int realLength(byte[] r)
{
int i;
for(i = 0; i < r.length; i++) {
if (r[i] != 0) {
break;
}
}

return r.length - i;
}

public static List<Group> mergeSimilar(List<Group> src)
{
List<Group> result = new ArrayList<Group>();

Group current = null;
for(int i = 0; i < src.size(); i++) {
Group g = src.get(i);
if (null == current) {
current = g;
} else {
if (current.power == g.power) {
} else {
current = g;
}
}
}

if (current != null) {
}

return result;
}

public static void addGroup(List<Group> groups, byte[] dif, int b, int e, int power)
{
if (!allZeroes(dif, b, e)) {
Group group = new Group(createCopy(dif, b, e), power);
}
}

public static byte[] createCopy(byte[] dif, int b, int e)
{
byte[] result = new byte[e - b];
System.arraycopy(dif, b, result, 0, e - b);
return result;
}

public static boolean allZeroes(byte[] dif, int b, int e)
{
for(int i = b; i < e; i++) {
if (dif[i] != 0)
return false;
}
return true;
}

public static byte[] add(byte[] A, byte[] B)
{
int l = Math.max(A.length, B.length) + 1;

byte[] C = new byte[l];

int carry = 0;
for(int i = 0; i < l; i++) {
int ia = A.length - 1 - i;
int ib = B.length - 1 - i;
int a = ia >= 0 ? A[ia] : 0;
int b = ib >= 0 ? B[ib] : 0;
int c = a + b + carry;
carry = c / 10;

int ic = C.length - 1 - i;
C[ic] = (byte)(c % 10);
}

return C;

}

public static void subtract(byte[] A, byte[] B, byte[] C)
{

int borrow = 0;
for(int i = 0; i < A.length; i++) {
int a = A[A.length - 1 - i] - borrow;

int b;
if (i < B.length)
b = B[B.length - 1 - i];
else
b = 0;

if (b > a) {
borrow = 1;
a += 10;
} else {
borrow = 0;
}

C[C.length - 1 - i] = (byte)(a - b);
}

}

/**
* return largest x such that 10^x <= s
*/
public static int tens(int len)
{
int x = 1;
int c = len - 1;
while(c > 0) {
c /= 2;
x *= 2;
}
return x/2;
}

public static byte[] toArray(String s, int len)
{
byte[] result = new byte[len];
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(s.length() - 1 - i);
assert(c >= '0' && c <= '9');
int d = c - '0';
result[result.length - 1 - i] = (byte)d;
}
return result;
}

/**
* s = all zeroes not allowed
*/
public static void subtract1(byte[] s)
{
for(int i = s.length - 1; i >= 0; i--) {
int d = s[i];
if (0 == d) {
s[i] = 9;
} else {
s[i]--;
break;
}
}
}

}

In python3 :

# work with big numbers as strings
L = input()
R = input()

# look for largest possible level
d = len(R)
level = 0
n = 1
tree = [n] # chunk dimension
while d >= n + 1:
tree.append(n)
level += 1
n = 2 ** level

# go backwards from largest level
def breakdown(N, k):
if k == 0:
return [int(N)]

div = tree[k]
chunks = breakdown(N[-div:], k - 1)
chunks.append(N[:-div].lstrip('0') or 0)
return chunks

divL = breakdown(L, level)
divR = breakdown(R, level)
seq = []

# add up to higher level for L
carry = 0
for k, n in enumerate(map(int, divL)):
if k == 0:
carry = -1 # add up lowest number

n += carry
carry = 0

if k < level:
if n > 0:
n = 10 ** tree[k] - n
carry = 1
elif n < 0:
n = 1 # if lowest was zero

seq.append((k, n))

# sum up last level of L and R
if n != 0:
divR[k] = int(divR[k]) - n
while divR[-1] == 0:
del divR[-1]
n = seq.pop()[1]
if n != 0:
divR[-1] = int(divR[-1]) + n

# add R in reversed order
seq.extend(reversed(list(enumerate(divR))))

# exclude empty levels
seq = [s for s in seq if s[1] != 0]
print(len(seq))

for s in seq:
print(*s)```
```

## View More Similar Problems

Given a pointer to the head of a linked list, insert a new node before the head. The next value in the new node should point to head and the data value should be replaced with a given value. Return a reference to the new head of the list. The head pointer given may be null meaning that the initial list is empty. Function Description: Complete the function insertNodeAtHead in the editor below

## Insert a node at a specific position in a linked list

Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is e

## Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

## Print in Reverse

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing