[綜合]無題 無名 ID:STzqOWhA 2022/07/31(日) 23:46:33.263 No.28543243
評分：-1, 年：-1, 月：-1, 週：-1, 日：-1, [+1 / -1] 最後更新：2022-08-02 07:18:45
徵求C++強者幫我 debug
窩要被退學惹 Q_Q
我怎麼跑 8000 的 case 都沒辦法到 120 秒內完成....
教會我的匯款 5000 給你 絕對不騙
窩不要被退學....
https://drive.google.com/file/d/1PKtGOApykBglo5KtuNow4QPHvZAvyW0_/view?usp=sharing
窩要被退學惹 Q_Q
我怎麼跑 8000 的 case 都沒辦法到 120 秒內完成....
教會我的匯款 5000 給你 絕對不騙
窩不要被退學....
https://drive.google.com/file/d/1PKtGOApykBglo5KtuNow4QPHvZAvyW0_/view?usp=sharing
無題 無名 ID:oyAH5uuI 2022/07/31(日) 23:48:40.813 No.28543275
幫你解完一定不會付錢
吃屎吧
吃屎吧
無題 無名 ID:3uZbZjZc 2022/07/31(日) 23:49:15.215 No.28543283
有毒
無題 無名 ID:NeUQrzRw 2022/07/31(日) 23:50:00.141 No.28543300
>>28543243
下次記得認真學。
下次記得認真學。
無題 無名 ID:U3G65uMw 2022/07/31(日) 23:50:56.728 No.28543312
不交作業 不去上課
退學剛好而已吧
退學剛好而已吧
>>28543243
K島可以直接貼程式碼 不想連你的雲端
K島可以直接貼程式碼 不想連你的雲端
無題 無名 ID:STzqOWhA 2022/07/31(日) 23:52:09.016 No.28543323
幹我都寫到 O(NW)了還是沒辦法120秒...
到底怎麼搞
到底怎麼搞
>>28543243
去找接案外包www
去找接案外包www
無題 無名 ID:STzqOWhA 2022/07/31(日) 23:55:05.070 No.28543361
無題 無名 ID:RSO2xOXA 2022/07/31(日) 23:58:27.812 No.28543412
題目是啥
無題 無名 ID:krzAxpGY 2022/08/01(一) 00:01:20.296 No.28543455
>>28543243
沒人在意 糞校廢物早點被退面對現實
沒人在意 糞校廢物早點被退面對現實
無題 無名 ID:mwkRy3WI 2022/08/01(一) 00:04:11.494 No.28543492
不是暑假了嗎 怎麼要寫作業？
題目是啥要輸出啥資料都不講就一擊脫離了喔
無題 無名 ID:CH9z7GM2 2022/08/01(一) 00:05:19.262 No.28543512
這什麼狗屎爛變數命名
無題 無名 ID:3RV58ACs 2022/08/01(一) 00:08:17.790 No.28543546
要島民幫忙你也先貼一本a漫表示誠意好嗎
無題 無名 ID:Vh5YlsBs 2022/08/01(一) 00:09:59.940 No.28543574
無題 無名 ID:2qAkcTaw 2022/08/01(一) 00:12:08.790 No.28543612
教你一招
直接辦休學來躲退學
直接辦休學來躲退學
>>28543579
你貼fb社團 很多人會幫
你貼fb社團 很多人會幫
無題 無名 ID:/ydDl7fA 2022/08/01(一) 00:18:39.607 No.28543698
你跟同學關係好的話先請教同學啊
無題 無名 ID:/ydDl7fA 2022/08/01(一) 00:20:20.566 No.28543715
>>28543624
FB一堆社團都只會虐菜而已 這種題目大部分都直接沉進海溝裡了
FB一堆社團都只會虐菜而已 這種題目大部分都直接沉進海溝裡了
無題 無名 ID:XD5V8L2s 2022/08/01(一) 00:23:25.834 No.28543746
所以你的code是有正常運作，但只是太慢?
>>28543756
太慢，答案是對的
gist 上的 case 是 8000，測試資料有到 80000
都可以跑，但是就是達不到時間需求
我覺得是我DP的設計可能有問題，或者是有什麼方法能夠 skip loops
我今天真的想破頭 幹...
有人要接案的話我馬上去註冊
5000+ 最好能早上給我 Q_Q
https://www.tasker.com.tw/
太慢，答案是對的
gist 上的 case 是 8000，測試資料有到 80000
都可以跑，但是就是達不到時間需求
我覺得是我DP的設計可能有問題，或者是有什麼方法能夠 skip loops
我今天真的想破頭 幹...
有人要接案的話我馬上去註冊
5000+ 最好能早上給我 Q_Q
https://www.tasker.com.tw/
無題 無名 ID:dMj0zCpM 2022/08/01(一) 00:36:29.278 No.28543906
5000塊真的你找不到同學接喔?
>>28543966
就錢太少沒人接ㄅ
就錢太少沒人接ㄅ
無題 無名 ID:11OkoWjg 2022/08/01(一) 00:46:02.774 No.28544003
改念台大國發所
無題 無名 ID:DD2mU/fU 2022/08/01(一) 00:47:00.069 No.28544019
幹你娘寫程式不用github 怎不去撞牆?
無題 無名 ID:y4dN/MM6 2022/08/01(一) 00:47:10.563 No.28544020
如果用這個呢?
https://cp.wiwiho.me/aliens/
https://cp.wiwiho.me/aliens/
>>28543818
你要不要先講一下你的解法
你要不要先講一下你的解法
從記憶體相關下手吧，給8000的檔案吃了18G
[init vector....]Mon Aug 1 00:57:12 2022
[aggregation...]Mon Aug 1 00:57:15 2022
[start DP...!]Mon Aug 1 00:57:15 2022
[[100/8000] Finished one iteration.]Mon Aug 1 00:57:15 2022
....
[[8000/8000] Finished one iteration.]Mon Aug 1 00:57:34 2022
[Generating result....]Mon Aug 1 00:57:34 2022
[init vector....]Mon Aug 1 00:57:12 2022
[aggregation...]Mon Aug 1 00:57:15 2022
[start DP...!]Mon Aug 1 00:57:15 2022
[[100/8000] Finished one iteration.]Mon Aug 1 00:57:15 2022
....
[[8000/8000] Finished one iteration.]Mon Aug 1 00:57:34 2022
[Generating result....]Mon Aug 1 00:57:34 2022
>>28544094
基本上就是用DP填表
https://hackmd.io/@BEepKzUiR-mU1eBtpHwBxA/BkTuVEEaq
>>28544061
謝謝島民
但是我還看不懂 我用力看
>>28543990
有人幫的話 我一定多給
>>28543966
真的不熟, 很哭
基本上就是用DP填表
https://hackmd.io/@BEepKzUiR-mU1eBtpHwBxA/BkTuVEEaq
>>28544061
謝謝島民
但是我還看不懂 我用力看
>>28543990
有人幫的話 我一定多給
>>28543966
真的不熟, 很哭
無題 無名 ID:mxLLAA4A 2022/08/01(一) 01:04:06.410 No.28544217
幹 島民幫一下他好嗎
很期待神人島島欸
很期待神人島島欸
無題 無名 ID:NeiI/pXY 2022/08/01(一) 01:07:29.599 No.28544256
>>28543243
我覺得你在這問
資訊工程研究所畢業 問 都問
https://forum.gamer.com.tw/C.php?page=1978&bsn=60076&snA=3146926
可能比較有人回
我覺得你在這問
資訊工程研究所畢業 問 都問
https://forum.gamer.com.tw/C.php?page=1978&bsn=60076&snA=3146926
可能比較有人回
>>28544159
大哥 你是有改過嗎? 還是機器超強
這執行時間好鬼
我是寫 python 的廢物 cpp 真的爛到不行
記憶體方面因為是到工作站上面跑所以我完全沒在管的
俗話說空間換時間 但是我根本換不到...
工作站上面 init 要 17s, 每 100 個 iteration 要 2s
8000 = 17 + 160 = 177 = 2分多
traseback 也要一些時間，加上 8000 算是 medium case
魔王是 80000...
我真的覺得是 DP 設計錯了，但是我現在腦細胞已經死得差不多 (48小時只睡5小時)
明天早上教授起床可能就會被當 = 退學
幹....... 我應該早點認清自己是垃圾，花錢消災的
大哥 你是有改過嗎? 還是機器超強
這執行時間好鬼
我是寫 python 的廢物 cpp 真的爛到不行
記憶體方面因為是到工作站上面跑所以我完全沒在管的
俗話說空間換時間 但是我根本換不到...
工作站上面 init 要 17s, 每 100 個 iteration 要 2s
8000 = 17 + 160 = 177 = 2分多
traseback 也要一些時間，加上 8000 算是 medium case
魔王是 80000...
我真的覺得是 DP 設計錯了，但是我現在腦細胞已經死得差不多 (48小時只睡5小時)
明天早上教授起床可能就會被當 = 退學
幹....... 我應該早點認清自己是垃圾，花錢消災的
無題 無名 ID:26Nk534U 2022/08/01(一) 01:15:05.482 No.28544328
無題 無名 ID:cFH6Esw2 2022/08/01(一) 01:19:37.939 No.28544386
要是
被退學後有甚麼打算
有想過嗎?
被退學後有甚麼打算
有想過嗎?
>>28544317
5600X配32G記憶體而已，你是用很爛的機器在跑嗎?
5600X配32G記憶體而已，你是用很爛的機器在跑嗎?
哪一間啊
啊大學會因為一科沒過就退學嗎？
還是你自己做死搞到被二一？
如果是研究所哪有啥退學
教授不滿意就一直沒法畢業啊
研究生就算再廢好歹有個奴隸幫忙做
教授哪會隨便把人踢掉？
啊大學會因為一科沒過就退學嗎？
還是你自己做死搞到被二一？
如果是研究所哪有啥退學
教授不滿意就一直沒法畢業啊
研究生就算再廢好歹有個奴隸幫忙做
教授哪會隨便把人踢掉？
無題 無名 ID:nHJlbjck 2022/08/01(一) 01:25:39.667 No.28544472
>>28544396
我是在學校的工作站上面跑的...
如果明天早上工作站突然升級就好了
>>28544412
必修 畢業年限
我是垃圾
努力過後 證明自己不配的垃圾
>>28544338
我覺得應該能從每個 cell 的 x 下手，而不是像我用每個座標去做
我物理上頭真的在痛 但是睡下去應該隔天就沒餘地了
我是在學校的工作站上面跑的...
如果明天早上工作站突然升級就好了
>>28544412
必修 畢業年限
我是垃圾
努力過後 證明自己不配的垃圾
>>28544338
我覺得應該能從每個 cell 的 x 下手，而不是像我用每個座標去做
我物理上頭真的在痛 但是睡下去應該隔天就沒餘地了
如果不存result然後把result的allocation也拿掉的話
DP的兩層迴圈還蠻快的(至少我跑起來是這樣
可能真的跟記憶體有關?
DP的兩層迴圈還蠻快的(至少我跑起來是這樣
可能真的跟記憶體有關?
無題 無名 ID:qD1d2s7g 2022/08/01(一) 01:35:07.374 No.28544572
你說的120秒是在什麼機器上啊?
有submit到伺服器上跑?
有submit到伺服器上跑?
無題 無名 ID:nHJlbjck 2022/08/01(一) 01:39:59.406 No.28544604
無題 無名 ID:nHJlbjck 2022/08/01(一) 01:42:57.821 No.28544634
>>28544597
以下是 makefile
我 cpp 很爛，這邊是直接用助教給的去改的，Google 過有 O2 flag 應該是有 optimization
有試過 O3，速度基本上相同
```
# CC and CFLAGS are varilables
CC = g++
CFLAGS = -c
AR = ar
ARFLAGS = rcv
# -c option ask g++ to compile the source files, but do not link.
# -g option is for debugging version
# -O2 option is for optimized version
DBGFLAGS = -g -D_DEBUG_ON_
OPTFLAGS = -O2
all : bin/mps
@echo -n ""
# optimized version
bin/mps : main_opt.o
$(CC) $(OPTFLAGS) main_opt.o -o bin/cl
main_opt.o : src/main.cpp
$(CC) $(CFLAGS) $< -Ilib -o $@
# clean all the .o and executable files
clean:
rm -rf *.o bin/*
```
以下是 makefile
我 cpp 很爛，這邊是直接用助教給的去改的，Google 過有 O2 flag 應該是有 optimization
有試過 O3，速度基本上相同
```
# CC and CFLAGS are varilables
CC = g++
CFLAGS = -c
AR = ar
ARFLAGS = rcv
# -c option ask g++ to compile the source files, but do not link.
# -g option is for debugging version
# -O2 option is for optimized version
DBGFLAGS = -g -D_DEBUG_ON_
OPTFLAGS = -O2
all : bin/mps
@echo -n ""
# optimized version
bin/mps : main_opt.o
$(CC) $(OPTFLAGS) main_opt.o -o bin/cl
main_opt.o : src/main.cpp
$(CC) $(CFLAGS) $< -Ilib -o $@
# clean all the .o and executable files
clean:
rm -rf *.o bin/*
```
是交到server上跑的話都沒有記憶體限制喔?
假設真的跟記憶體有關的話
我現在想的到的是把result改成map，
用(j, i)的tuple當key
應該就不需要那麼大的記憶體
假設真的跟記憶體有關的話
我現在想的到的是把result改成map，
用(j, i)的tuple當key
應該就不需要那麼大的記憶體
>>28544647
我覺得 bottleneck 應該不在記憶體上
server 上顯示的記憶體是 256G，不確定學校有沒有額外設定上限，但跑程式看起來是正常的
另外一個作業 (有過的) 有把記憶體吃到 80% 過也不會被 kill 掉，所以應該不是記憶體的問題
我覺得 bottleneck 應該不在記憶體上
server 上顯示的記憶體是 256G，不確定學校有沒有額外設定上限，但跑程式看起來是正常的
另外一個作業 (有過的) 有把記憶體吃到 80% 過也不會被 kill 掉，所以應該不是記憶體的問題
無題 無名 ID:qD1d2s7g 2022/08/01(一) 01:47:23.419 No.28544666
是時間複雜度的問題吧
我剛剛在我的8GB機器上跑原PO的程式
記憶體吃滿直接整個terminal被kernel kill掉踢出去
能成功跑完的話應該就不是記憶體不夠
我剛剛在我的8GB機器上跑原PO的程式
記憶體吃滿直接整個terminal被kernel kill掉踢出去
能成功跑完的話應該就不是記憶體不夠
無題 無名 ID:.rn7ggj2 2022/08/01(一) 01:51:22.501 No.28544700
無題 無名 ID:qD1d2s7g 2022/08/01(一) 01:55:28.484 No.28544733
我沒弄錯的話
外層迴圈是對每一個cell
內層迴圈是對每一個位置?
感覺內層迴圈應該到某個地方可以break出去才對...
外層迴圈是對每一個cell
內層迴圈是對每一個位置?
感覺內層迴圈應該到某個地方可以break出去才對...
無題 無名 ID:GVr9pzLk 2022/08/01(一) 01:56:24.610 No.28544742
>>28544681
填表的後半段會有很多重複
每次加入第 j 個 cell，cost_moving 都只會在特定區段內會變少，往後就會線性增加 (把 cell 往右拉)
總之 i 在 1..W 的迴圈後面部分會變成只選 cost_current (也就是沒變)
我本來想說我就額外去看 cost_moving 跟剩餘的 cost 都不變化了就直接省略 i..W 的部分
但是實作後跑下來程式反而變慢了...幹
可能是 fill_n 比 for loop assign 還慢...
殺小啦...
填表的後半段會有很多重複
每次加入第 j 個 cell，cost_moving 都只會在特定區段內會變少，往後就會線性增加 (把 cell 往右拉)
總之 i 在 1..W 的迴圈後面部分會變成只選 cost_current (也就是沒變)
我本來想說我就額外去看 cost_moving 跟剩餘的 cost 都不變化了就直接省略 i..W 的部分
但是實作後跑下來程式反而變慢了...幹
可能是 fill_n 比 for loop assign 還慢...
殺小啦...
>>28544745
所以註解部分也是正確的，只是更慢?
所以註解部分也是正確的，只是更慢?
>>28544767
在 small case 下是正確的 (8, 80, 800)
如果你想跑看看 建議用有 moving_cnt 的部分 (最晚的嘗試所以比較確定結果是一樣的)
`
// if (i < cost[1].size() - 1 && cost[1][i] == cost[1][i + 1] && cost[1][i] == cost[1][cost[1].size() - 1]) {
// if (moving_cnt > 10) {
// fill_n(cost[1].begin() + i, cost[1].size() - i , cost[1][i - 1]);
// fill_n(result[j].begin() + i, result[j].size() - i , -1);
// i = W;
// break;
// }
// }
`
助教沒有給 test script，所以我只能檢查 "是否非法" 而不能檢查 "是否 optimal"
但是助教的 hidden case 下 我那份 code 能跑過 800 & 5000
然後還有 20000, 60000, 80000 (80000有兩份，一份是public，但是 github 跟 hackmd 都傳不上去)
在 small case 下是正確的 (8, 80, 800)
如果你想跑看看 建議用有 moving_cnt 的部分 (最晚的嘗試所以比較確定結果是一樣的)
`
// if (i < cost[1].size() - 1 && cost[1][i] == cost[1][i + 1] && cost[1][i] == cost[1][cost[1].size() - 1]) {
// if (moving_cnt > 10) {
// fill_n(cost[1].begin() + i, cost[1].size() - i , cost[1][i - 1]);
// fill_n(result[j].begin() + i, result[j].size() - i , -1);
// i = W;
// break;
// }
// }
`
助教沒有給 test script，所以我只能檢查 "是否非法" 而不能檢查 "是否 optimal"
但是助教的 hidden case 下 我那份 code 能跑過 800 & 5000
然後還有 20000, 60000, 80000 (80000有兩份，一份是public，但是 github 跟 hackmd 都傳不上去)
無題 無名 ID:78nRQvvI 2022/08/01(一) 02:06:52.130 No.28544800
cell legalization有Google過、試過別人的解法了嗎?
感覺應該不會是全新的問題吧
感覺應該不會是全新的問題吧
稍微看了一下code
你的那行cost[0]=cost[1]實際上是很恐怖的東西
你就是沒辦法壓成一條array
用個指標做swap也好過你一個iterate就複製一條O(W)
你的那行cost[0]=cost[1]實際上是很恐怖的東西
你就是沒辦法壓成一條array
用個指標做swap也好過你一個iterate就複製一條O(W)
無題 無名 ID:qD1d2s7g 2022/08/01(一) 02:11:42.925 No.28544835
>>28544796
我試了一下，感覺沒有走進過這個branch啊
我試了一下，感覺沒有走進過這個branch啊
無題 無名 ID:qD1d2s7g 2022/08/01(一) 02:23:00.611 No.28544925
無題 無名 ID:nHJlbjck 2022/08/01(一) 02:25:49.893 No.28544941
我想想看能不能把它改成 top-down 的架構...
我腦袋好痛
我腦袋好痛
無題 無名 ID:qD1d2s7g 2022/08/01(一) 02:28:58.843 No.28544956
現在想的到的是
假如你知道某個區間的cost只會更高
那你應該只需要紀錄區間的頭尾
不需要全部填入
就應該可以在不用fill的情況下break
假如你知道某個區間的cost只會更高
那你應該只需要紀錄區間的頭尾
不需要全部填入
就應該可以在不用fill的情況下break
無題 無名 ID:LAfjLTnU 2022/08/01(一) 02:32:22.295 No.28544974
為什麼要電腦抓住那麼多沒用的東西
無題 無名 ID:U0/S8c0U 2022/08/01(一) 02:44:58.177 No.28545031
所以8000測資答案是啥
阿肥我記憶體只有8G沒辦法跑==
阿肥我記憶體只有8G沒辦法跑==
result[1]蓋完後result[0]就用不到了
釋放他，避免你記憶體吃太多害OS花時間在找記憶體
不要存「每個長度下各自最省代價的解法」
而是「每組具有意義的解法」，不具意義的就不存了(長度比別人長卻又沒比較省)
這不只省記憶體，也省你DP內圈的for次數
你不需要每個長度都試一次，你只要把每組解法各試一次就好
把「一組解法」包成一個struct
路徑還原的資料也寫進這個struct
以上猜的，我沒真的寫出來試試
你這期限到什麼時候？
還久的話我寫一版試試
釋放他，避免你記憶體吃太多害OS花時間在找記憶體
不要存「每個長度下各自最省代價的解法」
而是「每組具有意義的解法」，不具意義的就不存了(長度比別人長卻又沒比較省)
這不只省記憶體，也省你DP內圈的for次數
你不需要每個長度都試一次，你只要把每組解法各試一次就好
把「一組解法」包成一個struct
路徑還原的資料也寫進這個struct
以上猜的，我沒真的寫出來試試
你這期限到什麼時候？
還久的話我寫一版試試
無題 無名 ID:xsZNBPwk 2022/08/01(一) 02:49:41.408 No.28545052
>>28545033
他明天早上沒出來的話就死了
他明天早上沒出來的話就死了
無題 無名 ID:VBm8LBe2 2022/08/01(一) 02:50:02.301 No.28545054
無題 無名 ID:nHJlbjck 2022/08/01(一) 02:50:31.409 No.28545056
result改成一維，型態是struct
內含
vector<int> arr;//存位置(x')
int cost;//存cost
int width;//存長度
DP內圈改成
先複製result[最後一個]備用
對所有result裡的元素加上一個緊貼的自己
result[i].arr append(result[i].width)
result[i].cost += 我的cost(abs(width-x[j])*e[j])
result[i].width += 我的長度(w[j])
然後把result按照width從小到大排序
for result，把所有cost >= 目前最小值的元素砍了
拿出剛剛備用的更新前最後一個result
for 他的width < k <= 我的位置(x[j])
複製一份他塞進result最後
result[最後].arr append(k)
result[最後].cost += abs(k-x[j])*e[j]
result[最後].width = k+w[j]
應該差不多這樣吧，我猜
細節請自己修
還不算很漂亮，但應該比對整個width做DP來得好
內含
vector<int> arr;//存位置(x')
int cost;//存cost
int width;//存長度
DP內圈改成
先複製result[最後一個]備用
對所有result裡的元素加上一個緊貼的自己
result[i].arr append(result[i].width)
result[i].cost += 我的cost(abs(width-x[j])*e[j])
result[i].width += 我的長度(w[j])
然後把result按照width從小到大排序
for result，把所有cost >= 目前最小值的元素砍了
拿出剛剛備用的更新前最後一個result
for 他的width < k <= 我的位置(x[j])
複製一份他塞進result最後
result[最後].arr append(k)
result[最後].cost += abs(k-x[j])*e[j]
result[最後].width = k+w[j]
應該差不多這樣吧，我猜
細節請自己修
還不算很漂亮，但應該比對整個width做DP來得好
無題 無名 ID:AEFZ8GNc 2022/08/01(一) 03:34:35.981 No.28545236
>>28545185
我用看看!
我用看看!
無題 無名 ID:6K5gUgl. 2022/08/01(一) 03:39:31.913 No.28545255
sage
無題 無名 ID:5tGNkT1o 2022/08/01(一) 05:38:33.726 No.28545476
>>28545474
加油撐下去
加油撐下去
無題 無名 ID:aY/qofNk 2022/08/01(一) 05:47:47.348 No.28545489
唉 太苦了
無題 無名 ID:cFH6Esw2 2022/08/01(一) 06:04:07.775 No.28545521
天完全亮了
是否助教也醒了沒
想知道最後是生或死
有後續了?
是否助教也醒了沒
想知道最後是生或死
有後續了?
無題 無名 ID:cQaJnlhk 2022/08/01(一) 06:13:15.136 No.28545538
無題 無名 ID:pSWb49hE 2022/08/01(一) 07:45:23.047 No.28545810
無題 無名 ID:49c4JD02 2022/08/01(一) 09:59:59.210 No.28546684