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

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

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

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

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

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

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

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

Facebook的軟件工程師，活動組織者之一戴維·阿爾維斯(David Alves)表示：“之所以來到這里，是因為他們熱衷于參與這些事情。”

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

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

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

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

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

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

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

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

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

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

樣本問題

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

聚會時間

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

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

您要從G中選擇一組來賓。這組來賓應(yīng)包括您的所有朋友，并且由來賓形成的G的子圖必須已連接。您相信這將確保您的所有朋友都能享受您的聚會，因為他們中的任何兩個都會有話要說...

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

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

輸入輸入

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

輸出

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