UOJ Logo liu_cheng_ao的博客

博客

蔡德仁随笔:~一些 OI 教学研究的故事~

2024-09-14 21:51:12 By liu_cheng_ao

蔡德仁随笔:~一些 OI 教学研究的故事~

问题求解

知识点不只有算法

2017 年,距今七年之前——当时省选的主流 OJ,BZOJ 因故暂停服务,我作为一个学生参与 LibreOJ 的创建。在起初添加题目标签系统时,我们感觉到“OI 中似乎有两类不同的知识点”,然而,谁也说不清楚两者到底是什么,只好草草归结为“一般的理论或思想”和“具体的有模板题的知识点”,这就是 LibreOJ 玫红色和草绿色两种标签的由来。

时过境迁。大学二年级起,我们学习了一般的算法设计、计算理论。许多曾经模糊的、玄之又玄的思想和理论渐渐有了它清晰的面貌和数学上明确的表达与应用。那时,我意识到 OI 中确实存在两类不同的知识点——但不是什么宽泛和具体的对立,这二者的分野对研究算法和解决问题没什么意义。OI 中真正的区别在于组合模型与算法,也就是问题研究对象的结构和算法问题本身的性质。

例如这个经典例子:一个长为 $n$ 的序列 $\{a_i\}$ 每一项是 $1\dots m$ 之间的整数,给定若干个限制,每个限制的形式是 $l,r,u,v$ 表示 $a_{l\dots r}$ 这一段的最大值必须在 $[u,v]$ 内,问方案数。

这个问题的形式是统计方案数。最基本的做法是尝试判定一个特定的方案是否满足条件。这里,我们研究的是数学对象是序列上一些区间的最值。序列区间最值的结构是笛卡尔树——因此我们在笛卡尔树上的 LCA 处检查限制。于是,我们就找到了一种按照遍历笛卡尔树的顺序逐位判定某个方案是否满足条件的算法。直接对这个判定算法过程的状态压缩就可以得到一个递推(DP)算法统计方案数。也就是 $f(i,j,k)$ 表示区间 $a_{i\dots j}$ 最大值为 $k$ 的方案数,转移顺序表示最值结构(笛卡尔树的形状),再进行优化。

这里,问题求解有几个步骤: - 问题研究的组合对象:序列区间最值结构→笛卡尔树 - 根据笛卡尔树容易得到朴素的判定算法 - 问题形式-计数:从判定到计数→DP的基本方法 状态机-状态压缩 - 算法优化:经典的DP优化方法,状态合并、数据结构(前缀和等)

可以看到,这里存在两个知识点:“笛卡尔树”刻画序列区间最值结构,“递推/DP DP优化”在之后解决计数问题。换言之,OI中存在刻画问题的组合对象以及算法形式两个主要任务,它们是不同的。

问题在于,传统的OI训练完全是以算法形式(算法模板、模式、优化技巧)来组织的——因为只有算法会有模板题,组合对象在传统教学中不存在。除了笛卡尔树等少数,绝大多数的组合知识点尽管重要,却完全被忽略,只能在所谓的“杂题选讲”,DP/贪心/构造题单中寻得只鳞片爪。更严重的是,表示、推导、研究组合模型性质结构的方法几乎没有任何系统学习的意识。大半的NOI金银牌在半天内做不出任何有三、四个引理的组合推导问题(比如这样的)。对于那些没能从同学交流或自学组合数学悟出道理的多数同学来说,七年前和今天都是如此。

除了组合,一切没在算法模板题和经典教科书注册了位置的的数学也都如此被忽略。例如 OI 中这个常见的推导:最大化绝对值和 $\max(\sum \lvert x_i-y_i\rvert)$。

$$ \begin{aligned} &\max(\sum \lvert x_i-y_i\rvert)\\ =&\max(\sum \max(x_i-y_i,y_i-x_i))\\ =&\max(\sum \sigma_i(x_i-y_i))\\ \end{aligned} $$

将绝对值(或者曼哈顿距离、方差等类似的东西)写成参数最值,然后利用最值方向的一致性通过变量分离等简化最优化权值的范围/形式。本来,这个出现次数不少的技术也应当是一个知识点,但传统教学中学生很难意识到这一点。这导致不管是自己做题,还是题单、选讲等课程都很难避免学习中遗漏和忽略这类方法。

因此,在教学中传达这些现代数学的研究意识是必要的。任何的关键点、难点都应该被研究。例如 OI知识点的字段和类型 所写的。为了达到这一点,一些笔头的算法数学的练习、研讨也是必要的。

数学语言与一句话题解

《西江月·证明》 ——佚名

即得易见平凡,仿照上例显然。

留作习题答案略,读者自证不难。

反之亦然同理,推论自然成立。

省去过程QED,由上可知证毕。

每个 OIer 大概都有过对着题解抓狂的时刻。面对“单调性一下就行了”“注意到可以二分图染色并给白色权值异或1”……种种一句话题解,如同见到了一座精致的牙雕,但是谁又能想象出生长它的大象的样子呢。

对于个人笔记,一句话题解记录的是问题中的关键认识。表面上看,一句话题解看不懂可能有数学符号的含义没有标明,跳过表述等原因。但更多的问题在于,这个性质的前因后果是什么?(谁具有这个性质?哪里用到这个性质?)它的数学目的是什么?(能解决什么问题?没有为什么不行?有/无这个性质的区别是什么?)它能否推广到其它的情况?(改条件还成立吗?对于其它模型、问题能否诱导出类似的?)

这些是研究数学问题的一般方法。我们希望自己能通过一点例子举一反三,那么不妨试一试从这个例子中的关键点开始研究。

在今年的江苏省队集训(有四五个 NOI 金牌的同学参加)中,我出了自认为难度接近的 3 道题目,但实际结果却有些出乎预料。3 道题中有一道好几个同学会做,但另外 2 题却没人得出正确的思路。和同学讨论了想法和做法的细节后,我注意到这样一个事实:我们研究问题的思维方式是不同的。同学们做题的时候,往往找到问题的一个大概的模型(比如二维点、树上路径、二分图、生成函数等某个比较宽泛的对象)之后,根据自己的解题经验观察和尝试该模型上适用的算法模式/技巧(比如对于树上路径来说,尝试按LCA分类/启发式合并、树上差分、分治、倍增等手段),将其套入问题看是否能够满足条件和性质或联想做过的类似问题算法做些调整。

这一做法的问题是,对问题研究对象本身没有稳定的刻画,在不断尝试过程中,之前推导的性质观察往往被浪费。一次又一次地“重做”这道题,直到某个幸运时刻猜对了大体的做法,然后利用题感和经验完成细节工作。这对于整体不太经典(即使每个部分的推导都很常规)的问题就很难做了——甚至很多处理方法相当直接的问题都被称为 Ad-hoc。

举一个例子。有一排 $n$ 条鱼体型为正整数 $\{a_i\}$,可以让一条鱼吃掉另一条相邻的,体型不大于自己的鱼,并且体型加上被吃的鱼的体型。每次问一个范围,问里面哪些鱼能吃光范围内的其他所有鱼。

首先,容易发现,任何时候一条鱼的状态对应一个区间。然后,只有那些“极大”的,也就是无法继续吃掉左右相邻鱼的区间是有用的。到这里,我们作为“题感”选手迅速发现了一个事实:每次从极大区间跳到一个更大的极大区间,区间和(鱼大小)至少翻了一倍,容易得到总的层数是 $\log a$ 的。

到此为止——我们可以轻易用倍增、线段树等算法配合 $\log a$ 的势能来在可接受的时间复杂度内解决问题。然后 AC,下一题。

然而,等等。这时候我们对问题的认识足够充分吗?

想想一般方法。我们应该刻画问题的研究对象,并且不断加深对它的认识。对于这个问题来说,上面我们已经得到了刻画问题的关键是极大区间的结构。而我们容易证明:不能有两个极大区间在相交的同时互不包含。否则,假设有 $[a,c)$ 和 $(b,d]$ 两个极大区间满足这点且 $a\le b\le c\le d$,那么 $[a,c)\ge b\gt (b,d]\ge c\gt [a,c)$(这里的不等式比较的是对应的鱼体型总和),矛盾。极大区间一定满足它相邻两侧的数字比自己的区间和还要大,这会导致矛盾。

所以这是嵌套集,可以用一棵有根树的每个子树(对应的DFS序区间)来表示。上面的性质也对应了树高不超过 $\log a$ 等等。更重要的是——当我们想进一步研究这个问题时,只要研究这棵树就行了。显然,找到这棵树比起只是套用倍增、线段树解决特定问题,我们的认识深刻得多。

在一开始就刻画问题的研究对象,并不断推进认识——而不是直接尝试套用各种技巧。这是不那么依赖题感和灵感的一般方法。想想自己如果要打表找规律,该对谁打表(问题研究的关键数学对象),用什么格式输出(表示和刻画它的可能手段)。

题感做题就像盲人摸象,反复探索各个部位,不同局部性质难以联系,尝试很多次才能逐渐得到整体认知。而如果先知道了象的大致形态(问题的研究对象和可能的表示),再对具体的部位做研究逐步填充,局部之间是有联系的,自然探索起来事半功倍。

一句话题解令人迷惑,也往往是因为我们并不知道在问题中要刻画什么,因此缺乏目的。没有主语只有谓语,自然是读不懂文章的。反过来说,能把一句话题解的数学逻辑补全,也是一种可行的练习方式。

举一反三的计算理论

计算理论是另一个竞赛传统教学未曾意识到的部分。

问题类、归约、计算复杂性、计算模型——现在 OI 算法已经发展到了需要这些一般理论和思想的地步。具体到各类具体的算法,更一般的算法设计思想也很重要。OI 正在逐渐习惯基于组合结构的算法复杂性分析,或者基于自动机、等价类等的字符串研究(就像IOI2024D2T1)。生成函数云云更不可能被人力禁止。总之,OI 开始需要一些研究能力——而不只是学会一些经典算法和应用然后局部改编。

最近某位同学的一个问题可以作为例子:

问:有这么一个问题:删边加边MST(最小生成树),离线。使用线段树分治的前提下,存在一种并查集做法:在一个节点上,下传下来一些边,表示可能在MST里面(它们都已经完全覆盖这个节点),在这个节点上,忽略子树边,把所有完全覆盖的边掏出来,如果不在MST就永远没用。把子树边全加入,再把完全覆盖的掏出来,如果在MST就永远有用。后者缩点,前者删除,剩下的下传。

这个算法似乎有些反直觉。这个东西是否有拓展或者可能源于更加本质的某个事物??

(思考了一段时间之后)

这里面,是否:问题的核心在于保证递归到一个节点时候的有效点/边数量? 我想说,这个算法并不容易归结为最基本的mst方法和线段树分治的简单结合,而是有一点它自己的东西。它的牛逼之处在于对于复杂度的保证。 而这一点,是否有推广?或者说,就可以把它当作一道孤题,不再细究?

这位同学实际上已经注意到了问题的关键。学术上,这是数据结构的一个非常基本的思想。为了解释这个问题,我们可以考虑把它推广到MST以外的其他问题上并做一个比较。

答:这个怎么推广——感觉找到一些和MST有类似性质的东西还是不难的——比如二维偏序极值(有一堆区间,要求插入区间删除区间,用线段树分治处理,维护所有不被其他区间包含的区间组成的序列,也就是所谓动态单调栈或者说动态前缀最值)。

把维护MST换成维护二维偏序极值,这个技巧还适用,但可能需要更复杂的均摊。

具体来说就是得按子树内涉及到的操作参数对数轴进行分段(值域压缩/离散化),然后把上面继承下来的潜在的极值序列坐标同属一段的缩起来处理。每一段要么同时不是极值,要么同时是极值。

核心点在于,线段树分治的一个 $m$ 大小的节点的子树内可能涉及到的操作数是最多不超过 $m$ 的(或者有些问题 $m\log m$)。而在很多问题中,$m$ 个操作实际上最多也就只能区分出 $m$ 组本质不同的信息。 就像在长为 $n$ 的序列上做 $m$ 次区间加也可以分段缩点(值域压缩/离散化)把序列规模缩小到 $O(m)$。

而MST也满足这个条件(图里只有 $m$ 条边待考虑时,图待定最小生成树的规模也可以缩到 $O(m)$ 表示),所以也可以这么做。这实际上在组合对象里是非常常见的性质,并不是MST特殊的。

所以其实大部分线段树分治都可以这样处理。这也是数据结构的一个标准方法,操作少的时候,就是可以按“能否被不同操作区分”对原来的组合对象进行缩点,使得总规模变成和数据结构操作有关的。

当然,也有不满足这个的。比如动态增删物品的背包。因为只要达到 $\log V$ 个物品信息量就是 $\Theta(V)$ 的。

这位同学很快发现了其他应用。

有一个应用:P7361 拜神

首先这个题有一个显然的3log做法:二分,然后看区间max lcp,这个东西可以掏出来1log个支配对 ,再来一个log是线段树之类的。这是粗略的分析。当然实际上本题有一个优点:因为修改是1log,而查询没有log,那么二分的那个log正好补上来。所以这实际是2log。

另一种算法:整体二分。然而整体二分导致了按理来讲必须是3log。它加入支配区间,然后其实就是覆盖了一个阶梯,是二维偏序极值问题。查询本质上查询前缀最值。

然而注意到其实,询问有一个端点是不变的,所以可以在每一层的时候根据询问不变的那个端点来缩段,然后暴力维护前缀max。

分析复杂度:首先,所有节点总共本质不同的段是只有1log的。然而本来就有1log的支配对,一搭配线段树分治/(或者说整体二分,本质差不多), 已经自带2log了,即便是O(1)操作,复杂度无可避免的依然是2log。

当然,这也并不是完全没用,如果询问的q改成nlogn级别,那么正常算法的二分加持久化就会导致复杂度和整体二分一样变成3log。然而这个做法复杂度依然是2log。

只要理解了数学上准确的例子,从算法设计的一般思想中受益也并不困难。

前面几节,我们讨论的是如何在例题上举一反三——而在这一节,我们展示了学习算法时计算理论的意义——在算法设计上举一反三。当例子足够时,我们总会走向一般的理论。

天涯若比邻

OI 的研究和改进是站在计算机科学基础上,许多同学和老师们在 OI 社区中无私贡献的成果。

感谢他们。而对于我来说,有一些人是特别记得的。

感谢我的朋友 ljt12138,tqyaaaang,sys.,还有 Shilling.X,以及许多人。

感谢 EI 的所有工作。

感谢 Qingyu 的所有工作。

感谢 fjzzq,command_block,YeahPotato,skc,dXqwq,xht,undefined,Menci,rxz 和许多其它同学对更科学的 OI 学习资源和技术做出的贡献。(感谢小粉兔——如果那篇归约课件已经做完了的话。)

感谢蒋炎岩老师,您提出的问题总给我们指出道路。

感谢 cxm,xudyh,wls,vfk,jiry,lrj 和其它许多前辈带我接触 OI 教研。

感谢勰码团队和 lethalboy 对教学实践的支持。

感谢我在信息之路上重要的刘老师,董老师,陈老师,段老师,姚老师。

仍然,最后引用蒋老师的话来结尾:

大部分同学都没能迈过从 “业余选手” 到 “职业选手” 的门槛——给你更多的时间,能解出非常困难的题目。如果你接受过一点理论计算机科学的训练,就会发现竞赛作为一种 “竞技体育”,其实是性价比极低的。 ——蒋炎岩 Yanyan's Wiki (jyywiki.cn)

祝各位都能从题感走向严肃、科学的研究方法,成为算法设计和计算机科学技术的“职业选手”!

更多讨论

我们一般在公开 OJ 和各大 OI 群里讨论问题,不过,有时我一些内测的课件文件和讨论放在这里:

d50760233cabb11c112b77f707fc7b18

拓展阅读(示例)

LCA的省选NOI长训和测试赛公告

2024-09-12 04:09:01 By liu_cheng_ao

LCA的省选NOI长训和测试赛公告

LCA 的 OI 课堂开课辣!

fa025fd8c420225402faf6e7df41ed2e

2024 年 9 月 24 日起,LCA 的第一届省选 NOI 长训将在山东省青岛市举行。

本次长训将会以线下全日制集训形式进行,每年一届分为四期,每期约两个月。由LCA实际主讲,并且有多名跳蚤国神秘嘉宾担任命题、助教和教务等工作。其中,部分节假日或比赛前会有短期集训,期间会有更多高水平旅客讲课和紧凑的模拟赛。


目前,在 NOIP 以上的省选、NOI 水平的学习过程中,同学主要通过大量刷题、模拟赛训练来提升实力。在遇到困难和瓶颈时,缺乏科学的方法去分析具体的知识、学习情况和应对策略,往往只能粗略地增加某一类型的刷题数量,或者尝试在自学和同学交流的过程中自行领悟一些算法和数学方法。

仅有的几个省选 NOI 长训,也是基于这些传统的讲课、刷题、模拟赛、同学自学交流开展的,缺少具体的教学方法帮助选手高效发现问题和提升深层次的理解和解题能力。

不过,近几年的 OI 同学们已经发展和引入了不少一般性的算法知识理论和教学方法。我们也有幸为 OI 社区的学习资源做出一些贡献,用学术方法改进 DP、字符串等知识的深入理解,引入组合模型和计算理论等提高同学们研究和解决算法问题的能力,尝试题解补全、算法数学练习、问题改编研讨等新的教学技术和形式,并在近年山东、河北、江苏各省省队集训等课程中得到初步验证。

因此今年起我们计划开展长训课程,邀请全国各地达到一定水平并计划冲击省队 NOI 的选手进行更为科学的长线训练。


一些教学研究的笔记 https://loj.ac/d/4518

299f518daea1adc6d8518d47e59dda3a

测试赛

本次长训测试赛将于 9 月 15 日、9 月 16 日进行,所有同学均可直接报名参加。测试赛分为两场,NOIP+ 难度和省选难度各一,可根据自己水平自由选择参加其中一到两场。

测试赛成绩可以作为认定入营水平资格的标准。请保证参赛公平。请勿在测试赛期间与人讨论、上网搜索题目或用 AI 辅助写程序等。一旦发现违规行为即失去资格。

教学改进

省选/NOI 难度 传统教学 本次教学
学科体系 零散的算法知识点和题目 基于数学和算法科学的体系,带学生理解问题的实质和研究方法
教学内容 只有算法模板、变体和数学概念、例题 还包括描述和研究问题的数学模型、算法设计方法等
教学方式 讲课+刷题+模拟赛+答疑 还包括多种系统性解决问题的数学思维练习和研讨,如问题改编等
解题方式 以题感为主,方法靠自学领悟 理解数学方法,稳定记录和推进对问题的认识
作业题单 - 尽量覆盖各种OI中的技巧和应用
模拟赛 - 有编审对题目质量和难度进行把控,保证每场训练的有效性,避免低效题目如思维难度低的大代码毒瘤题、超纲的偏题怪题等。每个月有公开原创月赛。

日常训练采用讲练结合的模式,全日制上课,有理论课、交流研讨课、晚自习(有答疑老师),并安排体育活动,劳逸结合。

课后作业除了常规训练题单外,增加了算法数学练习。

交流研讨课注重算法数学练习题讲解讨论,鼓励学生进行好题分享、算法想法分享和解题交流等,另外还会开展题目研讨课,对题单或模拟赛题目进行深入研究,通过改编等方式探究各种问题的一般性推广,并讲解相关 OI 应用和学术拓展知识,增进学生对知识的理解和问题模型的研究能力。

基本信息

  • 时间 2024 年 9 月 24 日到 2025 年 7 月中旬,按照NOIP-省选-NOI时间分为四期,每期约两个月,两期之间根据正式比赛时间休息约 1 到 2 周。每周三到周一下午上课,周一晚上和周二休息。

  • 地点 山东省青岛市某中学,线下全日制集训。

  • 教学团队 刘承奥(蔡德仁/LCA/CommonAnts)主讲,另有多名 NOI 水平助教参与工作。此外,有多名 NOI 金银牌高水平同学共同学习。

090e2a2d7d61c6f49554018d16bb117d

招生信息

  • 招生范围 招收全国 NOIP 250 分以上或同等水平的同学(可参加入营测试,不要求过往比赛成绩),并且家庭和学校支持接受全日制线下集训。

  • 招生人数 总人数不超过30人。

  • 报名方式 按期报名,一期起报。有意向同学可以填写问卷:问卷链接

  • 学习费用 按期收取,根据不同基础成绩享受不同优惠,多人团体报名另有优惠。详情请在填写问卷之后咨询。

  • 奖学金 根据 2024 年 NOIP 和 2025 年省选/NOI/IOI 成绩设有奖学金。详情见下文附录。

  • 教学基金 勰码将出资成立教学基金,专项补贴部分有经济压力的同学顺利完成营地训练计划,可用于缴纳学费、住宿费、承担生活费等在营期间的学习、生活基本支出。受资助同学需要承担部分建设 OI 社区公开学习资源任务和教学任务(教学可选在退役后进行),以推动 OI 发展以及营地教研、积累教学经验。具体细则和申请流程将于近期公布,可关注社区/OJ公告。

报名&联系方式

c8b63adf03f91528f709f7bc8bbd2bb6

LibreOJ NOIP Round #1

2017-11-02 23:06:26 By liu_cheng_ao

又来 UOJ 打广告了 $\times 2$

LibreOJ

公告链接:公告

比赛链接:Day 1 Day 2

NOIP 将近,为了帮助广大 OIer 准备比赛,也为了改变各位对 LibreOJ 比赛难度的认识,以及实现我们在 β Round 5 中的承诺,是时候举办一场 NOIP 全模拟赛了!

LibreOJ NOIP Round #1 将于 11 月 4 日至 11 月 5 日举行。这是 LibreOJ 第一场 NOIP Round。

下面介绍比赛的具体情况。

基本信息

  • 时间 2017 年 11 月 4 日,星期六,上午 8:30 ~ 12:00 + 5 日,星期日,上午 8:30 ~ 12:00
  • 时长 3.5 + 3.5 小时
  • 题数 3 + 3
  • 赛制 NOI + NOI
  • Rated + Rated

出题人

比赛难度

比赛难度将与 NOIP2016 相近。

同时我们确保了较多的部分分,尽力做到了较好的区分度,丰富的思维含量,以及符合 NOIP 的算法知识和代码难度。

可能比 NOIP 还要 NOIP (雾)

比赛奖励

设两天至少参赛一天的人数为 $n$。

考虑到 NOIP 的难度、真实比赛的分省评奖方式以及 LibreOJ 用户在以往比赛中表现的水平,本次比赛不会像 NOI Round 那样按比例评奖,而采取综合考虑成绩分布、题目组成员和若干在以往 OI 系列赛事中发挥稳定的标志性选手的成绩的方法评定分数线。我们将评出基准(相当于 NOIP 中的全国基准线)和最高(相当于 NOIP 中的浙江分数线)两套分数线。

这次比赛将会根据两天的总分进行排序(如果存在同分将以两天的罚时总和作为第二关键字,如果仍同分将不分先后),并评奖。

  • 本次比赛未在以往比赛中获得 LOJ T-shirt 的 ID 中排名前 $\max(3,\min(6,\lfloor 0.03 n \rfloor))$ 的将获得 LibreOJ T-shirt 一件。

  • 所有选手中将以某些方式选择至多 5 名选手各获得小礼品一件。选择方式的 MD5 为 f7b4c69f242009c56863a14fd6518b3d

测评方式

比赛采用 NOI 赛制,以每道题目最后一次提交(包括 CE)为准。

为了模拟 NOIP 中选手参加 Day 2 时不知道 Day 1 成绩的情况,本次比赛采用 Day 1 只测第一个样例,两天结束后统一评测的方式。

一种基于错误的寻找重心方法的点分治的复杂度分析

2017-09-24 22:09:30 By liu_cheng_ao

我们知道,通常的点分治方法都基于重心,删除重心后将每个连通块分别分治。正常情况下寻找重心需要做树DP,需要遍历两次树(即使从上一层传入点数,也得在上一层遍历一次),某些选手就用了一些黑科技:从上一层传入“本层中与上一层重心相连的点”(称为根,记作 $K$)的以“上一层的根”为根的子树大小作为本层总点数

听起来很拗口,实际上是这么回事:(图中 $K'$ 表示本层的根,$K$ 表示上一层的根)

TR1.png

可以明显发现,当 $K$ 和 $K'$ 处于上一层重心 $O$ 的同一子树时,传入的点数是错误的。

这是否会对时间复杂度造成影响呢?

这与找重心的方式有关。我们讨论两种最常见的找法:

法1

从本层的根开始深度优先遍历,并同时计算出子树大小,以第一个所有子树大小不超过 $\frac{n}{2}$ 的为重心。

结论:算法错误

传入的点数值为 $n$。

可以举出反例:考虑这样一棵树:由重心和端点与之相连的三条长 $\frac{n-1}{3}$ 的链组成。初始的根位于某个叶子处。

第一层分治,传入到根所在链的大小为 $\frac{2n+4}{3}\geq 2\cdot\frac{n-1}{3}$,因而任何点都符合条件。按照深度优先顺序,这次找的“重心”是第一层的根。

第二层分治,传入到根所在链的大小为 $2<\frac{1}{2}\cdot(\frac{n-1}{3}-1)$(当 $n\geq 16$ 时)。这时不存在符合条件的点,分治无法进行,算法错误

法2

从本层的根开始深度优先遍历,并同时计算出子树大小,将传入值与以自身为根子树大小之差作为向本层根方向的子树大小,再取最大子树最小的点为重心。

结论:算法正确,递归层数 $O(\log n)$,访问节点的总次数 $O(n\log n)$。

我们来分析时间复杂度:

我们将分治结构稍作改变,只考虑输入点数等于实际点数的问题。显然当点数为 $1$ 时访问节点数 $O(1)$。

初始问题是符合条件的。现在考虑把问题分解前处理一层产生的代价(包括递归但大小错误的部分):

TR2.png

由于只有本层的根所在的方向递归时会错误,因而只要考虑对于本层重心而言根所在子树即可。

考虑一个问题。设本层实际大小为 $n$,以 $O_1$ 为根时含 $K_1$ 子树的根为 $K_1'$(也有可能 $O_1=K_1$,这时没有出现错误,复杂度正确),以 $K_1$ 为根时子树 $O_1$ 的大小为 $y_1$,以 $K_1'$ 为根时 $K_1$ 所在子树大小为 $x_1$。(均指实际大小)

解决本层的访问节点数为 $O(n)$。现在考虑递归到 $K'$ 的错误部分。该部分的实际点数为 $n-y_1$,传入点数为 $n-x_1$。设该部分处理时与上一层对应的部分用层数下标表示。以此类推直到 $K_i=O_i$ 为止。这一系列问题访问的总点数即为问题处理的代价。

运用归纳法,我们可以知道每一次的实际点数 $N_i$ 分别为 $n,n-y_1,n-y_1-y_2,...,n-\sum_{i=1}^{n-1}y_i$,传入点数 $N'_i$ 分别为 $n,n-y_1,n-x_1-y_2,...,n-\sum_{i=1}^{n-2}x_i-y_{i-1}$。

下面证明 $x_i \leq y_i$。使用归纳法,设对于 $j < i$ 该结论均成立(由重心显然对于第 $1$ 层成立)。实际上,若 $x_i > y_i$ 则对“重心”$O_i$ 而言包含 $K_i$ 的子树为最大子树,并且由于 $x_{i-1} \leq y_{i-1}$,本层的传入点数不小于实际点数。这样,用传入点数减去子树大小算出的点数不小于 $x_i$。故该算法计算出的 $O$ 的最大子树必为 $K_i'$ 且计算出的大小不小于 $x_i$。对 $K_i'$ 而言,除 $O_i$ 外的各子树大小计算值均小于其作为 $O_i$ 子树的计算值。又 $y_i< x_i$,故子树 $O_i$ 也小于该值。这样 $K_i'$ 计算出的最大子树严格小于 $O_i$ 的,与重心的计算定义矛盾。

更进一步地,我们可以证明 $y_i\geq \frac{1}{2}N_i$。证明方法类似:假设 $y_i<\frac{1}{2}N_i$,同上可证其最大子树必为 $K_i'$ 且计算的大小不小于其实际值,$N_i-y_i > y_i$。则对于 $K_i$ 而言,也可以用类似上一段的方法证明其计算出的最大子树严格小于 $O_i$,与重心的计算定义矛盾。

故有 $N_{i+1}\leq \frac{1}{2}N_i$。由于第 $i$ 层的访问点数为 $O(N_i)$,一个规模为 $n$ 的问题处理总点数满足 $T(n)=T(\frac{n}{2})+O(n)$,解得 $T(n)=O(n)$,且这部分递归层数 $O(\log n)$。

故分治时处理一个问题的时间为 $O(n)$。并且其分解出的子问题互不相交且都是正确方法的某个子问题的子集,故递归层数和子问题的时间复杂度不高于一般点分治。证毕。

最小期望次数生成随机有理数

2017-09-21 17:32:35 By liu_cheng_ao

已知:随机数生成元件等概率返回 $[0,p)$ 中的整数,要构造一个以概率比 $a_0:a_1:...:a_n(\gcd(a_i)=1)$ 返回 $[0,n)$ 中的整数的随机数生成器,求元件的最小期望使用次数。

设第 $i$ 次返回的结果分配了 $K_{i,j}$ 个给返回值 $j$。则:

$$ \begin{array} \forall j ,\sum_i p^{-i}K_{i,j}=\frac{a_j}{\sum a} & (1)\\ \text{minimum.} \sum_{i,j}ip^{-i}K_{i,j} & (2) \end{array} $$

引理1 $\forall i,j ,K_{i,j}\in [0,p) $

证:使用调整法:

若 $\forall i,j ,K_{i,j}\neq p $,由 $(1)$ 有 $i>0$ ,则可令 $K_{i-1,j}$ 增加 $1$,$K_{i,j}$ 减少 $p$,显然 $(1)$ 式仍成立。

$(2)$ 式的改变量为 $(i-1)p^{-i+1}-pip^{-i}=-p^{-i+1} < 0$ ,得到了一个更优解。

证毕。

现在来构造 $K$。考虑返回值为 $j$ 的情况,取出 $K$ 的第 $j$ 列向量,设为 $\vec{k}$。

则 $\vec{k}$ 是 $p$ 进制的 $\frac{a_j}{\sum a}$ 的位向量。当 $\sum a$ 是 $p$ 的幂时有两解,取最后为 $0$ 循环的一解;否则 $\vec{k}$ 是唯一的。证明从略。

至此找到了一个下界 $K$。在决策树上第 $i$ 层给 $j$ 分配 $K_{i,j}$ 个点,用归纳法可以证明方案是存在的。

另外可得推论:

推论1 “$a$ 是有理数”与“存在一个有 $n$ 个终态,字符集为 $[0,p)$ ,按随机数生成元件的结果转移,返回终止的状态的DFA满足条件。”是等价的。

证明从略。解释说明:由于 DFA 是有限状态的,因而对应的概率是循环小数(有理数)。反之则可用上述方法构造。

liu_cheng_ao Avatar