Marathon24比賽quals：脫氧核糖核酸-TLE

我正在重新嘗試這problem statement,now that the contest is all over（所以這不是作弊或任何事情，只是想學習，因爲答案沒有公佈，只有給定的測試用例輸入正確的輸出文件）。Marathon24比賽quals：脫氧核糖核酸-TLE

有10個給定的測試用例輸入，爲此要提交相關的輸出文件。我最初的提交是一個初始嵌套循環（開始，結束）對的實現，回答了查詢：從（從0開始）索引start，結束於end（含）的子字符串的波動率度量是什麼。

顯然，對於最大問題限制10 ，O（N 2 ）是不可行的，所以我只得到儘可能5/10測試用例正確的（第一 - 和更簡單的 - 5，的課程）。因此，我寫這裏是爲了尋求關於如何改進我的算法的人羣智能，也就是說我懷疑嵌套for循環（start，end）是優化的主要瓶頸（當然！）。到目前爲止，我已經試圖將其作爲動態編程（DP）在字符串/子串問題上進行闡述，但在獲得狀態表示和轉換位方面沒有取得任何成功，從而可以實現DP 。

爲了方便參考，爲了表明這不是功課，並且我誠實地嘗試過了，我的原始提交文件是here。

任何幫助非常感謝，甚至鏈接到類似的問題，我可以谷歌教程博客文章/樣本解決方案/賽後編輯分析。

來源

2013-10-22 evandrix

你試過分而治之？如果我正確地理解了這個問題，給定一個長度爲n的DNA鏈S，我們將S分成兩部分，S_left和S_right，其中S_left由S [i]組成，其中0 < = i < n/2， S_right由S [j]組成，其中（n/2）+1 < = j < n。最易變的片段要麼完全出現在S_left內，完全在S_right內，要麼穿過S_left和S_right的邊界。

要找到S_left和S_right的最易變的片段，我們只需使用遞歸。棘手的一點是要找到穿過S_left和S_right邊界的碎片的波動率度量。這裏有一個正整數分數的數學性質：給出四個正（非零）整數a，b，c和d，（a + c）/（b + d）永遠不會大於兩個（a/b）和（c/d）。這裏一個和b在S_LEFT嘌呤和嘧啶起始於邊界的累積計數，而Ç和d在S_right嘌呤和嘧啶起始於邊界的累積計數。這個數學性質意味着我們不需要檢查超過a = 0或c = 0的交叉片段的波動性度量，因爲它保證小於S_left或S_right的最大波動率。這種搜索的時間複雜度可以在O（n）中針對交叉片段完成，並且O（n lg n）針對整個算法。

希望這可以工作，因爲我沒有編碼算法。也許它有這個問題的O（n）時間DP算法，但這是我現在所擁有的。

來源

2013-10-24 15:43:49

謝謝，下次有機會我會盡快試用。我會附上其他地方從我的類似帖子收到的意見，例如。 Codeforces，Codechef，Topcoder等以供參考和信息 – evandrix

＃1：測試用例數據是特殊的，每種情況下'T'或'C'的數量很小並且可以是強制性的，除了包含1000000'T'或'C'的一種情況字符沒有明顯可以用手解決的'A'或'G'字符。 – evandrix

＃2：1.如果我們只想最大化比例，而不是長度，我們可以考慮只有一個壞字母的子字符串。 2.如果長度也考慮到餘數，我們應該另外檢查是否存在形式爲0000110000（k個零，2個和k個零）的子串，其中k是最佳比率。 P.S.開始時，T和C的比率與A和G的比率接近1. 後來，爲了使輸入更好地壓縮，這個比率高度降低了。 – evandrix

Marathon24比賽quals：脫氧核糖核酸-TLE

回答

相關問題