我的区块链价值观

原文发表在我的独立博客
链闻有授权转载

上文说到,这周末要去北京打 TCO Onsite,考虑到有越来越多的 OIer/ACMer 已经开始参与或者正在考虑参与到 Blockchain Industry 之中(IOST、Tezos、Conflux、etcs),感觉有必要写篇文章以备不时之需。顺便也给最近这段时间对行业的理解做个阶段性总结。

归纳的态度 Inductive Attitude

区块链是一个很多学科交叉汇集的地方,她的快速演化使得我们必须要以谦卑的姿态虚心的更新着自己的认知。按照波利亚的话说,我们应该抱有归纳的态度1来理解正在发生的事情。

这其中自然也包括货币化与自由市场。亚当·斯密(Adam Smith)使用 看不见的手(Invisible Hand)来隐喻其中所隐含的秩序。虽然她 偶尔也会失效,但是我们今天绝大部分的世界仍旧依照着她的指引运行并演化着,有兴趣的读者可以去读《致命的自负》,这里不再赘述。

所以当这个圈子隔三差五出现,某某是不是骗子,某某盘是不是骗局2这样的讨论时,我应该抛给你的是一个概率分布 —— 我分别是有百分之多少的概率认为它是有百分之多少的骗局(革命)成分的。

作为裁判的自由市场 Free market as a Judgementor

而最后判断我们的猜想正确与否的唯一 Criteria,就是币价和市值。资金盘之所以为资金盘,就是她有一天会崩盘。显然我们应该参考所有人用真金白银做出的判断。下面这副颇为有趣的名为「区块链又革命了」的迷因(Meme)之所以能够广为流传,就是反映了上面所说的观点。

最近有人提议 港人进行大规模的换汇冲击联系汇率以抵抗某条例,如果真的能够被执行,那其中所蕴含的力量将会是十分惊人的。咳咳,Out of topic 了。3

商业能够创造财富,劳动则未必。人们通过交易实际上将自己所掌握的信息通过自由市场广播出去,市场则会给予正确的信息予以恰当的激励。自由市场足够的复杂,被教做人的故事屡见不鲜4。虽然她将每个 individual 所掌握的零零碎碎的信息汇集成一个 indicator,但这个 indicator 同时也会包含诸如市场的情绪、假新闻、贪婪或恐惧、Hype or Fear 等噪音。仅仅通过市场去寻求真理显然会落入缘木求鱼的圈套,但市场至少是一个好的裁判,币价不会说谎,她诚实的反应了群体5所掌握的所有信息。而当我们动态的审视这个指标变化的过程时,我们有理由相信自己已经取得了某些进展。

当我们的知识不足以让我们进行判断时,不妨求助于集体的智慧,以自由市场来作为我们的 Single Source of Truth。

Right. Otherwise we couldn’t have a finite limit of 21 million coins, because there would always need to be some minimum reward for generating. In a few decades when the reward gets too small, the transaction fee will become the main compensation for mining nodes. I’m sure that in 20 years there will either be very large transaction volume or no volume.
—— Either… Or!, 21 Wise and Funny Bitcoin Quotes by Satoshi Nakamoto

所以就连中本聪自己也不能判断 Bitcoin 究竟是不是革命,但自由市场可以。

ゆっくり読んでください …

GCJ 2019 Round3 B

Problem B. Pancake Pyramid

Brief Description

给定长度为 n 的序列 h[i]。
每次你可以选择一段连续子序列 [l, r],你可以给其中某些项执行 +1 操作,使得操作后形成一个金字塔形状(先递增再递减)。
问遍历所有的子序列,总操作次数最少是多少。

Analysis

相同元素可能会带来重复计数,我们统一先认为相同的元素出现时,左边的更大。

考虑暴力做法。注意到我们这里 只有 +1 操作,所以可以直接贪心。
每次枚举区间,设:
– M[l][r] 表示 [l, r] 区间最大的数的位置。
– L[l][r] 表示把 [l, r] 这个区间处理成递增序列的最小代价。
– R[l][r] 表示把 [l, r] 这个区间处理成递减序列的最小代价。

那么我们枚举所有的区间,统计所有 L[l][m] + R[m][r] 就是答案,可以预处理这些数组,复杂度 O(n2),可以过小数据。

考虑大数据,其实题目里已经疯狂暗示你了要用单调栈(stack)。。。
回忆 POJ 2559. Largest Rectangle in a Histogram

我们发现之前是要处理出,以 h[i] 为最低点,左右两边分别可以延伸多远。
这里恰好是求,以 h[i] 为最高点,左右两边分别可以延伸多远,假设就是 Dl[i] 和 Dr[i]。
这样唯一不同的是,我们还需要一个累计代价数组 Sl[i] 和 Sr[i],分别表示以 h[i] 为最高点,往左和往右累计的代价。
因为最后答案就是:
$$\Sigma_{i=1}^n Dl[i] * Sr[i] + Dr[i] * Sl[i]$$

我们可以在维护单调栈的过程中,顺路求 Sl 出 Sr。不放考察从左往右扫描求 Dl 的过程。
设当前扫描到位置 i,将要被弹出的栈顶元素为 sp,这个位置右边一直到 i 这个区间现在都至少需要是 h[sp] 的高度才符合要求。
记这个代价为小写的 sl,我们预处理部分和后可以 O(1) 的求出 sl。记新的栈顶元素的位置与刚才被我们弹出的栈顶元素的位置之间的距离为 sp – s.top(),
sl 需要被统计 sp – s.top() 次。最后加上这个区间本身的代价 Sl[sp]。

stack<int> s; s.push(0); REP_1(i, n) {
    Sl[i] = 0;
    while (h[i] > h[s.top()]) {
        int sp = s.top(); s.pop();
        Int sl = Int(h[sp]) * (i-sp-1) - (hh[i-1]-hh[sp]);
        Sl[i] += sl * (sp - s.top()) + Sl[sp];
    }
    Dl[i] = i - s.top();
    s.push(i);
}

TCO 2019 2B

Beijing Onsite 的热身,不过居然晋级了,下一场还是好好打(受虐)一下吧。。。

250 MedianFaking

Brief Description

给定 n 个人,每个人有 m 个测量结果。取所有人所有测量结果的中位数(偶数时下去整)为最终结果。
已知测量结果应该是 goal,问至少修改几个测量结果可以使得结果恰好为 goal,在这种情况下最少需要参与修改的人数又是多少。

Analysis

如果要让结果恰好为 goal,那么比 goal 小的数和比 goal 大的数都不能超过一半,显然这两边只会有一边不符合。
于是我们只要关心这一边需要修改几个数就好了,并且现在只需要考虑一边,第二问只要统计出每个人可以带来的贡献,排序贪心即可。

500 DivisorSequences

Brief Description

给定 n,我们将 n 拆分成若干个整数相加的形式:n = a1 + a2 + … + am。
要求 a 序列严格递增且 a_i 整除 a_{i+1},问 m 最大可以是多少。

Analysis

观察 15 = 1 + 2 + 4 + 8…
我们发现如果把 1 去掉的话,有 14 = 2(1 + 2 + 4)…
这样我们就发现了一个子问题!
定义 f(n) 表示将 n 分解,并且第一个数是 1 的方案数,每次减去 1 后枚举约数递归即可。那么实际的答案可能第一个数不为 1,所以开始再额外枚举一次约数就好。
复杂度虽然不太容易估计,但貌似不记忆化也能过。

1000 SlightlyBigger

Brief Description

Alice 和 Bob 报数,从 1 到 oo,目标是比对方报的数只大一点。
– 如果恰好差小于等于 maxDiff,那么大的一方获胜,并得到 ifNear 分。
– 否则,小的一方获胜,并得到 ifFar 分。

双方都采取最优策略时,问 Alice 报的数恰好为 query 的概率。
(ifNear < ifFar <= 2×ifNear)

Analysis

第一眼感觉这个题很神,看了一下大家后来都是高斯消元做的。但是不知道怎么列方程。后来请教了一下毕克老师,毕老师说其实这个问题跟剪刀石头布是一样的,就你想象一个剪刀石头布游戏,然后给你一个收益矩阵。
对方把自己的策略的概率分布向量已经告诉你了,在最优情况下,你发现你即便知道这个向量也并不能让你取得任何优势。
这就是传说中的 纳什均衡,于是只要设表示报 x_i 的概率,根据上面这些关系,列出线性方程组,高斯消元即可。

纳什均衡虽然提供了 n 组方程,但是 rank 似乎是 n-1 的,最后别忘了加上所有概率分布之和等于 1。
可以预计答案不会很大,可以带极限数据跑一下看看边界。