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,參照觀看風味更佳。 

Have we borrowed too much?

Have we borrowed too much?

Rule 1 : Don』t have debt rise faster than income. (because your debt burdens will eventually crush you.)
—— How The Economic Machine Works by Ray Dalio

在下一篇關於廣告的文章之前,我想先討論一組關於債務的問題。畢竟現在已經到了一個是個 App 就會有白條或白條廣告的時代了。

前段時間在家裡看 Tmono 看《長安十二時辰》。聽 Tmono 說,這是一部質量上乘的網劇,服飾考究,節奏明快,甚至稍微有一點美劇的意思。不過這部大紅網劇,戳中我的居然不是劇情本身,而是在中間,插入的遠遠比我所能夠接受的多得多的 P2P 網貸產品的廣告。

為什麼我認為《長安十二時辰》是一顆毒藥?我看了前 4 集就棄劇了,主要原因在於每每看到精彩處,中間就會穿插一個 P2P 理財廣告,讓我尷尬症都犯了。以下是幾張廣告的相關截圖,植入的推廣文案都非常簡單粗暴。而且,這些廣告的植入主要偏向於從安全、收益穩定、讓你賺錢的角度,讓你去信任這些網貸理財產品,風險提示語卻非常小。
—— 年輕人,為什麼說四字弟弟主演的《長安十二時辰》是一顆毒藥?

網上搜了一下,看來果然不止我一個人吐槽這件事。截止目前為止,這部網劇里出現的互金公司的廣告就已經有和信貸、愛錢進、悟空理財、PPmoney 和人人貸。以人人貸為例,事實上早在《軍師聯盟》里,就出現了 這種互金廣告,套路和《長安十二時辰》里的也如出一轍。

除了網劇,這些網貸平台還瞄準了直播平台這些年輕人聚集的地方。一個鬥魚 DNF 主播寶哥,曾經就在他的直播間里強烈譴責鬥魚掛人人貸廣告的行為,並提醒他的粉絲理性看待網貸。而在這則視頻的評論區,就有很多人記錄了自己身邊的案例。

《長安十二時辰》里有一個橋段,說有賊人給算不清賬的老人放印子錢(古代的高利貸),滾出幾十倍的利,然後收房搶閨女,最後還拒捕。而網貸產品也選擇把目標瞄準了風險意識不足年輕人,並且,這種透支未來的情況不僅僅只有 P2P 借貸,還有 貸款培訓貸款租房,各種五花八門的 P2P 形態也層出不窮。

1年虧損凈6億元,達內教育「欺詐招生」也無法扭轉僵局。目前,市面上部分教育機構通過與一些金融平台合作的方式,提供教育分期業務。簡而言之,學生可通過向合作的金融機構借款支付學費,再以分期的方式來償還借款。

而除了虛假宣傳、誘導貸款外,教育分期的另一弊端便是貸款付費的模式難以維繫。不少培訓機構在收取學生費用後失聯,無處上課的學生,同時還將承擔高昂的學費。
其中,2016年12月,在北京開辦近10年的北京環球美聯英語培訓機構突然停業,老闆跑路失聯,但學員們的課程並沒有學完。據了解,涉及學員超過500人,課時費從幾千元到幾萬元不等。
—— 達內教育「花式割韭菜」:誘導學員貸款 2018年虧損近6億元

這個案例不禁讓我想起,多年之前廖老師和我提到的 美國學生貸款(Student loans in the United States)。美國的大學教育普遍很昂貴,哪怕對於很多中產階級,特別是私立學校,學費是全美國統一的。含住宿的話學費在 $40,000 – $60,000 左右一年。特別是美國的文化比較崇尚小孩 18 歲以後獨立在社會闖蕩,盡量少的得到家庭的資助。這也是為什麼許多大學生習慣貸款付學費如果父母收入不高的話。

助學貸款通常被認為是好債,學生還款剛性強。它的利率的確有吸引力,相比銀行 5.5% 的貸款利率、汽車消費貸 5.05% 的利率,美國本科聯邦學生貸款利率為 5.05%、研究生為 6.6%。
但這也讓很多人高估了自己未來的還貸能力,巨大的壓力面前,許多人將戰線越拉越長。彭博全球數據顯示,超過十分之一的借款人至少逾期 90 天,目前嚴重違約率已經達到 9.1%的新高,而抵押貸款和汽車貸款的違約率分別為 1.1% 和 4%。
—— 好奇心日報,美國助學貸款規模達到 1.56 萬億美元,僅次於住房抵押貸款

根據 維基百科的資料NCES 在 2018 年的一份統計,12 年學生貸款的違約率為 52%,這個數字在非裔族群里是 65.7%。在一份 布魯金斯學會(Brookings Institution) 同年的調查報告里,指出 “近 40% 的在 2004 年借出的學生貸款將會在 2023 年遭遇違約”。

學生貸款是非極個別情況下,唯一不能隨著破產申請而一筆勾銷的債務。一些批評人士認為,學生貸款正在逐漸演變為加在美國底層民眾身上的一種 「奴役契約」,讓學生用未來勞動償還教育成本,並潛在地影響了學生的學習和職業選擇,是資本主義的至惡。

要知道,債務是危機的種子,美國次貸危機才剛剛過去 10 年而已。我們確定要把這種東西也 Copy to China 么?

參考資料

廣告:惡之源頭

UPD:http://jacek.zlydach.pl/blog/2019-07-31-ads-as-cancer.html

廣告:惡之源頭 Advertising the Evil Side

壟斷(Monopoly),污染(Pollution)以及誤導(Misleading),是廣告的三大惡因。

維基百科的創辦人吉米·威爾士 曾經說「商業本無過,廣告亦非惡」,這句話放在 10 年以前似乎還能成立。但是放在今天,我們的身邊已經有足夠多廣告作惡的例子,讓我們對這後半句產生懷疑了。是什麼讓 Facebook 們頂著 GPDR 收集著我的數據?是廣告。是什麼讓無關內容充斥著我的 Timeline,分散我的 Attention?是廣告。是什麼讓我們的 Future President 只能去平行世界裡當總統?是廣告,還是廣告。

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