您可以精確地與僵尸戰(zhàn)斗嗎？饑餓的魚能從動態(tài)編程中受益嗎？這些問題激發(fā)了為Facebook年度Hacker Cup設計問題的開發(fā)人員的靈感。 

今天是該競賽的決賽，已經(jīng)是第九年。編程競賽向公眾開放，今年吸引了6,000多名參與者。最終的25名參賽者，經(jīng)過了四輪最高分的預選賽，將嘗試解決從太平洋標準時間上午9:30 –美國東部標準時間12:30 pm -5：30pm開始的勝利之路。您可以在此處觀看直播。 

由于Stack Overflow的全部目的是詢問和回答編程問題，因此我們認為與一些為Hacker Cup編寫問題并學習如何解決問題的開發(fā)人員坐下來很有趣。盡管關于SO的大多數(shù)問題本質上都比較實用，但是Stack Exchange擁有自己的Code Golfers社區(qū)，他們樂于在業(yè)余時間為編程問題設計最有效的解決方案。 

那么，是什么導致巨大的Hacker Cup問題呢？我們與Hacker Cup貢獻者Jacob Plachta和Wesley May進行了聊天，他們撰寫了過去幾年中使用的大多數(shù)問題。兩人在多倫多大學學習期間相識，并自2014年以來一直在合作舉辦Hacker Cup。 

除了分享有關他們?nèi)绾谓鉀Q這些問題的過程的一些見解之外，普拉塔和梅還分享了一個針對2018賽季設計的問題，但最終并未包含在比賽中。您可以在此處找到它，我們期待看到我們的社區(qū)對此難題有所幫助。 

取得適當?shù)钠胶?/strong>

May和Plachta說，設計一個出色的Hacker Cup問題集的挑戰(zhàn)在于管理問題的難度，多樣性和獨創(chuàng)性。每一輪的目標是縮小下一輪的范圍，并確保每個人都擁有愉快的教育經(jīng)歷。

“在最后一輪，理想的情況是每個問題都得到解決，每個人至少解決一個問題，但沒人能解決每個問題，” May說。“在較早的幾輪中，我們希望總的困難是使每個解決所有問題的人都進步，但是您并不需要解決所有問題?！?/span>

問題必須具有多樣性，同時又要保持在比賽范圍之內(nèi)。每個問題的解決方案應該可以從第一原理或眾所周知算法的組合中獲得。任何人都不應為一個問題所困擾，因為它依賴于一些非常專業(yè)的知識。也就是說，沒有人希望在每次比賽中都解決相同的問題，因此問題也必須是原創(chuàng)的。

普拉奇塔（Platchta）認為存在兩種產(chǎn)生問題的一般方法。首先涉及從解決方案的某些方面入手，然后進行反向工作以解決問題?！斑@種方法可以奏效，但也很容易導致出現(xiàn)問題，最終感覺更標準，更原始?！?Plachta說。第二種方法（如今Plachta經(jīng)常使用）是從一個解決方案未知的問題開始的。

普拉希塔說：“我基本上花了大量時間在思考可能會變成問題的粗略想法上?！?“任何給定的想法都不太可能實現(xiàn)，絕對不到10％的機會。畢竟它可能會變得毫無趣味，或者在嘗試解決由此產(chǎn)生的問題時，結果會變得太容易，太麻煩或無法解決。不幸的是，您通常在經(jīng)過很多思考后才知道。但是，在嘗試了足夠多的不同想法或變化之后，我會遇到一個實際上變成一個大問題的想法。總是很令人興奮！”

從日常世界中尋找靈感

有時候，現(xiàn)實世界中的經(jīng)驗會帶來問題。May和Plachta遇到了讓他們思考的問題，然后慢慢找到了一種將這些想法變成編碼問題的方法?！拔?guī)椭帉懥?015賽季第三輪名為Broken Bits的問題，” May說?！斑@是基于我對數(shù)字時鐘損壞的實際觀察得出的，這意味著某些LED分段只是無法工作。我記得凝視了一段時間，然后思考，好了，您可以看一下這個時鐘，也許由于某些部分丟失而無法說出現(xiàn)在的時間，這使它變得模棱兩可。但是，如果您觀看此時鐘足夠長的時間，那么最終您可能會有足夠的信息來弄清楚它實際上應該是幾點鐘了。”

問題想法也可能來自游戲。May回憶說：“我和朋友一起玩了很多Pathfinder Adventure Card Game?！?“您必須為攻擊選擇不同的項目，這意味著使用不同的骰子來確定您將遭受的損失。也許我的一次攻擊的平均傷害較高，但我可能更喜歡另一次攻擊的平均傷害較低，但方差較高。這變成了一個名為“與僵尸戰(zhàn)斗”的問題，該問題出現(xiàn)在2017年的資格賽中?！?/span>

“有時候，每年我們都會在多個問題中使用相同的字符和主題。這些問題在主題上可能感覺相似，即使它們可能非常不同，也應該相似?！?May說。“去年，我們遇到了一個苦苦掙扎的計算機科學專業(yè)學生的一系列問題，這些學生永遠無法完全正確地編寫代碼?！?一旦想到了主題，Plachta和May就會嘗試進一步開發(fā)該主題，以查看可能還會出現(xiàn)其他問題。

這是計算機編程的挑戰(zhàn)，但有時靈感來自大自然，例如觀看象牙魚將蛤c砸向行星地球上的巖石?！斑@個概念看起來很酷，所以我考慮了如何擴展它。也許可能會有多個硬度不同的蛤different和巖石，因此蛤need需要砸在更堅硬的巖石上?！?“我考慮了很多變化，包括放置這些蛤and和巖石的背景以及目標是什么。事實證明，將它們排列在數(shù)字線上并要求最小旅行距離以打開所有蛤the的簡單概念解決了正確的問題，從而導致了2019年第二輪海鮮的最后一個問題。”

“鑒于象牙魚可能采取的可能路徑呈指數(shù)級增長，這是一開始似乎不可行的問題，這是理想的。只是在進一步考慮之后，您才能將可能的最佳路徑縮小到一組更易于管理的模式。從那里開始，它可以歸結為使用動態(tài)編程可解決的問題，這是通過遞歸解決較小的子問題來有效解決優(yōu)化問題的通用方法，這在比賽中通常很有用。盡管在這種情況下，需要一種更高級的技術（通常被稱為“凸包技巧”）來獲得足夠的有效時間復雜性?！?/span>

無論靈感如何，他們都通過將其包裝在敘述中來使問題變得有趣?！肮适碌淖詈笫且粚忧迤帷＞拖衲斎徊槐負碛兴?，但它卻有趣得多?！?在兩個披薩送貨員之間的競爭中，提出了在網(wǎng)格上放置塊的問題。關于在樹上的節(jié)點周圍移動的問題變成了一個痣家庭的婚姻沖突的故事。 

不斷發(fā)展的復雜性

如果您看一下幾十年前奧運會體操運動員的獲勝常規(guī)，那么與當今頂級表演的復雜性相比，它們似乎簡直太簡單了。自2011年以來一直在舉辦的Hacker Cup期間完成的這類問題也是如此，這種問題來自更早的比賽，如ICPC（自1970年代以來一直活躍）。自從5月開始以來，問題就變得越來越難?！叭绻一叵肫?008年ICPC的世界總決賽問題，現(xiàn)在我可以解決很多這樣的問題。而如果我單單從今天開始看一個問題，我大概最多可以解決11個問題中的三個?！?/span>

1970年代和80年代的最后一輪比賽今天被認為是中等難度?！耙郧暗膯栴}非常明確地說明了您必須采取的措施，而大多數(shù)挑戰(zhàn)在于實施而不是實際解決問題。如今，這類問題通常被認為是瑣碎而乏味的?！?“重點已經(jīng)轉向尋找核心算法和數(shù)據(jù)結構的有趣應用。因此，例如，找出最適合這種情況的工具-二進制搜索，深度優(yōu)先搜索，分段樹，動態(tài)編程等，然后使它們發(fā)揮作用。”

由于許多參賽者在整個高中和大學時代就一直在解決這類問題，并且配備了預先編寫的算法，因此“黑客杯”的問題不僅僅在于確定正確的工具?！叭缃?，我們試圖解決問題的方式是有趣的轉變，”梅說。“也許您會得到一些未在圖表上明確玩過的游戲，但是如果您以正確的方式考慮它，您會發(fā)現(xiàn)它實際上具有抽象的圖表結構。一個棘手的問題應該很難解決，因為需要一系列有趣的見識才能提出可行的解決方案，而不是因為實際的編碼工作既冗長又挑剔?！?/span>

隨著參賽者能力的提高，有時候是參賽者使問題作者感到驚訝?！皡①愓咛峤坏膬?nèi)容有時會比我們自己想出的更優(yōu)雅，” Plachta解釋說?！耙粋€很好的例子是在今年的第三輪中存在一個名為“整數(shù)即服務”的問題。我打算讓解決方案涉及素數(shù)分解并獨立處理不同的素數(shù)，這是處理GCD和LCM的一種非常典型的方法，這是此問題所必需的。而且，這就是多少人去做。但是，一些頂級選手想出了一種更簡單的方法，即利用GCD和LCM相互交互并更直接地使用它們。即使在比賽的短時間內(nèi)看到這些思考過程，也真的很酷，令人印象深刻！”

雖然競爭性程序設計的更廣闊世界已經(jīng)發(fā)展，但黑客杯也是如此。在最初的幾年中，每輪比賽都有三個問題，包括決賽。現(xiàn)在，每個在線回合都有四個問題，最后一輪比賽從三個問題的三個小時變?yōu)榱鶄€問題的四個小時?！安粌H增加了問題，我們還努力保持質量和原創(chuàng)性。我們希望每一年都比上一年更好?！?May說。隨著時間的流逝，總體理念的某些方面也發(fā)生了變化。“過去，對于每個問題給出的示例測試用例，我們都是卑鄙的。由于您只有一次機會可以在Hacker Cup中提交每個問題，因此我們?nèi)缃褡兊酶涌犊?。如果您對樣本?shù)據(jù)正確，則可能是正確的解決方案。我們正在嘗試測試您解決有趣問題的能力，

駭客，針對駭客，向所有人開放

May和Plachta都是前ICPC世界總決賽的競爭對手。他們最初是在2011年在多倫多大學ICPC團隊的選拔賽上見面的，最終他們一起參加了世界總決賽。第二年，由于世界總決賽有兩次出場限制，May不能再參加ICPC比賽，所以他接任了U.T的教練職務，而Plachta和他的團隊又進行了一次世界總決賽。從那時起，他們在各種競賽中都遇到了書面問題，包括高中水平的競賽，例如加拿大計算機奧林匹克競賽和沃本挑戰(zhàn)賽。

更值得注意的是，雖然May在學習CS時成為一名競爭性程序員，但Plachta卻在學習音樂?！拔业牡谝粋€世界總決賽團隊有一名統(tǒng)計學專業(yè)的學生，他負責解決大多數(shù)問題，而我們其他兩個人則負責所有編碼工作，”梅說?！澳鸁o需參加傳統(tǒng)的“技術”課程即可享受算法競賽并獲得成功。我的兩個最好的隊友都沒有專注于CS或工程?！?/span>

多年來，黑客杯的參與者一直在Facebook工作，其中許多人參加時仍在上大學或高中。梅說：“盡管競爭性編程僅測試非常具體的技能子集，但參加者顯示出一定程度的編碼熱情?！?“我在西蒙·弗雷澤大學（Simon Fraser University）讀本科，這在美國并不是特別著名。我競爭激烈的編程活動首先使我成為Facebook的關注?！?/span>

早些年，F(xiàn)acebook始終在其門洛帕克總部舉辦比賽的最后階段。為了擴大比賽的范圍和可及性，F(xiàn)acebook開始從全球范圍內(nèi)選擇新的地點來舉辦現(xiàn)場活動。今年，黑客杯將在都柏林舉行，您可以在美國東部時間上午8:30開始觀看決賽的現(xiàn)場直播。如果您想了解更多有關Plachta的信息，請在此處查看個人資料。最后但并非最不重要的一點是，如果您今天早晨感到有些困惑，請不要忘記查看Hacker Cup團隊在Code Golf上分享的問題。