Tho*_*hle 9 algorithm integer sequence
我遇到了以下问题,从那时起我一直在想这个问题:
爱丽丝N在黑板上写了连续的正整数.例如"99, 100, 101, 102".Bob已经删除了所有数字,但每个数字都有一个数字,因此序列现在可以读取例如"9, 0, 0, 1".请注意,他留下的数字对于每个整数都可以是不同的数字.
我们的任务是,O(N log N时间复杂度,找到可能已启动序列的最小数字.在上面的例子中答案是99.对于长度为7的序列"1, 4, 0, 5, 4, 1, 4",答案是1042.(其产生序列1042,1043,1044,1045,1046,1047,1048).
我可以显示周围的上限1234567890*N,因此输出不能是无限大小.但是我甚至找不到有效的O(N^2)解决方案.
有任何想法吗？
更新:对于那些感兴趣的人,这个问题出现在2014年波罗的海信息学奥林匹克(BOI)中(这是"序列"的任务).由于Codeforces用户Fdg,这是一个O(N log N)解决方案:尝试起始值的每个可能的最后一位数.将连续的数组元素分区为末尾有数字0到9的组(这可以从起始值的最后一位数字推断出来).我们知道在删除最后一个数字后,同一组中的所有值都具有相同的前缀.让我们消除输入中的数字与根据位置应该具有的最后一个数字相匹配的所有值.
现在我们有一个稍微不同的子问题:对于每组10个,我们知道它的前缀中出现的一组数字.我们将其折叠为单个数组元素.这个广义问题只有原始问题大小的十分之一,并且可以递归地使用相同的算法来解决.
因此,我们得到递归T(N)= 10*T(N/10)+ O(N),我们使用主定理求解为T(N)= O(N log N).
例:
让我们说输入是[1, 4, 0, 5, 4, 1, 4, 9, 5, 0, 1, 0].因此,在通用形式中,我们知道每个位置的以下数字子集:
{1} {4} {0} {5} {4} {1} {4} {9} {5} {0} {1} {0}
我们检查2数字是起始编号的最后一位数(当然我们也检查所有其他数字,但这个分支将结果包含最小解决方案).我们知道最后数字的顺序就像
2 3 4 5 6 7 8 9 0 1 2 3
所以我们知道具有相同前缀的组(2-9和0-3).我们还从已知的集合中删除那些位于正确位置的数字:
{1} {4} {0} {} {4} {1} {4} {} | {5} {0} {1} {0}
通过收集每个组的所有数字,我们得出减少的问题
{0,1,4} {0,1,5}
我们再一次强制倒数第二位.假设我们正在检查4.我们得到:
4 5
{0,1} {0,1}
这减少到
{0,1}
既然我们只有一个数组元素,我们只需要在那些没有前导零的数字中构建按字典顺序排列的最小数字,即10.结果是1042.
我相信这里的一个关键观察是,在这样的进展中,长度为N,只有最后一个ceil(log_10(N))数字被改变不止一次.因此,我们可以强制执行最后一个ceil(log_10(N))数字,前缀末尾的9个数字和O(N*log N)之前的数字.
所以我们修复了这个模式
P..PX9..9S...S
在已知后缀S的情况下,已知9的数量,X <9是已知的,但前缀P不是.
我们现在可以从已经与我们已知的其中一个数字相匹配的序列中删除这些数字.我们留下一组数字,我们知道它们包含前缀P.我们只是形成字典上最小的字符串,它没有前导零并包含所有数字.
运行时为O(N ^ 2 log N).