Blog E

Probability and Computing 第四章笔记

Moment Generating Functions \[M_X(t)=\mathbb{E}[e^{tX}]\] 性质 $M_X^{(n)}(0)=\mathbb{E}[X^n]$ X,Y 独立,则 $M_{X+Y}(t)=M_X(t)M_Y(t)$ Chernoff Bounds 根据上述生成函数和马尔可夫不等式可以得到: $\Pr(X\ge a)\le \min_{t>0}\frac{\mathbb{E}[e^tX]}{e^{ta}}$ $\Pr(X\le a)\le \min_{t<0}\frac{\mathbb{E}[e^tX]...

Posted by ethan-zhou on August 3, 2023

Probability and Computing 第三章笔记

Markov’s Inequality 若 X 恒大于0,则: \[\Pr(x\ge a)\le \frac{\mathbb{E}[x]}a\] Moments 定义 kth moment of a random variable X is $\mathbb{E}[x^k]$ variance $\mathrm{Var}[X]=\mathbb{E}[X^2]-(\mathbb{E}[X])^2$ covariance $\mathrm{Cov}(X,Y)=\mathrm{E}[(X-\mathrm{E}[X])(Y-\mathrm{E}[Y])]$ 定理 \(\...

Posted by ethan-zhou on August 3, 2023

Probability and Computing 第二章笔记

Linearity of Expectations (不要求独立) \[\mathbb{E}[\sum X_i]=\sum \mathbb{E}[X_i]\] 琴生不等式 $f(x)$为凸函数,则$\mathbb{E}[f(x)]>f(\mathbb{E}[x])$,利用泰勒展开证明即可. binomial random variable $\Pr(X=j)=\binom n j p^j (1-p)^{n-j}$ 性质 $\mathbb{E}[X]=np$ 应用考虑一个函数 S.每次调用它,S 都会递归调用 X 次自己.其中 X 是二项式概率分布的变量...

Posted by ethan-zhou on July 26, 2023

Probability and Computing 第一章笔记

最近看 Probability and Computing, 在此记录一些重要结论和有趣算法. Polynomial Identities 多项式次数为d,则x在[0,100d]随机取值,仅有$\frac{1}{100}$概率错误(根据代数基本定理,f-g最多有d个根). 一些基本定义和引理: 概率定义容斥原理事件的独立性条件概率 $\Pr(E|F)=\frac{\Pr(E\cap F)}{\Pr(F)}$ Veryfying Matrix Multiplication 给定三个方阵 A,B,C 快速验证 $A\times B=C$? 随机算法随机...

Posted by ethan-zhou on July 21, 2023

并查集随机合并的复杂度

一把洛阳铲

似乎好久没有写博客了，其实写了一个EC-final游记，但是不太想发今天来挖个坟，这是一年前我发的帖子关于并查集随机合并复杂度正确性，当时帖子底下有许多或对或错的感性证明。在写带撤销并查集的时候，因为路径压缩只能保证均摊复杂度。所以往往需要写按秩合并，而这种随机合并的写法可以让你省去几秒钟的思考，省去几行代码，减少一点数组操作，增加一些常数。今天又写了一个带撤销并查集的题，用到了这个写法。又想了想这种合并方法，似乎可以严谨证明，就写一下，以后可以放心这么写不被卡了。注意：下文的证明基于以下这种先find再比较rnd的写法！别的写法可能被卡，详见上面帖子中我的回复 int...

Posted by ethan-zhou on April 29, 2023

2022ICPC沈阳区域赛游记

活学活用，论“批归一化”在算法竞赛中的运用

热身赛 rank 2，大概是 rp 全都给热身赛了吧。。。（虽然热身赛是纯拼手速和想题速度）感觉这场区域赛区分度极低，四题有一百多队，五题有二十多队，而区分了不少队的 A 题也没啥思维含量，本来是个好想好写的问题，结果出题人生硬地加了一个单点，让代码变的繁琐不少。而除了这五题之外的题都比较有难度，做出来的不多。最后五题 rank 27，金牌靠后，发挥略低于预期，不过也没啥影响。上来发现 15 秒就有人过了 D，于是让 wky 看看 D, 在 6 分钟签到成功。然后又发现 C 过了好多人，于是我就开了 C，简单分析发现 $l$ 和 $r$ 一定有一个卡着某一个 $A_i...

Posted by ethan-zhou on November 7, 2022

2021ICPC济南区域赛VP记录

打的还行

和破壁人及 wky VP 了去年的济南区域赛。最后排第 8，虽然离前 3 还有不少距离，但至少发挥没有之前两次 ICPC 预选赛那么拉跨。这次签到题很少，并且 E 题连写带调弄了一个多小时，差点都以为要寄了。感觉有几道题目很有意思，故记录一下思路。（前面有两队是打星参加的） E 下文约定记号 $G_i=\{j\mid(i,j)\text{ is a magic link}\}$ 观察到 M 的大小比较蹊跷，于是猜想有 $O(NM)$ 做法。首先不考虑题目所求，想一下如何在不删点的情况下计算总分数。考虑如下的一个交叉产生的代价如何计算：凑了一阵均摊复杂度之后，可...

Posted by ethan-zhou on September 30, 2022

ICPC第一场网络预选赛游寄

CCPC被禁赛，只能打ICPC了

按照之前的开题顺序，我开中间四题。然后就发现 F 题是之前 HDU 的原题，然而是个重量级的数论，上次我们就没过。读着题的时候，破壁人就说 L 很签，上机写了一会，又突然说假了。于是我就上去签 H，在 17 分钟过了。这个 H 的题面就非常灵性，让我更深刻的理解了 CCPC “比赛中不能打开头文件”的规则。 H 题面：啪的一下，很快呀 wky 就说 C 也是签到，遂在 22 min 通过。此时，由于我们手速飞快，排名在第五，这也是整场比赛排名最高的时候。于是我开了 G，wky 开始构造 D。过了一会，wky 想出一个构造，于是开写，然而样例挂了。于是我就胡了一个 $...

Posted by ethan-zhou on September 18, 2022

关于联名抗议 CCPC 全校禁赛的提议

联名呼吁已经在 2022 年 9 月 18 日通过反馈平台提交。今天收到了 CCPC 组委会发布的以下通知：我们理解并支持诚信参赛，公平竞争。对作弊行为必须零容忍，必须严格处理。对于作弊者，作弊队伍来说，一切后果都是咎由自取。但是，对于其他诚信参赛的队伍来说，这样“一人犯法，株连九族”的连坐，则极为不公平。这样的连坐制，既不公平，也起不到相应作用，而且会起到反作用。其一，对于没有违规的队伍是极度不公平，且没有意义的——本无过错却要接受严厉的惩罚。这样的处罚起不到杀鸡儆猴的作用——因为在赛前，学校老师学长等等都已经多次强调过参赛规则，然而还是有队伍明知故犯，以身犯险...

Posted by ethan-zhou on September 12, 2022

更换域名通知

重金购入 www.blog-e.top 域名！

freenom 的免费域名 www.blog-e.tk 用了一年，又过期了，而且无法免费续约。而且我也受够了一年换一次域名。终于咬咬牙，花了二十块巨款在腾讯云上面买了个 www.blog-e.top，最近还在配 DNS 解析什么的，访问和评论功能可能会有一些问题。

Posted by ethan-zhou on September 10, 2022