Square-Ten Tree| Tree
Task(hard)
The square-ten tree decomposition of an array is defined as follows:
- The lowest (0th) level of the square-ten tree consists of single array elements in their natural order.
- The kth level (starting from 1) of the square-ten tree consists of subsequent array subsegments of length 102k-1 in their natural order. Thus, the 1st level contains subsegments of length 102, the level contains subsegments of length , the level contains subsegments of length , etc.
Task
Given the borders of array subsegment [L,R], find its decomposition into a minimal number of nodes of a square-ten tree.
Input Format
The first line contains a single integer denoting L.
The second line contains a single integer denoting R.
Constraints
1<=L<=R<=1010
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 m 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 n(i.e., the compressed sequence block count).
- For each of the n subsequent lines, print 2 space-separated integers, ti and ci (ti>=0,ci>=1), meaning that the number appears consequently times in sequence . Blocks should be listed in the order they appear in the sequence. In other words, s1, s2,….,sc1 should be equal to , should be equal to t2, etc.
Sample Input 0
1
10
Sample Output 0
1
1 1
SOLUTION 1
def square_ten_tree_decomposition(L, R):
level_sizes = []
size = 1
# Determine all possible level sizes
while size <= R - L + 1:
level_sizes.append(size)
size *= 10
# Initialize k to the last index of level_sizes
k = len(level_sizes) - 1
segments = []
while k >= 0:
size = level_sizes[k]
start = (L - 1) // size
end = (R - 1) // size
count = end - start + 1
if count > 0:
segments.append((k, count))
L += count * size
k -= 1
# Compress the output
result = []
if segments:
prev_k, prev_count = segments[0]
for i in range(1, len(segments)):
current_k, current_count = segments[i]
if current_k == prev_k:
prev_count += current_count
else:
result.append((prev_count, prev_k))
prev_k = current_k
prev_count = current_count
result.append((prev_count, prev_k))
# Output the result
print(len(result))
for count, level in result:
print(count, level)
# Example usage
L = 1
R = 10
square_ten_tree_decomposition(L, R)
EXPLANATION STEPS
1.DFS for Subtree Sums: The DFS traversal calculates the sum of weights in each subtree efficiently.
2.Efficient Query Response: By precomputing the subtree sums, each query can be answered in constant time.
3.Edge Cases: Handle edge cases like single-node trees and ensuring correct indexing (1-based vs. 0-based).
