# 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)```
```

## Costly Intervals

Given an array, your goal is to find, for each element, the largest subarray containing it whose cost is at least k. Specifically, let A = [A1, A2, . . . , An ] be an array of length n, and let be the subarray from index l to index r. Also, Let MAX( l, r ) be the largest number in Al. . . r. Let MIN( l, r ) be the smallest number in Al . . .r . Let OR( l , r ) be the bitwise OR of the

## The Strange Function

One of the most important skills a programmer needs to learn early on is the ability to pose a problem in an abstract way. This skill is important not just for researchers but also in applied fields like software engineering and web development. You are able to solve most of a problem, except for one last subproblem, which you have posed in an abstract way as follows: Given an array consisting

## Self-Driving Bus

Treeland is a country with n cities and n - 1 roads. There is exactly one path between any two cities. The ruler of Treeland wants to implement a self-driving bus system and asks tree-loving Alex to plan the bus routes. Alex decides that each route must contain a subset of connected cities; a subset of cities is connected if the following two conditions are true: There is a path between ever

## Unique Colors

You are given an unrooted tree of n nodes numbered from 1 to n . Each node i has a color, ci. Let d( i , j ) be the number of different colors in the path between node i and node j. For each node i, calculate the value of sum, defined as follows: Your task is to print the value of sumi for each node 1 <= i <= n. Input Format The first line contains a single integer, n, denoti

## Fibonacci Numbers Tree

Shashank loves trees and math. He has a rooted tree, T , consisting of N nodes uniquely labeled with integers in the inclusive range [1 , N ]. The node labeled as 1 is the root node of tree , and each node in is associated with some positive integer value (all values are initially ). Let's define Fk as the Kth Fibonacci number. Shashank wants to perform 22 types of operations over his tree, T

## Pair Sums

Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v