[綜合]無題

[綜合]無題無名 ID:STzqOWhA 2022/07/31(日) 23:46:33.263 No.28543243

回覆: >>28543300 >>28543317 >>28543324 >>28543455 >>28543472 >>28543574 >>28544020 >>28544256 >>28545810 >>28546684

評分：-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

無題無名 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

不交作業不去上課
退學剛好而已吧

無題無名 ID:bfsQN2AA 2022/07/31(日) 23:51:44.911 No.28543317

回覆: >>28543361

>>28543243
K島可以直接貼程式碼不想連你的雲端

無題無名 ID:STzqOWhA 2022/07/31(日) 23:52:09.016 No.28543323

幹我都寫到 O(NW)了還是沒辦法120秒...
到底怎麼搞

無題無名 ID:2VJNb4pg 2022/07/31(日) 23:52:12.382 No.28543324

回覆: >>28543579

>>28543243
去找接案外包www

無題無名 ID:STzqOWhA 2022/07/31(日) 23:55:05.070 No.28543361

https://gist.github.com/aji-ajiaji/e81610a0f3225ee2109486866b9666f3

>>28543317
島救...

無題無名 ID:RSO2xOXA 2022/07/31(日) 23:58:27.812 No.28543412

題目是啥

無題無名 ID:krzAxpGY 2022/08/01(一) 00:01:20.296 No.28543455

>>28543243
沒人在意糞校廢物早點被退面對現實

無題無名 ID:/ydDl7fA 2022/08/01(一) 00:02:35.789 No.28543472

回覆: >>28543548

>>28543243
你不把資料全部攤開誰想看啦
現在一堆人都用手機你這個雲端超麻煩

無題無名 ID:mwkRy3WI 2022/08/01(一) 00:04:11.494 No.28543492

不是暑假了嗎怎麼要寫作業？

無題無名 ID:7cynTL1Q 2022/08/01(一) 00:04:14.189 No.28543494

回覆: >>28543548

題目是啥要輸出啥資料都不講就一擊脫離了喔

無題無名 ID:CH9z7GM2 2022/08/01(一) 00:05:19.262 No.28543512

這什麼狗屎爛變數命名

無題無名 ID:3RV58ACs 2022/08/01(一) 00:08:17.790 No.28543546

要島民幫忙你也先貼一本a漫表示誠意好嗎

無題無名 ID:XD5V8L2s 2022/08/01(一) 00:08:30.796 No.28543548

回覆: >>28543698

>>28543494
>>28543472

題目在這!

無題無名 ID:Vh5YlsBs 2022/08/01(一) 00:09:59.940 No.28543574

>>28543243
尼可以拜託那個最近常上島報告自己寫新糞島的C++島民ㄚ
雖然窩覺得他腦子不太正常

無題無名 ID:XD5V8L2s 2022/08/01(一) 00:10:14.894 No.28543579

回覆: >>28543624

>>28543324
有人知道要去哪裡嗎? 我直接去開
有島民願意幫忙就去下標 (如果有平台 ==)

無題無名 ID:2qAkcTaw 2022/08/01(一) 00:12:08.790 No.28543612

教你一招
直接辦休學來躲退學

無題無名 ID:/29jbbY2 2022/08/01(一) 00:13:17.415 No.28543624

回覆: >>28543715

>>28543579
你貼fb社團很多人會幫

無題無名 ID:/ydDl7fA 2022/08/01(一) 00:18:39.607 No.28543698

>>28543548
還以為是菜雞看到這落落長的題目
我覺得凶多吉少你耗子尾汁

無題無名 ID:7O/BBpEk 2022/08/01(一) 00:19:57.448 No.28543713

回覆: >>28543746

你跟同學關係好的話先請教同學啊

無題無名 ID:/ydDl7fA 2022/08/01(一) 00:20:20.566 No.28543715

>>28543624
FB一堆社團都只會虐菜而已這種題目大部分都直接沉進海溝裡了

無題無名 ID:XD5V8L2s 2022/08/01(一) 00:23:25.834 No.28543746

>>28543713
我就是超級邊緣延畢仔
同學都上班去了我還在這邊快被退學
島島...

我去找一下接案類的網站，晚點回來看

無題無名 ID:qD1d2s7g 2022/08/01(一) 00:24:28.163 No.28543756

回覆: >>28543818

所以你的code是有正常運作，但只是太慢?

無題無名 ID:XD5V8L2s 2022/08/01(一) 00:29:04.735 No.28543818

回覆: >>28543906 >>28544094

>>28543756
太慢，答案是對的
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

>>28543818
全部改用C寫
最簡單暴力的方法

無題無名 ID:qD1d2s7g 2022/08/01(一) 00:41:57.688 No.28543966

回覆: >>28543990 >>28544202

5000塊真的你找不到同學接喔?

無題無名 ID:cFH6Esw2 2022/08/01(一) 00:44:32.625 No.28543990

回覆: >>28544202

>>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

>>28543243
你是台大碩班嗎
怎麼會有這種沒搞好就不能畢業的東西

無題無名 ID:aY/qofNk 2022/08/01(一) 00:50:34.240 No.28544061

回覆: >>28544202

如果用這個呢?
https://cp.wiwiho.me/aliens/

無題無名 ID:tvsZyh3Q 2022/08/01(一) 00:53:08.748 No.28544094

回覆: >>28544202

>>28543818
你要不要先講一下你的解法

無題無名 ID:pbKEGQY. 2022/08/01(一) 00:58:40.982 No.28544159

回覆: >>28544317 >>28544338

從記憶體相關下手吧，給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

無題無名 ID:XD5V8L2s 2022/08/01(一) 01:03:12.929 No.28544202

回覆: >>28544328

>>28544094
基本上就是用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
可能比較有人回

無題無名 ID:XD5V8L2s 2022/08/01(一) 01:14:15.328 No.28544317

回覆: >>28544396

>>28544159
大哥你是有改過嗎? 還是機器超強
這執行時間好鬼

我是寫 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

>>28544202
該不會 pr_time 搬出去就能時間內過了吧
另外這真的有用 DP 嗎，感覺兩層迴圈都紮紮實實跑滿了

無題無名 ID:aY/qofNk 2022/08/01(一) 01:15:47.480 No.28544338

回覆: >>28544472

>>28544159
空間複雜度也是O(NW)
所以 W=600000 N=8000
需要的空間是600000*8000*4B=19.2GB
不過實際上result根本不用存那麼多東西

無題無名 ID:cFH6Esw2 2022/08/01(一) 01:19:37.939 No.28544386

要是
被退學後有甚麼打算
有想過嗎?

無題無名 ID:pbKEGQY. 2022/08/01(一) 01:20:22.944 No.28544396

回覆: >>28544472

>>28544317
5600X配32G記憶體而已，你是用很爛的機器在跑嗎?

無題無名 ID:I1DpUFn. 2022/08/01(一) 01:21:17.515 No.28544412

回覆: >>28544472

哪一間啊
啊大學會因為一科沒過就退學嗎？
還是你自己做死搞到被二一？

如果是研究所哪有啥退學
教授不滿意就一直沒法畢業啊
研究生就算再廢好歹有個奴隸幫忙做
教授哪會隨便把人踢掉？

無題無名 ID:nHJlbjck 2022/08/01(一) 01:25:39.667 No.28544472

>>28544396
我是在學校的工作站上面跑的...
如果明天早上工作站突然升級就好了

>>28544412
必修畢業年限
我是垃圾
努力過後證明自己不配的垃圾

>>28544338
我覺得應該能從每個 cell 的 x 下手，而不是像我用每個座標去做
我物理上頭真的在痛但是睡下去應該隔天就沒餘地了

無題無名 ID:qD1d2s7g 2022/08/01(一) 01:32:46.280 No.28544548

回覆: >>28544572

如果不存result然後把result的allocation也拿掉的話
DP的兩層迴圈還蠻快的(至少我跑起來是這樣
可能真的跟記憶體有關?

無題無名 ID:qD1d2s7g 2022/08/01(一) 01:35:07.374 No.28544572

>>28544548
再試了一下
感覺沒有什麼差
是我弄錯了

無題無名 ID:qD1d2s7g 2022/08/01(一) 01:37:47.828 No.28544590

回覆: >>28544597 >>28544604

你說的120秒是在什麼機器上啊?
有submit到伺服器上跑?

無題無名 ID:qD1d2s7g 2022/08/01(一) 01:38:55.948 No.28544597

回覆: >>28544634

>>28544590
噢，看到你說在工作站上跑了
我自己的電腦是不用30秒，所以這真的有點難搞...
你有開optimization嗎?

無題無名 ID:nHJlbjck 2022/08/01(一) 01:39:59.406 No.28544604

>>28544590
HPE ProLiant DL360 Gen10
沒辦法改，作業要求要傳到 server 上跑

無題無名 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/*
```

無題無名 ID:qD1d2s7g 2022/08/01(一) 01:44:09.386 No.28544647

回覆: >>28544663 >>28544666

是交到server上跑的話都沒有記憶體限制喔?
假設真的跟記憶體有關的話
我現在想的到的是把result改成map，
用(j, i)的tuple當key
應該就不需要那麼大的記憶體

無題無名 ID:nHJlbjck 2022/08/01(一) 01:47:01.259 No.28544663

回覆: >>28544681 >>28544700

>>28544647
我覺得 bottleneck 應該不在記憶體上
server 上顯示的記憶體是 256G，不確定學校有沒有額外設定上限，但跑程式看起來是正常的
另外一個作業 (有過的) 有把記憶體吃到 80% 過也不會被 kill 掉，所以應該不是記憶體的問題

無題無名 ID:qD1d2s7g 2022/08/01(一) 01:47:23.419 No.28544666

>>28544647
不過在試這個之前應該可以直接試把result拿掉
就知道問題是不是記憶體了

無題無名 ID:qD1d2s7g 2022/08/01(一) 01:49:22.300 No.28544681

回覆: >>28544745

>>28544663
好吧，那我也不知道了
你的code裡面cost_move < cost_current的else那裡是為什麼註解掉了?

無題無名 ID:CH9z7GM2 2022/08/01(一) 01:50:31.563 No.28544692

回覆: >>28544742

是時間複雜度的問題吧

我剛剛在我的8GB機器上跑原PO的程式
記憶體吃滿直接整個terminal被kernel kill掉踢出去
能成功跑完的話應該就不是記憶體不夠

無題無名 ID:.rn7ggj2 2022/08/01(一) 01:51:22.501 No.28544700

>>28544663
我已經在床上了手邊沒機器幫跑==
看上面島民跑的數據跟你描述的差那麼多我就先猜處理器問題了
你server的cache應該很破= =

無題無名 ID:qD1d2s7g 2022/08/01(一) 01:55:28.484 No.28544733

我沒弄錯的話
外層迴圈是對每一個cell
內層迴圈是對每一個位置?
感覺內層迴圈應該到某個地方可以break出去才對...

無題無名 ID:GVr9pzLk 2022/08/01(一) 01:56:24.610 No.28544742

>>28544692
你就是因為記憶體allocate不出來才被os kill掉
跟時間複雜度沒關係= =

無題無名 ID:nHJlbjck 2022/08/01(一) 01:56:47.215 No.28544745

回覆: >>28544767

>>28544681
填表的後半段會有很多重複
每次加入第 j 個 cell，cost_moving 都只會在特定區段內會變少，往後就會線性增加 (把 cell 往右拉)

總之 i 在 1..W 的迴圈後面部分會變成只選 cost_current (也就是沒變)
我本來想說我就額外去看 cost_moving 跟剩餘的 cost 都不變化了就直接省略 i..W 的部分
但是實作後跑下來程式反而變慢了...幹
可能是 fill_n 比 for loop assign 還慢...
殺小啦...

無題無名 ID:qD1d2s7g 2022/08/01(一) 02:00:29.448 No.28544767

回覆: >>28544796

>>28544745
所以註解部分也是正確的，只是更慢?

無題無名 ID:nHJlbjck 2022/08/01(一) 02:05:52.543 No.28544796

回覆: >>28544835

>>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 都傳不上去)

無題無名 ID:78nRQvvI 2022/08/01(一) 02:06:52.130 No.28544800

cell legalization有Google過、試過別人的解法了嗎?
感覺應該不會是全新的問題吧

無題無名 ID:GVr9pzLk 2022/08/01(一) 02:08:53.584 No.28544820

回覆: >>28544925

稍微看了一下code
你的那行cost[0]=cost[1]實際上是很恐怖的東西

你就是沒辦法壓成一條array
用個指標做swap也好過你一個iterate就複製一條O(W)

無題無名 ID:qD1d2s7g 2022/08/01(一) 02:11:42.925 No.28544835

>>28544796
我試了一下，感覺沒有走進過這個branch啊

無題無名 ID:qD1d2s7g 2022/08/01(一) 02:23:00.611 No.28544925

>>28544820
我試了一下，在我的電腦上幾乎沒有差
不過不知道在他的server上會有什麼不一樣...

無題無名 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

無題無名 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沒辦法跑==

無題無名 ID:46YAoQOY 2022/08/01(一) 02:45:26.280 No.28545033

回覆: >>28545052 >>28545054 >>28545056

result[1]蓋完後result[0]就用不到了
釋放他，避免你記憶體吃太多害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

>>28545033
>明天早上教授起床可能就會被當 = 退學
所以來不及了ㄏㄏ

無題無名 ID:nHJlbjck 2022/08/01(一) 02:50:31.409 No.28545056

>>28545033
到早上... G_G

補充幾個測資給大家玩
https://gist.github.com/aji-ajiaji/e81610a0f3225ee2109486866b9666f3

無題無名 ID:46YAoQOY 2022/08/01(一) 03:21:57.376 No.28545185

回覆: >>28545236

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來得好

無題無名 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:AEFZ8GNc 2022/08/01(一) 05:37:20.588 No.28545474

回覆: >>28545476 >>28545538