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

Task
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++ :



/*
*/

//#pragma comment(linker, "/STACK:16777216")
#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 yn askfhwqriuperikldjk
#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;
}

vector<int> add(vector<int> a, vector<int> b)
{
	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);
			v1 = add(v1, v2);
			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)
	{		
		String[] input = readInput();

		List<Group> groups = solve(input[0], input[1]);
		
		//Util.validate(strL, strR, groups);

		printGroups(groups);	
		
	}

	public static String[] readInput()
	{
    	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>();

		addGroupsL(tens, dif, groups);
		
		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);
		
		addGroupsR(tens, groups, 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;
			addGroup(groups, dif3, b, e, t/2);
			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;
			addGroup(groups, dif, b, e, t/2);
			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) {
					current.source = add(current.source, g.source);
				} else {
					result.add(current);
					current = g;					
				}
			}
		}
		
		if (current != null) {
			result.add(current);
		}
		
		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);
			groups.add(group);
		}
	}

	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

Square-Ten Tree

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

View Solution →

Balanced Forest

Greg has a tree of nodes containing integer data. He wants to insert a node with some non-zero integer value somewhere into the tree. His goal is to be able to cut two edges and have the values of each of the three new trees sum to the same amount. This is called a balanced forest. Being frugal, the data value he inserts should be minimal. Determine the minimal amount that a new node can have to a

View Solution →

Jenny's Subtrees

Jenny loves experimenting with trees. Her favorite tree has n nodes connected by n - 1 edges, and each edge is ` unit in length. She wants to cut a subtree (i.e., a connected part of the original tree) of radius r from this tree by performing the following two steps: 1. Choose a node, x , from the tree. 2. Cut a subtree consisting of all nodes which are not further than r units from node x .

View Solution →

Tree Coordinates

We consider metric space to be a pair, , where is a set and such that the following conditions hold: where is the distance between points and . Let's define the product of two metric spaces, , to be such that: , where , . So, it follows logically that is also a metric space. We then define squared metric space, , to be the product of a metric space multiplied with itself: . For

View Solution →

Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

View Solution →

Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

View Solution →