Description

Top-k Sum of Subarray
PA5 簡介
• 問題定義 : Top-k Sum of Subarray
• 輸入/輸出格式
• 作業繳交檔案
• 評分方式
問題定義
• Sum of Subarray
• 將一個Array中相鄰位置的數加起來的值，或其中某一個數的值
Sum=0
Sum=3
問題定義
• Top-1 Sum of Subarray
• Sum of Subarray 的最大值 Sum=4

問題定義
• Top-k Sum of Subarray
• Sum of Subarray前k大的值
Top-1 Sum of Subarray Top-2 Sum of Subarray Top-3 Sum of Subarray

3 1 -1 Sum=4 3 1 -1 Sum=4 3 1 -1

Sum=4

3 1 -1

Sum=3 Sum=3
Sum=3
sum一樣, 但位置不一樣
注意事項
• 請使用 python3.7 的環境
• 只能修改 main.py 中 TODO 範圍內的程式碼
• 可以使用 python standard library: https://docs.python.org/3/library/
，但不可使用其他 library（例如numpy）
• 可以使用任何資料結構及演算法，但不可使用 multithread programming
• 不可使用 Cython

輸入/輸出格式
輸入(json) Output (json)
{“array”: [1, -2, -3, -8, 7, 1, 5, [33, 28, 26]
10, 10, -5], “topk”: 3}
• “array”: 型態為 integer array, 長度n, 數值範圍為 [–n , n] • 型態為 integer array，數值需由大到小排列
• “topk”: 型態為 integer, 數值範圍為 [1, n].
作業繳交檔案
• 1.程式碼 main.py
• 2.報告，限pdf格式，取名為report.pdf，頁數不可超過兩頁
• 報告內容需簡述你所提出的解法，需註明使用哪些資料結構及演算法，並分析解決此問題所需的時間複雜度。時間複雜度的大小會納入評分標準。
* 提示：
• 1. 暴力解：大於或等於 O(n^3)
• 2. Dynamic Programming + Heap : 小於 O(n^3)
• 3. 有其他更快的解法？請同學自由發揮
作業繳交檔案
• 截止時間 6/28, at 4:00 am
• 請將 main.py 和 report.pdf 放到取名為你的學號的目錄,並壓縮上傳

評分標準
• 程式結果正確性 : 50分
• 執行時間: 20分
• 報告 : 40分
評分標準
• 測試資料
• 輸入: input_1.json ~ input_10.json
• 答案: golden_1.json ~ golden_10.json
• Input_1.json ~ input_6.json 用於評分程式正確性，會提供給同學。
• Input_7.json ~ input_10.json 用於評分程式執行時間，不提供給同學。
評分標準
• 評分正確性的指令碼: evaluation.sh
• 執行方式
• bash evaluation.sh
main.py 的輸出結果正確 main.py 的輸出結果不正確

評分標準
1. 正確性: 50分
input_1.json size=3 input_2.json size=10 input_3.json size=100 input_4.json size=300 input_5.json size=1000 input_6.json size=3000
分數 7.5分 7.5分 7.5分 7.5分 10分 10分
2. 執行速度: 20分
input_7.json size=3000 input_8.json size=3000 input_9.json size=3000 input_10.json size=3000
分數 5分 5分 5分 5分
3. 報告: 40分
評分標準–執行速度
• 程式執行結果正確後，才能獲得執行速度的分數。
• 你的程式會和其他正確結果同學的程式做比較，依照每個測試資料的的執行時間長短，分別排名給分，每個測試資料滿分為5分。
• 前 20% : 5 分
• 前 21%~40% : 4 分
• 前 41%~60% : 3 分
• 前 61%~80% : 2 分
• 前 81%~100% : 1 分
評分標準–報告
• 有交報告，但所提出的解法錯誤： 5分～15分
• 所提出的解法正確，時間複雜度大於或等於O(n^3)（暴力解）
• 沒有時間複雜度的推導過程：15分
• 有時間複雜度的推導過程，但結果錯誤：17分
• 有時間複雜度的推導過程，且結果正確：20分
• 所提出的解法正確，時間複雜度小於 O(n^3)
• 沒有時間複雜度的推導過程：15分
• 有時間複雜度的推導過程，但結果錯誤：30分
• 有時間複雜度的推導過程，且結果正確：40分
Any Questions?
• 張富傑(Mark)
• email : d09942015@ntu.edu.tw
• phone : 0989922753