2016-2022 All Rights Reserved.平安財(cái)經(jīng)網(wǎng).復(fù)制必究 聯(lián)系QQ280 715 8082 備案號:閩ICP備19027007號-6
本站除標(biāo)明“本站原創(chuàng)”外所有信息均轉(zhuǎn)載自互聯(lián)網(wǎng) 版權(quán)歸原作者所有。
過去一周充滿了重大新聞,這在一定程度上要?dú)w功于在奧斯丁舉行的South By Southwest Interactive會議。朱莉·奧德爾在那里采訪推動者和振動器,所以執(zhí)行編輯迪倫Tweney填寫為VBWeekly的主機(jī)。一月份,來自世界各地的6,000多名充滿希望的人參加了Facebook的編程挑戰(zhàn)賽 “ 黑客杯”。三個月后,今天只有25位決賽入圍者在Facebook新的Menlo Park校園進(jìn)行了為時三小時的爭奪戰(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)然,與眾多世界一流的程序員抗衡確實(shí)令人振奮。
Facebook的軟件工程師,活動組織者之一戴維·阿爾維斯(David Alves)表示:“之所以來到這里,是因?yàn)樗麄儫嶂杂趨⑴c這些事情。”
除了一個人以外,其他人都來自海外。進(jìn)入決賽的國家/地區(qū)包括俄羅斯,德國,烏克蘭,波蘭,中國,韓國,臺灣,日本和美國。經(jīng)過連續(xù)三輪更具挑戰(zhàn)性的資格賽后,這25名決賽選手在這里花費(fèi)了Facebook幾天的時間參觀,打保齡球和三個小時的編碼。
Facebook的Hacker Cup并不是唯一的此類編碼競賽。這里的許多編碼人員還參加TopCoder競賽,Google Code Jam競賽以及本國的編碼競賽。這就是Alves推測某些地區(qū)(例如東歐和亞洲)產(chǎn)生了更成功的代碼競賽者的原因之一:他們更習(xí)慣于此類競賽。另外,他補(bǔ)充說,他們的國家擁有出色的科學(xué)和數(shù)學(xué)教育。
駭客杯的工作方式是這樣的:每個編碼人員都會遇到三個困難的編程問題,需要三個小時才能解決。在第一輪中,問題很容易:例如,找出可用于給定大小和指定文本的符號的最大大小字體。當(dāng)挑戰(zhàn)者進(jìn)入最后一輪比賽時,問題變得棘手。(有關(guān)去年競賽的示例問題,請參見下文。)阿爾維斯(Alves)預(yù)計(jì)只有一個或兩個參賽者才能完成這三個問題,而只有大約一半的人甚至可以完成一個問題。這就是去年Facebook第一臺Hacker的結(jié)果杯賽。
Alves說,盡管70%的人選擇C ++,但參賽者可以使用他們想要的任何編程語言和開發(fā)環(huán)境。(少數(shù)使用Java,一兩個使用C#。)完成程序后,參賽者可以對其進(jìn)行測試,然后將其提交給裁判。該程序有六分鐘的運(yùn)行時間,如果產(chǎn)生正確的結(jié)果,則通過。
評委根據(jù)程序產(chǎn)生的結(jié)果的準(zhǔn)確性來確定獲勝者,然后由編碼人員提出解決方案的速度決定。
這是一個挑戰(zhàn),它測試了所有參賽者的計(jì)算機(jī)科學(xué)技能,但是還需要一定水平的直覺和開箱即用的思維。
阿爾維斯說:“通常,解決問題的直接方法遠(yuǎn)遠(yuǎn)不夠快。”
從物理上講,“黑客杯”沒什么好看的:一群年輕人緊緊盯著他們超大的顯示器,連續(xù)三個小時。房間是如此安靜,以至于我相機(jī)的快門的咔嗒聲是最大的聲音。一個小時后,墻上顯示的駭客杯網(wǎng)頁顯示三名選手分別完成了一個問題。該消息的沉默掩蓋了潛在的強(qiáng)度。
盡管參賽者確實(shí)可以訪問Internet,并且可以在Wikipedia上進(jìn)行查找,但他們不應(yīng)該與外部的任何人合作或交流。但是Alves不太擔(dān)心有人外包他們的問題集。
“他們將外包給誰?”阿爾維斯說。“這個房間里的人最有資格解決這些問題。”
樣本問題
想知道參加駭客杯的感覺如何?從去年的比賽來看這個問題。請記住,這只是三個問題之一,您只需三個小時即可創(chuàng)建一個解決所有三個問題的程序。
聚會時間
您正在為朋友舉辦聚會,但是由于您的朋友可能并不互相認(rèn)識,因此您擔(dān)心其中一些人可能不會喜歡您的聚會。因此,為避免這種情況,您決定同時邀請朋友中的一些朋友。但是,您應(yīng)該邀請誰參加一次盛大的聚會呢?
幸運(yùn)的是,您擁有有關(guān)您的朋友及其朋友的所有友誼的數(shù)據(jù)。在圖論術(shù)語中,您有社交圖的子集G,其頂點(diǎn)與您的朋友和他們的朋友(不包括您自己)相對應(yīng),并且該圖中的邊表示相互友誼。此外,您已經(jīng)成功地獲得了對G中每個人在聚會期間將消耗多少食物的準(zhǔn)確估計(jì)。
您要從G中選擇一組來賓。這組來賓應(yīng)包括您的所有朋友,并且由來賓形成的G的子圖必須已連接。您相信這將確保您的所有朋友都能享受您的聚會,因?yàn)樗麄冎械娜魏蝺蓚€都會有話要說...
為了省錢,您想挑選一組客人,以使所需的食物總量盡可能少。如果有多種方法可以這樣做,那么您最好選擇一種來賓最少的方法。
社交圖的子集G中的人/頂點(diǎn)的編號從0到N –1。為方便起見,您的朋友編號從0到F – 1,其中F是您要邀請的朋友的數(shù)量。您也可以假設(shè)已連接G。再次注意,您本人并不代表G。
輸入輸入
的第一行包含一個數(shù)字T,即測試用例的數(shù)量。每個測試用例都從包含三個整數(shù)的行開始,即N,即G,F(xiàn)中的節(jié)點(diǎn)數(shù),朋友數(shù),以及M,即G中的邊沿?cái)?shù)三個整數(shù)。隨后是M行,每行均包含兩個整數(shù)。這些行的第i行將包含兩個不同的整數(shù)u和v,這表示人u與人v之間的相互友誼。此后是包含N個以空格分隔的整數(shù)的單行,第i行代表人i所食用的食物量。
輸出
輸出T線,每個測試用例的答案單獨(dú)在一條線上。每行應(yīng)包含兩個數(shù)字,第一個是滿足給定標(biāo)準(zhǔn)的聚會上所消耗的最小食物總量,第二個是您可以在該聚會上擁有的最小人數(shù)。
2016-2022 All Rights Reserved.平安財(cái)經(jīng)網(wǎng).復(fù)制必究 聯(lián)系QQ280 715 8082 備案號:閩ICP備19027007號-6
本站除標(biāo)明“本站原創(chuàng)”外所有信息均轉(zhuǎn)載自互聯(lián)網(wǎng) 版權(quán)歸原作者所有。