从 Open Source 到 Self Hosting

最近 推上 传出一张有趣的图,Richard Stallman 受邀跑到 Microsoft Campus 去宣讲自由软件,欢乐之余,也让我们不得不赞叹纳德拉确实有一套,这样的场景放在十年之前,恐怕是谁都不敢想象的吧?那一年比尔盖茨来北大演讲的时候,底下可是还有人高举 FOSS 的大旗抗议呢。。。(我还记得我认识开源哥的时候,他的头像自己是脚踢微软中国的照片呢。。。后来变成了西木野真姬。。就是题外话了。。)

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

PT07Z

批改 作业 时间。显然有两个问题:
– 数据没有从 IO 读入读出。
– 第一个 dfs 求出的不是最远的端点。

不过我修改了之后目前依然没有通过 SPOJ 的测试。支持 Javascript 的 OJ 也很少,
Codeforces 上 Javascript 的提交也远不如其他语言。
如何在 SPOJ 提交 Javascript?这个链接 下面附了一个 Life, the Universe, and Everything 的 JS 标程。

let vertexLen = parseInt(readline().trim()); // 顶点数
let vertex = new Map(); // 顶点数据集合 map 可以设置键对值 0 1 2 3 4 5 or 1 2 3 4 5 6 or A B C D E F G ... ...

/**
 * 设置顶点
 * @param {String || Number} v 顶点
 */
const setVertex = v => vertex.set(v, []);
/**
 * 设置边
 * @param {String || Number} v1 点
 * @param {String || Number} v2 点
 */
const setVertexEdge = (v1, v2) => {
  vertex.get(v1).push(v2);
  vertex.get(v2).push(v1);
};

// 设置点
for (let i = 1; i <= vertexLen; i++) setVertex(i);

// 定义边
let vertexEdge = [[1, 4], [2, 4], [3, 4], [4, 5], [5, 6]];

// 设置边
// for (let i = 0; i < vertexEdge.length; i++)
//   setVertexEdge(vertexEdge[i][0], vertexEdge[i][1]);
for (let i = 0; i < vertexLen - 1; i++) {
    var edge = readline().trim().split(" ").map(function(x) { return parseInt(x); });
    setVertexEdge(edge[0], edge[1]);
}


/**
 * dfs
 * @param {String || Number} startNode 开始点
 */
const dfs = startNode => {
  let visited = new Map(); // 保持和顶点结构一样
  let f = startNode;
  let z = 0;
  for (let i = 1; i <= vertexLen; i++) visited.set(i, false); // 设置访问状态

  // dfs 方法
  const dfsFunc = (startNode, visited, dep) => {
    if (dep > z) {
        f = startNode;
        z = dep;
    }
    dep += 1;
    visited.set(startNode, true); // 第一个点设置已访问
    let get_next = vertex.get(startNode); // 获得顶点的所有临接点
    for (let i = 0; i < get_next.length; i++) {
      // 循环临接点
      let get_elem = get_next[i]; // 得到元素
      if (!visited.get(get_elem)) {
        dfsFunc(get_elem, visited, dep);
      }      
    }
    return z;
  };
  dfsFunc(startNode, visited, 0);
  return f;
};

/**
 * dfs
 * @param {String || Number} startNode 开始点
 */
const dfs1 = startNode => {
  // 记录开始点和父级节点
  const dfsFunc = (startNode, parentNode = -1) => {
    let z = 0; // 记录长度
    let get_next = vertex.get(startNode); // 得到相邻节点
    for (let i = 0; i < get_next.length; i++) { // 循环点
      let get_elem = get_next[i]; // 得到点
      if (get_elem === parentNode) continue; // 如果是父节点 跳过
      z = Math.max(z, dfsFunc(get_elem, startNode) + 1); // 递归添加长度
    }
    return z;
  };
  return dfsFunc(startNode);
};

let z = dfs(1);

// console.log(z);

let z1 = dfs1(1);
// console.log(z1);

print(z1);

// console.log(vertex);

勿让权钱交易腐蚀学科竞赛的纯洁性

子曰:「有教无类」
—— 《论语·卫灵公》

最近几天 NOIP 停办的事情牵动着很多 exOIer 们的心,看到好友圈纷纷晒出自己当年的 NOIP 1= 的奖状,我们现在或活跃在学术一线,或在互联网公司搬砖,无不是化为一颗社会主义的螺丝钉,为实现四化燃烧着生命在做贡献。

「最迷人的果然还是中等数学啊」,对我而言,我当然对学科竞赛有着特别的感情。对于我这样的问题学生,按部就班的好好学习文化课似乎无法调动我的兴趣,且不说家里一书柜的各类学科竞赛的题集,小升初、初升高、以及大学也都是一路,最后都是靠着那一点微薄的竞赛加分,最后得以逃出生天的。吃水不忘挖井人,而这一切的源头,就是 NOIP。

这里说一则佚文,事实上我的那个决定我一生命运的 NOIP 1= 的奖状,似乎被我撕成了碎片(虽然后来我妈又拿胶水粘起来了)。原因是,那一年高一的暑假,郑州办 NOIP 培训班,我想去参加,但是报名费要 6000 块,然后我妈就不想让我去参加(事实上原因应该不仅仅是 6000¥,还有担心影响我文化课,以及一个人出远门不放心等。。。),事实上不仅没有让我去参加,还在市内带我去科大找可以辅导我的老师,(当然是不存在啦),总之原本抱着巨大期待的我,感觉被我妈玩弄了几天,一气之下,把我贴在墙上的从小学到高中的奖状全部撕了。

当然后来要感谢网购,感谢当当,至少我还可以有办法自学。。。但是无论如何,学习效率一定是差很多的,主要是中间如果卡住了,没人指点可能就跳不出来了。

当然我这里不是要鼓吹教育平权什么的,我只是认为,NOIP 联赛作为信息学奥赛里最普及最基础的部分,不应该被过多的无关因素牵连,她应该是公益的,纯粹的,无差别的。

Google Code Jam 2019 World Finals

Google Code Jam 2019 World Finals

今年的 Code Jam 结束了,一不留神 Tourist 又^6 夺冠了。。。
先来看一下 Final 的题目吧。

Board Meeting

Brief Description

交互题。给定一个无限大的棋盘,上面摆放了至多 n 个国王。准备阶段,你可以进行询问至多 r 次,每次询问一个坐标,系统返回所有国王距离这个坐标的距离和。之后,询问阶段角色互换,系统会向你询问至多 r 次,每次询问一个坐标,你需要返回所有国王距离这个坐标的距离和。

(每个国王的坐标绝对值不超过 m,询问的坐标绝对值不超过 10m)
(n <= 10, m = 1e6,r = 1000)
(小数据中,n = 1)

Idea

先考虑一个点的情况?回忆航海里的三角测量以及 GPS 里的三点定位?
对于大数据,有办法可以得到每个点的坐标吗?需要得到每个点坐标吗?

Sorting Permutation Unit

Brief Description

你需要将 k 段长度为 n 的数组按照非递减顺序排序。排序的方法是使用你自己构造的置换。你可以至多构造 p 组置换,每次排序可以使用这些置换不超过 s 次。

(k <= 30, n <= 50, s = 450)
(Small: p = 20)
(Large: p = 5)

Won’t Sum

Juggle Stuggle Part

Brief Description

平面内给出 n 条线段,称这组线段是相融的,如果他们两两相交。
– Part 1: 给定 2n 个点,构造一组相融的连线方式,数据保证一定有解。
– Part 2: 给定 n 条线段,判断它们是否相融。

Idea

Go To Considered Helpful

Brief Description

给定一个 r*c 的迷宫,要求构造一个长度最短的带 Goto 的指令序列,可以从起点走到终点。

(Small: r,c <= 10)
(Large: r,c <= 100)

比特币十万刀,会发生什么?

比特币十万刀,会发生什么?

看了小伙伴发来的 Tony 周末在杭州的演讲1,感觉茅塞顿开,解答了我心中诸多疑惑。之前比特币上一万刀的时候,我还 煞有介事的做了一些分析,现在看起来这些因素其实都无关痛痒。因为影响币圈的还有一个最重要的因素,就是外部性。Vitalik 说,大多数人困于系统,而我生活在系统之外。Tony 的这次演讲告诉我们,理解币圈也需要跳出币圈系统,看全球市场的脉搏。

我之前说,对待市场,要使用 归纳的态度,Tony 则告诉我们,市场总是对的,通过阅读市场我们有理由获得一些知识。我们反过来演绎,比特币十万刀,会发生什么?实际上反而是,发生了什么,比特币才会十万刀。

那么我认为答案应该很明确了,十万刀等价于 Mainstream Adoption。

比特币作为平行世界的资产选择最关键属性,在于其作为 Hard money 带来的 Self-sovereignty(硬资产带来的强所有权,就是钥匙在币在,自己对资产有绝对的所有权和控制权)。这意味着比特币在当地法币严重超发与崩盘时,确实有对于区域性货币危机的避险功能。

在长期看来,比特币对冲的是世界范围的系统性货币危机。在中短期来看,比特币更多是作为一种有强所有权的硬资产,来抵御暴力机构对私有财产的肆意征收和强行割让。二战时期德国纳粹接近 1/3 的军费来源是靠收刮和剥夺犹太人财产所得,生在和平年代的我们,也许还意识不到私有财产所有权的重要性,但是那一天来临的时候,没有私钥的你会被残酷的现实冲击的措手不及。
—— 《比特币不是避险资产 , yet》

Dovey 之前也描述,比特币对冲的是世界范围的系统性货币危机,而不是传统意义上的避险资产。因而我认为,仅仅依靠减半显然是不足以推高到十万刀的。

必然在市场之外发生了什么。


  1. 还没看的赶紧去看:Tony,通证经济还有未来吗?。正好当时我正在 上海参加 Frank 参加的另一场 Meetup,参照观看风味更佳。