如何计算具有特定属性的大A和B之间的整数？

Question

在编程竞赛中,以下模式出现在很多任务中:

给定数字A和B很大(可能是20个十进制数字或更多),确定具有特定属性P的A≤X≤B的整数X

SPOJ有许多这样的任务用于练习.

有趣的属性的例子包括:

• "X的数字总和是60"
• "X仅包含数字4和7"
• "X是回文",这意味着X的十进制表示等于其反向(例如,X = 1234321)

我知道如果我们将f(Y)定义为这样的整数X≤Y,那么我们问题的答案就是f(B) - f(A - 1).减少的问题是如何有效地计算函数f.在某些情况下,我们可以利用某些数学属性来提出公式,但通常属性更复杂,我们在比赛中没有足够的时间.

在很多情况下是否有更通用的方法？它是否也可以用于枚举具有给定属性的数字或计算它们上的一些聚合？

其变体是找到具有给定属性的第k个数,当然可以通过使用二进制搜索和计数函数来求解.

Answer 1

实际上,这种模式有一种方法可以经常使用.它也可用于枚举具有给定属性的所有X,前提是它们的数量相当小.您甚至可以使用它来聚合具有给定属性的所有X上的某个关联运算符,例如查找它们的总和.

为了理解一般的想法,让我们尝试用X和Y 的十进制表示来表达条件X≤Y.

假设我们有X = x ₁ x ₂ ... x _{n - 1} x _n和Y = y ₁ y ₂ ... y _{n - 1} y _n,其中x _i和y _i是X和Y的十进制数字.如果数字的长度不同,我们总是可以在较短的数字前面添加零数字.

让我们定义leftmost_lo为最小的我用X _我 <Y _我.如果没有这样的i,我们定义leftmost_lo为n + 1.类似地,我们定义为最小的我与X _我 >ÿ _我,或N + 1,否则.leftmost_hi

现在X≤Y如果确实如此,则为真leftmost_lo <= leftmost_hi.通过这种观察,可以对问题应用动态编程方法,一个接一个地"设置"X的数字.我将用您的示例问题证明这一点:

计算整数X的数字f(Y),其属性X≤Y,X的数字和60

我们n是个Y的位数和y[i]是我根据上述定义的Y个十进制数字.以下递归算法解决了这个问题:

count(i, sum_so_far, leftmost_lo, leftmost_hi):
    if i == n + 1:
        # base case of the recursion, we have recursed beyond the last digit
        # now we check whether the number X we built is a valid solution
        if sum_so_far == 60 and leftmost_lo <= leftmost_hi:
            return 1
        else: 
            return 0
    result = 0
    # we need to decide which digit to use for x[i]
    for d := 0 to 9
        leftmost_lo' = leftmost_lo
        leftmost_hi' = leftmost_hi
        if d < y[i] and i < leftmost_lo': leftmost_lo' = i
        if d > y[i] and i < leftmost_hi': leftmost_hi' = i
        result += count(i + 1, sum_so_far + d, leftmost_lo', leftmost_hi')
    return result

现在我们已经f(Y) = count(1, 0, n + 1, n + 1)解决了这个问题.我们可以为函数添加memoization以使其快速.对于此特定实现,运行时为O(n ⁴).事实上,我们可以巧妙地优化这个想法,使其成为O(n).这是作为练习留给读者(提示:您可以压缩存储在信息leftmost_lo和leftmost_hi到单个位,你可以修剪如果sum_so_far > 60).该解决方案可以在本文末尾找到.

如果你仔细观察,sum_so_far这里只是一个从X的数字序列计算一个值的任意函数的例子.它可以是任何可以逐位计算并输出足够小的结果的函数.它可能是数字的乘积,是满足某个属性或许多其他东西的数字集的位掩码.

它也可以只是一个返回1或0的函数,具体取决于数字是否只包含数字4和7,这可以简单地解决第二个例子.我们要小心一点,因为在这里我们是允许在一开始就具有前导零,所以我们需要贯彻递归函数的额外调用位告诉我们,我们是否仍然允许使用零作为一个数字.

计算整数X的数字f(Y),其属性X≤Y,X是回文

这个稍微强硬一点.我们需要小心前导零:回文数的镜像点取决于我们有多少前导零,所以我们需要跟踪前导零的数量.

有一个技巧可以简化它:如果我们可以计算f(Y)的额外限制,所有数字X必须具有与Y相同的数字计数,那么我们也可以通过迭代解决原始问题所有可能的数字计数并将结果相加.

所以我们可以假设我们根本没有前导零:

count(i, leftmost_lo, leftmost_hi):
    if i == ceil(n/2) + 1: # we stop after we have placed one half of the number
        if leftmost_lo <= leftmost_hi:
            return 1
        else: 
            return 0
    result = 0
    start = (i == 1) ? 1 : 0    # no leading zero, remember?
    for d := start to 9
        leftmost_lo' = leftmost_lo
        leftmost_hi' = leftmost_hi
        # digit n - i + 1 is the mirrored place of index i, so we place both at 
        # the same time here
        if d < y[i]     and i     < leftmost_lo': leftmost_lo' = i
        if d < y[n-i+1] and n-i+1 < leftmost_lo': leftmost_lo' = n-i+1
        if d > y[i]     and i     < leftmost_hi': leftmost_hi' = i
        if d > y[n-i+1] and n-i+1 < leftmost_hi': leftmost_hi' = n-i+1
        result += count(i + 1, leftmost_lo', leftmost_hi')
    return result

结果将再次出现f(Y) = count(1, n + 1, n + 1).

更新:如果我们不仅要计算数字,但可能枚举它们或从它们计算一些不暴露组结构的聚合函数,我们需要在递归期间强制执行X的下限.这增加了一些参数.

更新2: O(n)"数字和60"示例的解决方案:

在这个应用程序中,我们将数字从左到右放置.由于我们只对是否leftmost_lo < leftmost_hi成立感兴趣,让我们添加一个新参数lo.lo是真的iif leftmost_lo < i和false否则.如果lo是,我们可以使用任何数字作为头寸i.如果它是假的,我们只能使用数字0到Y [i],因为任何更大的数字都会导致leftmost_hi = i < leftmost_lo并且因此不能导致解决方案.码:

def f(i, sum_so_far, lo):
    if i == n + 1: return sum_so_far == 60
    if sum_so_far > 60: return 0
    res = 0
    for d := 0 to (lo ? 9 : y[i]):
         res += f(i + 1, sum + d, lo || d < y[i])
    return res

可以说,这种看待它的方式有点简单,但也比leftmost_lo/ leftmost_hi方法稍微明确一些.对于像回文问题这样的更复杂的情况,它也不会立即起作用(尽管它也可以在那里使用).