Facebook的Hacker Cup吸引了全球速度編程精英

過去一周充滿了重大新聞，這在一定程度上要?dú)w功于在奧斯丁舉行的South By Southwest Interactive會(huì)議。朱莉·奧德爾在那里采訪推動(dòng)者和振動(dòng)器，所以執(zhí)行編輯迪倫Tweney填寫為VBWeekly的主機(jī)。一月份，來自世界各地的6,000多名充滿希望的人參加了Facebook的編程挑戰(zhàn)賽 “ 黑客杯”。三個(gè)月后，今天只有25位決賽入圍者在Facebook新的Menlo Park校園進(jìn)行了為時(shí)三小時(shí)的爭(zhēng)奪戰(zhàn)。

優(yōu)勝者的名字(所有25名決賽入圍者都是男性)刻在50磅的獎(jiǎng)杯上，獎(jiǎng)杯是帶有像素化外觀的二維黃銅拳頭，作品“ HACK”被燙平，放在一個(gè)立方體的頂部。具體，

更新：經(jīng)過三個(gè)小時(shí)的比賽，F(xiàn)acebook宣布了2012年黑客杯的獲獎(jiǎng)?wù)撸?/p>

第一名：俄羅斯的羅曼·安德列夫(Roman Andreev)在1小時(shí)4分鐘內(nèi)正確完成了一個(gè)問題

第二名：來自美國(guó)的Tomek Czajka，在1小時(shí)5分鐘內(nèi)正確完成了一個(gè)問題

第三名：來自中國(guó)的天成樓，在1小時(shí)44分鐘內(nèi)正確完成了一個(gè)問題

一等獎(jiǎng)獲得者將獲得5,000美元的獎(jiǎng)金，但大部分獎(jiǎng)勵(lì)將是被公開任命為世界頂級(jí)編碼員之一的榮耀。另外，當(dāng)然，與眾多世界一流的程序員抗衡確實(shí)令人振奮。

Facebook的軟件工程師，活動(dòng)組織者之一戴維·阿爾維斯(David Alves)表示：“之所以來到這里，是因?yàn)樗麄儫嶂杂趨⑴c這些事情。”

除了一個(gè)人以外，其他人都來自海外。進(jìn)入決賽的國(guó)家/地區(qū)包括俄羅斯，德國(guó)，烏克蘭，波蘭，中國(guó)，韓國(guó)，臺(tái)灣，日本和美國(guó)。經(jīng)過連續(xù)三輪更具挑戰(zhàn)性的資格賽后，這25名決賽選手在這里花費(fèi)了Facebook幾天的時(shí)間參觀，打保齡球和三個(gè)小時(shí)的編碼。

Facebook的Hacker Cup并不是唯一的此類編碼競(jìng)賽。這里的許多編碼人員還參加TopCoder競(jìng)賽，Google Code Jam競(jìng)賽以及本國(guó)的編碼競(jìng)賽。這就是Alves推測(cè)某些地區(qū)(例如東歐和亞洲)產(chǎn)生了更成功的代碼競(jìng)賽者的原因之一：他們更習(xí)慣于此類競(jìng)賽。另外，他補(bǔ)充說，他們的國(guó)家擁有出色的科學(xué)和數(shù)學(xué)教育。

駭客杯的工作方式是這樣的：每個(gè)編碼人員都會(huì)遇到三個(gè)困難的編程問題，需要三個(gè)小時(shí)才能解決。在第一輪中，問題很容易：例如，找出可用于給定大小和指定文本的符號(hào)的最大大小字體。當(dāng)挑戰(zhàn)者進(jìn)入最后一輪比賽時(shí)，問題變得棘手。(有關(guān)去年競(jìng)賽的示例問題，請(qǐng)參見下文。)阿爾維斯(Alves)預(yù)計(jì)只有一個(gè)或兩個(gè)參賽者才能完成這三個(gè)問題，而只有大約一半的人甚至可以完成一個(gè)問題。這就是去年Facebook第一臺(tái)Hacker的結(jié)果杯賽。

Alves說，盡管70%的人選擇C ++，但參賽者可以使用他們想要的任何編程語言和開發(fā)環(huán)境。(少數(shù)使用Java，一兩個(gè)使用C#。)完成程序后，參賽者可以對(duì)其進(jìn)行測(cè)試，然后將其提交給裁判。該程序有六分鐘的運(yùn)行時(shí)間，如果產(chǎn)生正確的結(jié)果，則通過。

評(píng)委根據(jù)程序產(chǎn)生的結(jié)果的準(zhǔn)確性來確定獲勝者，然后由編碼人員提出解決方案的速度決定。

這是一個(gè)挑戰(zhàn)，它測(cè)試了所有參賽者的計(jì)算機(jī)科學(xué)技能，但是還需要一定水平的直覺和開箱即用的思維。

阿爾維斯說：“通常，解決問題的直接方法遠(yuǎn)遠(yuǎn)不夠快。”

從物理上講，“黑客杯”沒什么好看的：一群年輕人緊緊盯著他們超大的顯示器，連續(xù)三個(gè)小時(shí)。房間是如此安靜，以至于我相機(jī)的快門的咔嗒聲是最大的聲音。一個(gè)小時(shí)后，墻上顯示的駭客杯網(wǎng)頁(yè)顯示三名選手分別完成了一個(gè)問題。該消息的沉默掩蓋了潛在的強(qiáng)度。

盡管參賽者確實(shí)可以訪問Internet，并且可以在Wikipedia上進(jìn)行查找，但他們不應(yīng)該與外部的任何人合作或交流。但是Alves不太擔(dān)心有人外包他們的問題集。

“他們將外包給誰?”阿爾維斯說。“這個(gè)房間里的人最有資格解決這些問題。”

樣本問題

想知道參加駭客杯的感覺如何?從去年的比賽來看這個(gè)問題。請(qǐng)記住，這只是三個(gè)問題之一，您只需三個(gè)小時(shí)即可創(chuàng)建一個(gè)解決所有三個(gè)問題的程序。

聚會(huì)時(shí)間

您正在為朋友舉辦聚會(huì)，但是由于您的朋友可能并不互相認(rèn)識(shí)，因此您擔(dān)心其中一些人可能不會(huì)喜歡您的聚會(huì)。因此，為避免這種情況，您決定同時(shí)邀請(qǐng)朋友中的一些朋友。但是，您應(yīng)該邀請(qǐng)誰參加一次盛大的聚會(huì)呢?

幸運(yùn)的是，您擁有有關(guān)您的朋友及其朋友的所有友誼的數(shù)據(jù)。在圖論術(shù)語中，您有社交圖的子集G，其頂點(diǎn)與您的朋友和他們的朋友(不包括您自己)相對(duì)應(yīng)，并且該圖中的邊表示相互友誼。此外，您已經(jīng)成功地獲得了對(duì)G中每個(gè)人在聚會(huì)期間將消耗多少食物的準(zhǔn)確估計(jì)。

您要從G中選擇一組來賓。這組來賓應(yīng)包括您的所有朋友，并且由來賓形成的G的子圖必須已連接。您相信這將確保您的所有朋友都能享受您的聚會(huì)，因?yàn)樗麄冎械娜魏蝺蓚€(gè)都會(huì)有話要說...

為了省錢，您想挑選一組客人，以使所需的食物總量盡可能少。如果有多種方法可以這樣做，那么您最好選擇一種來賓最少的方法。

社交圖的子集G中的人/頂點(diǎn)的編號(hào)從0到N –1。為方便起見，您的朋友編號(hào)從0到F – 1，其中F是您要邀請(qǐng)的朋友的數(shù)量。您也可以假設(shè)已連接G。再次注意，您本人并不代表G。

輸入輸入

的第一行包含一個(gè)數(shù)字T，即測(cè)試用例的數(shù)量。每個(gè)測(cè)試用例都從包含三個(gè)整數(shù)的行開始，即N，即G，F(xiàn)中的節(jié)點(diǎn)數(shù)，朋友數(shù)，以及M，即G中的邊沿?cái)?shù)三個(gè)整數(shù)。隨后是M行，每行均包含兩個(gè)整數(shù)。這些行的第i行將包含兩個(gè)不同的整數(shù)u和v，這表示人u與人v之間的相互友誼。此后是包含N個(gè)以空格分隔的整數(shù)的單行，第i行代表人i所食用的食物量。

輸出

輸出T線，每個(gè)測(cè)試用例的答案單獨(dú)在一條線上。每行應(yīng)包含兩個(gè)數(shù)字，第一個(gè)是滿足給定標(biāo)準(zhǔn)的聚會(huì)上所消耗的最小食物總量，第二個(gè)是您可以在該聚會(huì)上擁有的最小人數(shù)。