一个最坏复杂度到平均复杂度的规约

本文是ECCC TR18-138(FOCS2018最佳学生论文奖之一)的一个笔记。由于(笔者个人观点)论文写得比较晦涩,而idea本身比较简洁,所以我在这里会试着讲得更加科普向(>_>),可能会为了直观性而一定程度地放弃严谨性。另外,笔者也只是刚刚理解了论文的大致思路,因此可能会有错误之处,烦请各位批评指正。

本文假设读者有本科计算理论的背景,例如知道$\mathsf{P},\mathsf{NP}$的定义,知道规约的概念。

阅读全文

codeforces April fool contest 2018

提示:这篇文章的主题是code-golf(即写出尽可能短的代码),使用的语言是Python 2/3。这篇文章含有cf April Fool contest 2018的剧透。

(除草。。还没更完,看心情更。。

继续阅读

IBM Ponder this 2018 August

诈尸(

阅读全文

IBM Ponder this 2018 April

这题其实可以手算。

继续阅读

IBM Ponder this 2018 March

10个月没做IBM了。。

继续阅读

强制戒毒工具

chrome + tampermonkey禁止自己访问知乎。

继续阅读

codechef FEB18

提示:由于排版需要,我的Editorial使用了[hide][/hide]标签,不科学上网这个标签就用不了,所以请大家科学浏览Editorial。(不过说起来不科学浏览的话,公式什么的也显示不了吧。

继续阅读

均摊分析三连

又称“膜拜Tarjan三连”。

(upd:完结撒花!

实际上是某算法课的一个笔记。不过我猜考试不考

继续阅读

Uyhip2017 October

贵站倒闭了。。。呜呜呜

10月30的晚上开始刚T3。。刚出一个正好为$N$的解。。然后发现脑细胞不够用了。。

就没有赶上贵站的最后一个riddle。。。

可能会看心情更T3,但是更可能会烂尾(毕竟期中考试)。目前更到:答案$\le N$。upd:居然找到原题

继续阅读

codechef LTIME52

居然达成了0人AC的成就。。。虽然这不是我的本意。。。

继续阅读