Problems：https://codeforces.com/contest/1651

D. Nearest Excluded Points

题目

给定平面上$n$个点，第i个点坐标为整数$(x_i, y_i)$。定义两个点之间的距离为 $|x1-x2|+|y1-y2|$，也就是曼哈顿距离。

对这n个点中的每个点，输出一个距离它最近的整数坐标点$P_i$，并且$P_i$不能在输入的$n$个点里。

$1\le n\le 2\times10^5$，$1\le x_i,y_i\le10^9$

题解

发现很难直接求。但我们可以发现，“可能成为答案的点”一定是紧挨着某个输入的点！一共$4\times n$个可能成为答案的点，将它们全都放到队列中开始BFS。BFS过程中只能走输入的点，同时记录答案即可。时间复杂度O($n$)。

另一种做法

考场上写了一种智障解法，但感觉也是值得一提的。

首先考虑曼哈顿距离最近的点，距离一定不超过$\sqrt n$。因为最坏情况就是$n$个点聚成一坨，成为一个边长为$\sqrt n$的正方形。

对于每个点，如果我们能确定答案距离是多少，那么就可以在O($\sqrt n$)点时间里找到这个答案。因为距离每个点距离为$d$的点总共有O($d$)个，依次枚举判断即可。

同时，曼哈顿距离与切比雪夫距离是可以相互转换的。将$(x,y)$转化为$(x-y,x+y)$，两个点的曼哈顿距离等于新坐标下的切比雪夫距离 $\max(|x1-x2|, |y1-y2|)$。那么距离点$P$距离不超过$d$的点，都在以点$P$为中心，边长为$2\times d+1$的正方形中。

先转化为切比雪夫距离，对每个点，二分这个$d$，用树套树求这个正方形内点的个数（或者用可持久化线段树，少一个log）。找到$d$之后，O($\sqrt n$)求答案点。

如果用可持久化线段树的话，总时间复杂度 O($n\sqrt n+n\log^2n$)，应该也可以过。但考场上没时间了，就写了个O($n\sqrt n\log n$)的，超时。

E. Sum of Matchings

题意

给定一个二分图。左边是节点1到n，右边是节点n+1到2n。并且，每个节点的度数都为2。不会有重边。

定义 $G(l,r,L,R)$ 表示左边选$l$到$r$，右边选$L$到$R$，这些点选出来形成的子图。对于所有的子图 $1\le l\le r\le n$，$n+1\le L\le R\le 2n$，求它们的最大匹配之和。

$n \le 1500$。

题解

因为每个点的度数都为2，整个图就是由一个个环组成的。

考虑每一条路径，统计它在多少个 $G(l,r,L,R)$ 中出现过即可。

如何统计？需要这条路径在子图中没有延伸出去，只需要两端点之外的两个点不在区间范围内即可。乘一乘就可以了。

时间复杂度O($n^2$)，为枚举所有路径的复杂度。

F. Tower Defense

题意

不想翻译了 https://codeforces.com/contest/1651/problem/F

题解

首先，塔的位置其实可以认为都在0点（但顺序仍要保持）。因为对于第$i$个塔，第$j$个怪会在$t_j+i$秒到达它，下一个怪会在$t_{j+1}+i$秒到达，相当于它在0点。

如果某个怪$j$打穿了所有塔，那么相当于所有塔从$t_j$时刻从0开始恢复。

如果某个怪$j$没有打穿所有塔，在第$k$个塔停下来了，那么第1到$k-1$个会从$t_j$时刻从0开始恢复。第$k$个塔会剩一些血，然后$k+1$到$n$还是按之前的恢复进度。

相当于一个怪，最多会将塔变的多两段。对于每一段，如果我们能用某种数据结构维护，那么就解决问题了。

残血的塔每次最多1个，暴力维护即可。我们需要考虑的是，对于从$from$到$to$这一段连续的塔，都从$t$时刻开始从0恢复，如何维护。最开始所有塔都满血，也可以认为所有塔是从-inf时刻开始从0恢复。

如何维护呢？我们注意到，一段塔能打掉的血，取决于当前时间$now$与$t$之间的差值，记为$dt$。如果$dt\ge c_i/r_i$，记录这些塔的$c_i$之和即可，否则记录塔的$r_i$之和，乘以$dt$即可。

可以用线段树套平衡树维护。线段树维护1到n（用来请求$from$到$to$），每个节点上的平衡树（也可以线段树）按$c_i/r_i$作为key，维护$\sum c_i$和$\sum r_i$。当然考虑一下可以发现，我们没有插入删除塔的操作，所以可以按$c_i/r_i$排序，用可持久化线段树维护。对每个$dt$二分查找root。

如果怪不能通过某一段塔，直接在线段树上二分查找$k$。总时间复杂度O($n\log n$)。

代码

https://codeforces.com/contest/1651/submission/149749827

题目

https://codeforces.com/contest/10/problem/E

一个整数硬币系统，满足c[1] > c[2] > … > c[n]，且c[n] = 1。

对于钱数w，为了用最少的硬币数表示出w，有一种贪心算法：不断地取<=w的最大的c[i]，然后w-=c[i]。例如人民币来说，128就可以表示成100 + 20 + 5 + 1 + 1 + 1，共6张钱，也是最优的。

显然这种贪心算法不一定总能得到最优解。例如货币系统4,3,1，当钱数w=6时，贪心算法会得到4+1+1共3个硬币，但最优解是3+3共2个硬币。

现在给定c[1..n]，问这个硬币系统会不会出现贪心算法得不到最优解的问题。如果会出现，那么求出最小的w，使得贪心算法失效。n<=400，0<=c[i]<=10^9。

题解

这道题就是论文《A Polynomial-time Algorithm for the Change-Making Problem》讨论的问题。下载：https://drive.google.com/file/d/1u8fMFGA4myi2ZgJL3TDoNGe6EHH1w16e/view?usp=sharing

以下内容基本是翻译论文内容。

首先，给定c[1..n]和w，要得到w的最优解，是NP-Hard的。要判断对w来说，贪心算法是否是最优解，也是NP-Hard的（虽然这个问题比上面的问题简单一些）。

但是，判断是否存在某个w使得贪心算法失效，以及求出这个最小的w，却有O(n^3)的多项式解法。这跟前面两个NP-Hard的问题并不矛盾。

首先定义硬币系统为 $C=(c_1,c_2,…,c_n)$ 是一个n维向量。定义一个组合为 $V=(v_1,v_2,…,v_n)$ ，那么 $w=V\cdot C=\sum_{i=1}^nv_ic_i$ 就是这个组合得到的钱数。定义$|V|=\sum_{i=1}^nv_i$。

对于$w$来说，设由贪心算法得到的组合为$G(w)$，最佳组合为$M(w)$。我们的问题就是，求最小的$w$，使得$|G(w)|\gt|M(w)|$。如果有多个最佳组合，$M(w)$为字典序最大的那个。

定义两个$n$维向量的小于关系：$U<V$，代表$U$的字典序小于$V$。定义包含关系$U\subset V$，表示对任意$i$，都有$u_i\le v_i$。

我们可以证明几个性质：

1. 如果$a\lt b$，那么字典序$G(a)\lt G(b)$。但对于$M$不具备此性质。
2. 对于任意可以表示出$w$的组合$V$，都有$V\le G(w)$。也就是说，贪心算法得到的是字典序最大的$V$。
3. 如果$U\subset V$，且$V=G(V\cdot C)$，那么$U=G(U\cdot C)$。根据贪心过程即可证明。
4. 如果$U\subset V$，且$V=M(V\cdot C)$，那么$U=M(U\cdot C)$。根据最佳组合的定义即可证明。

假设$w$是最小的满足$|G(w)|\gt|M(w)|$的钱数。我们可以发现，$G(w)$和$M(w)$一定是不相交的，也就是说如果某个位置i上某一个大于0，那么另一个在位置i上一定等于0。这是因为我们找的是最小的$w$。如果某个位置i上$G(w)$和$M(w)$都大于0，那么$w-c_i$就成了一个更小的满足条件的值。

同时字典序$M(w)\lt G(w)$。假设$M(w)$中第一个非0的位置是i，最后一个非0的位置是j，那么对于$G(w)$而言，它在第i位上必须是0。因此$G(w)$必定在1到i-1之间有非0的值，才能保证字典序最大。这也告诉我们，$i\gt1$。

接下来我们证明Theorem 1：$M(w)$ 与 $G(c_{i-1}-1)$ 在1到j-1位都相同，在第j位上比后者大1，在第j+1到n位都等于0。

证明：

因为$G(w)$在1..i-1之间有非0位置，所以 $w\ge c_{i-1}$。

考虑$w-c_j$，因为$w$是最小的贪心算法失效的钱数，那么必有 $M(w-c_j)=G(w-c_j)$。同时可以发现，$M(w-c_j)$ 与 $M(w)$ 只是在第j位相差1。因为，对于$w-c_j$而言，贪心的时候第一个贪到的数是$c_i$，因此 $w-c_j\lt c_{i-1}$

于是我们得到：$w-c_j\lt c_{i-1} \le w$

对于 $c_{i-1}-1$来说，第一个贪心到的数是$c_i$。我们考虑将第i位减去1，得到 $c_{i-1}-1-c_i$，有 $c_{i-1}-1-c_i\lt w-c_i$，因此有 $G(c_{i-1}-1-c_i)<G(w-c_i)=M(w-c_i)$。那么我们在第i位上加上1，不会改变字典序大小，那么就得到 $G(c_{i-1}-1)\lt M(w)$。

另外因为 $c_i-1\ge w-c_j$，那么$G(c_{i-1}-1)\ge G(w-c_j)=M(w-c_j)$。于是我们得到：
$$
M(w-c_j) \le G(c_{i-1}-1) \lt M(w)
$$

这里的小于是字典序小于。注意到两头的两项只在第j位差1，并且第j位是 $M(w)$ 的最后的非0位置，因此Theorem 1得证。

那么如何找到最小的$w$呢？O(n^2)枚举i和j，求出$G(c_{i-1}-1)$，然后就可以求出$w$，然后再判断一下$w$是否满足条件即可。总复杂度O(n^3)。

代码

https://codeforces.com/contest/10/submission/149007309

思考

问题来了，如果我没看过这篇论文咋整？好像也没啥办法，能想出来的最多也就限于Theorem 1之前的那部分了。可能通过一些打表观察来找到 $c_{i-1}-1$ 的规律吧。

课程主页： https://pdos.csail.mit.edu/6.824/schedule.html 。Spring 2021

在读了DDIA之后，6.824算是巩固和提升吧。

4个lab，可见 https://github.com/xindubawukong/6.824 。目前是private的。

Lectures:

1. mapreduce
2. 介绍go
3. GFS
4. 通过vm-ft介绍Primary-Backup Replication
5. Raft(1)
6. Lab1 Q&A
7. Raft(2)
8. Lab2 Q&A
9. Zookeeper，共识协议的应用

• 分布式锁，以及ready file的例子挺有意思

10. Guest Lecture on Go，没看
11. Chain Replication。我觉得应该先将vm-ft，再讲CR，最后讲Raft比较好。
12. Frangipani，一个小的文件系统，通过锁实现cache-consistency和automacy，通过write-ahead log实现crash recovery
13. Distributed Transactions，2PL和2PC
14. Spanner
15. FaRM，OCC。微软的一个research prototype，内部的读写都通过RDMA。因此使用OCC。
16. Spark，mapreduce的优化版
17. Facebook Memcache。从cluster维度，到region维度，再到global维度，cache系统的设计
18. SUNDR, fork consistency
19. Bitcoin
20. BlockStack
21. 不知道啥玩意。感觉是自动生成的胡说八道论文。

越学越觉得自己不会的东西太多。g

一些没用的context：

• GnuPG入门：https://zhuanlan.zhihu.com/p/396325678
• keybase: https://zhuanlan.zhihu.com/p/23953972，https://keybase.io/xindubawukong
• 对称算法与非对称算法：https://zhuanlan.zhihu.com/p/135358997

paper: https://drive.google.com/file/d/1qVBC4Ku_bRqb7L7SJASsStxnNqrfzlYi/view?usp=sharing

对于bitcoin，其本质就是对于一些transaction达成了consensus。那么我们为什么一定要存储transaction呢？如果我们可以存储任意的log，那么就可以通过这些log构造出state machine，从而可以实现decentralized applications。

具体看论文里的那图吧。

paper: https://drive.google.com/file/d/14AXiW1kFylpoj_uSVUqdHga493_1rLox/view?usp=sharing

比特币白皮书 个人翻译+注解 - 金晓的文章 - 知乎
https://zhuanlan.zhihu.com/p/25039679

核心思想：去中心化的货币系统。因此需要统一的log。所有交易必须公开。

那么谁来决定交易的顺序呢？proof of work。

其他都是一些细节了，比如每个transaction的结构，每个block的结构等。

昨天面了个试gg了，代码没写完，因为找思路的时间太长

题意

有一个S3的storage的接口是

1

void read(int offset, int limit, char* output);

但是这玩意贼慢。要你实现一个CacheReader，来优化clients的read操作。最多能存n bytes的数，尽量少直接请求S3。

做法

一开始想的复杂了、、因为每个read都有一个[l,r]区间，然后我就在想怎么维护这些区间、、忘了OS课上讲的东西了。

其实这种很明显，得自己定义一个pageSize。不然怎么实施缓存替换策略？分成固定大小的块之后，各种处理都会变得简单很多。比如GFS，要是按照各个文件的长度分配磁盘那不就要了老命了。

缓存替换用LRU就行。

面的太二了。惭愧。

行程安排：

同行：mingfei, claire dai, yixin, kylie, huyang。

太累了。。懒得写了。到祖国的西北边陲看了看。

挺神秘的一个题，题意自己看吧 https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted/

先写一个暴力做法，然后找规律。需要用到快速幂。太麻烦了，懒得讲了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
    int ksm(int a, int b, int c) {
        int res = 1;
        while (b > 0) {
            if (b & 1) res = (long long)res * a % c;
            a = (long long) a * a % c;
            b >>= 1;
        }
        return res;
    }

    int get_ans(string s) {
        int n = s.length();
        int mo = 1000000007;
        vector<int> f(n + 1);
        vector<int> ni(n + 1);
        f[0] = 1;
        f[1] = 1;
        ni[0] = 1;
        ni[1] = 1;
        for (int i = 2; i <= n; i++) {
            f[i] = (long long) f[i - 1] * i % mo;
            ni[i] = ksm(f[i], mo - 2, mo);
        }
        int ans = 0;
        vector<int> num(26);
        num[s[s.length() - 1] - 'a']++;
        for (int now = s.length() - 2; now >= 0; now--) {
            num[s[now] - 'a']++;
            int tmp = f[s.length() - now - 1];
            for (int j = 0; j < 26; j++) {
                tmp = (long long) tmp * ni[num[j]] % mo;
            }
            for (int i = s[now] - 'a' - 1; i >= 0; i--) {
                if (num[i] == 0) continue;
                int qq = (long long) tmp * num[i] % mo;
                ans = (ans + qq) % mo;
            }
        }
        return ans % mo;
    }

public:
    int makeStringSorted(string s) {
        return get_ans(s);
    }
};

行程安排：https://docs.google.com/spreadsheets/d/1VkhQElkOJj09VeKx8KFxPrEk5cT5VYK22OEuY01N58c/edit?ts=606db7a6#gid=0

4.11: 晚上到达普洱机场，提车去listing，然后去逛了茶马古城。回listing打阿瓦隆

4.12：上午去咖啡庄园，下午去小熊猫庄园。晚上吃烧烤，玩uno

4.13：开车去西双版纳。路上撞车了。处理完之后，下午去曼掌村摸鱼。晚上逛夜市。

4.14：西双版纳原始森林公园，丛林飞跃。下午吃了傣家饭，然后还吃了很多乱七八糟的东西。晚上回去之后开始上吐下泻。

4.15：坐了一天车到达元阳大山里的listing。休息一晚上。

4.16：早起看梯田。开车去建水listing。晚上逛建水古城。

4.17：坐建水的小火车。下午开车到昆明，晚上回北京。

说实话，旅游确实是刚需。我以前一直觉得只有衣食住行才是刚需。但是对于有点闲钱的人来说，娱乐活动是必不可少的。疫情结束之后必然是旅行的爆发。但根据相关法律，本人不对ABNB股价有任何看法。

另外，现在的租车也太方便了。以后自驾游全都可以参考这次。以及，开车技术也很重要。以后有机会也要多练。

感谢同行的mingfei, simeng, claire dai, kylie, shu, ashley lei。

此情可待成追忆，只是当时已惘然。

题目

https://leetcode.com/problems/make-the-xor-of-all-segments-equal-to-zero/

给定一个数组a和一个整数k。对于a中任意长度为k的连续子数组，要求其中的元素xor和为0。最少需要修改a中的多少个数？

a.size <= 2000, a[i] < 1024

做法

https://leetcode.com/submissions/detail/465921930/

脑子要灵活。不要看啥就是啥。

很容易发现1到k个数与k+1到2k个数是一样的。因此我们只需确定前k个数，使其xor为0即可。

容易想到dp：f[i][j]表示前i个数xor和为j，最少修改多少个数。

看上去是一个O(n^3)的，但实际上只需枚举i有限几个值即可。另外的可能的值转移过程都是一样的。因此时间复杂度O(n^2)。