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 :



title-img


                            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

Subsequence Weighting

A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. You are given a sequence A in which every element is a pair of integers i.e A = [(a1, w1), (a2, w2),..., (aN, wN)]. For a subseqence B = [(b1, v1), (b2, v2), ...., (bM, vM)] of the given sequence : We call it increasing if for every i (1 <= i < M ) , bi < bi+1. Weight(B) =

View Solution →

Kindergarten Adventures

Meera teaches a class of n students, and every day in her classroom is an adventure. Today is drawing day! The students are sitting around a round table, and they are numbered from 1 to n in the clockwise direction. This means that the students are numbered 1, 2, 3, . . . , n-1, n, and students 1 and n are sitting next to each other. After letting the students draw for a certain period of ti

View Solution →

Mr. X and His Shots

A cricket match is going to be held. The field is represented by a 1D plane. A cricketer, Mr. X has N favorite shots. Each shot has a particular range. The range of the ith shot is from Ai to Bi. That means his favorite shot can be anywhere in this range. Each player on the opposite team can field only in a particular range. Player i can field from Ci to Di. You are given the N favorite shots of M

View Solution →

Jim and the Skyscrapers

Jim has invented a new flying object called HZ42. HZ42 is like a broom and can only fly horizontally, independent of the environment. One day, Jim started his flight from Dubai's highest skyscraper, traveled some distance and landed on another skyscraper of same height! So much fun! But unfortunately, new skyscrapers have been built recently. Let us describe the problem in one dimensional space

View Solution →

Palindromic Subsets

Consider a lowercase English alphabetic letter character denoted by c. A shift operation on some c turns it into the next letter in the alphabet. For example, and ,shift(a) = b , shift(e) = f, shift(z) = a . Given a zero-indexed string, s, of n lowercase letters, perform q queries on s where each query takes one of the following two forms: 1 i j t: All letters in the inclusive range from i t

View Solution →

Counting On a Tree

Taylor loves trees, and this new challenge has him stumped! Consider a tree, t, consisting of n nodes. Each node is numbered from 1 to n, and each node i has an integer, ci, attached to it. A query on tree t takes the form w x y z. To process a query, you must print the count of ordered pairs of integers ( i , j ) such that the following four conditions are all satisfied: the path from n

View Solution →