How can realize fair numbering for two counters/markers?

Question

Suppose Alice & Bob have to write from page 1 to page 200. According to this simple division, Alice will write 1, 2, 3... until 100. Bob will write 101, 102, 103... to 200. Bob will have to write a lot more digits than Alice! Let's say Alice & Bob are counters or markers for numbering, so how we can fairly split up this numbering task?

Considering two integers, start & end, for the starting and ending page numbers (inclusive) defining the range of pages that needs handwritten numbering.

• A page number has to be written by either Alice or Bob. They cannot jointly write one number.

• Page numbers are all decimal integers count from 1. The missing number of pages can start from page 1 or anywhere in the middle of the notes.

Input: There are multiple tests in each test case.

Line 1: Integer N, the number of tests to follow.

Following N lines: Each line has two integers, st ed, for the starting and ending page numbers (inclusive) defining the range of pages that needs handwritten numbering.

#Input examples
4       #N=4 it means 4 following lines
1 200
8 10
9 10
8 11

import sys
import math

n = int(input()) #1 ≤ N ≤ 200
for i in range(n): #1 ≤ start < end ≤ 10,000,000
    start, end = [int(j) for j in input().split()]

Output:

N Lines: For the test in the input, It should be written the corresponding last page number that should be responsible by Alice to write the needed page number on.

#Output examples
118
9
9
9

I was trying to get inspired by this post on fair casting dice unsuccessfully. I also was wondering the solution is far from Checking number of elements for Counter .

Answer 1

First thing to note is this cannot be done, consider the sequence 99, 100. You cannot split this up fairly. In saying that you can get pretty close +- 1 digit, this assumes you always start counting from 1.

start = 1
end = 200

bobs_numbers = []
alices_numbers = []
count = 0

for i in range(end, start - 1, -1):
    if count > 0:
        bobs_numbers.append(i)
        count -= len(str(i))
    else:
        alices_numbers.append(i)
        count += len(str(i))

print(bobs_numbers, alices_numbers, count)

Answer 2

This is an answer to the initial question. Since the question has been changed, I posted another answer for the new question.

The initial question was: Partition the set [1, 200] into two subsets such that the total number of digits in one subset is as close to possible to the total number of digits in the other subset.

Since user Mitchel Paulin already gave a straightforward iterative solution, let me give an arithmetic solution.

Counting the number of digits

First, let's count the total number of digits we want to split between Alice and Bob:

• there are 9 numbers with 1 digit;
• there are 90 numbers with 2 digits;
• there are 101 numbers with 3 digits.

Total: 492 digits.

We want to give 246 digits to Alice and 246 digits to Bob.

How to most simply get 246 digit by summing up numbers with 1, 2 and 3 digits?

246 = 3 * 82.

Let's give 82 numbers with 3 digits to Bob, and all the other numbers to Alice.

Finally Bob can handle numbers [119, 200] and Alice can handle numbers [1, 118].

Generalizing to any range [1, n]

Counting the numbers of numbers with each possible number of digits should be O(log n).

Dividing by 2 to get the number of digits for Bob is O(1).

Decomposing this number using dynamic programming is linear in the maximum number of digits, i.e., O(log n) space and time (this is exactly the coin change problem).

Transforming this decomposition into a union of ranges is straightforward, and linear in the maximum number of digits, so again O(log n). Deducing the ranges for Alice by "subtracting" Bob's ranges from [1, n] is also straightforward.

Conclusion: the algorithm is O(log n) space and time, as opposed to Mitchel Paulin's O(n) algorithm. The output is also logarithmic instead of linear, since it can be written as a union of ranges, instead of a long list.

This algorithm is a bit more complex to write, but the output being in the form of ranges mean that Alice and Bob won't bother each other too much by writing adjacent pages, which they would do a lot with the simpler algorithm (which mostly alternates between giving a number to Bob and giving a number to Alice).

Answer 3

Since the question has changed, this is an answer the new question.

The new question is: Given a range [a, b], find number m such that the total number of digits in range [a, m] is as close as possible to the number of digits in range [m+1, b].

Algorithm explanation

The algorithm is simple: Start with m = (a + b) / 2, count the digits, then move m to the right or to the left to adjust.

To count the total number of digits in a range [1, n], we first count the number of unit digits (which is n); then add the number of tens digits (which is n - 9; then add the number of hundreds digits (which is n - 99); etc.

To count the total number of digits in a range [a, b], we take the difference between the total number of digits in ranges [1, b] and [1, a-1].

Note that the number of digits of a given number n > 1 is given by any of the two expressions math.ceil(math.log10(n)) and len(str(n)). I used the former in the code below. If you have a phobia of logarithms, you can replace it with the latter; in which case import math is no longer needed.

Code in python

import math

def count_digits_from_1(n):
    power_of_ten = math.ceil(math.log10(n))
    total_digits = 0
    for i in range(1, power_of_ten+1):
        digits_at_pos_i = n - (10**(i-1) - 1)
        total_digits += digits_at_pos_i
    return total_digits

def count_digits(a, b):
    if a > 2:
        return count_digits_from_1(b) - count_digits_from_1(a-1)
    else:
        return count_digits_from_1(b) - (a - 1)   # assumes a >= 1

def share_digits(a, b):
    total_digits = count_digits(a, b)
    m = (a + b) // 2
    alices_digits = count_digits(a, m)
    bobs_digits = total_digits - alices_digits

    direction = 1 if alices_digits < bobs_digits else -1

    could_be_more_fair = True
    while (could_be_more_fair):
        new_m = m + direction
        diff = math.ceil(math.log10(new_m))
        new_alices_digits = alices_digits + direction * diff
        new_bobs_digits = bobs_digits - direction * diff
        if abs(alices_digits - bobs_digits) > abs(new_alices_digits - new_bobs_digits):
            alices_digits = new_alices_digits
            bobs_digits = new_bobs_digits
            m = new_m
        else:
            could_be_more_fair = False

    return ((a, m), (m+1, b))

if __name__=='__main__':
    for (a, b) in [(1, 200), (8, 10), (9, 10), (8, 11)]:
        print('{},{}  --->  '.format(a,b), end='')
        print(share_digits(a, b))

Output:

1,200  --->  ((1, 118), (119, 200))
8,10  --->  ((8, 9), (10, 10))
9,10  --->  ((9, 9), (10, 10))
8,11  --->  ((8, 10), (11, 11))

Remark: This code uses the assumption 1 <= a <= b.

Performance analysis

Function count_digits_from1 executes in O(log n); its for loop iterates over the position of the digits to count the number of unit digits, then the number of tens digits, then the number of hundreds digits, etc. There are log10(n) positions.

The question is: how many iterations will the while loop in share_digits have?

If we're lucky, the final value of m will be very close to the initial value (a+b)//2, so the number of iterations of this loop might be O(1). This remains to be proven.

If the number of iterations of this loop is too high, the algorithm could be improved by getting rid of this loop entirely, and calculating the final value of m directly. Indeed, replacing m with m+1 or m-1 changes the difference abs(alices_digits - bobs_digits) by exactly two times the number of digits of m+1 (or m-1). Therefore, the final value of m should be given approximately by:

new_m = m + direction * abs(alices_digits - bobs_digits) / (2 * math.ceil(math.log10(m)))