NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » 一般 » 綜合討論區
 2010NPSC決賽[純粹閒聊]

作者 主題: 2010NPSC決賽[純粹閒聊]  (閱讀 9334 次)

wudaiyang

  • 初級會員
  • **
  • 文章數: 23
    • 檢視個人資料
2010NPSC決賽[純粹閒聊]
« 於: 十二月 11, 2010, 11:54:09 pm »

今年這樣的難度應該還算蠻理想的吧
防破台的有防到
簡單題也有動小腦的價值
好像跟去年一樣都卡在三題說.....
個人覺得
   pB不用卡那麼緊
   為了卡S^2lgS也卡到常數大的S^2
   
哀擠不出第四題實在很囧的
總之高手雲集
要拿前六頗難說...
記錄

suhorng

  • 初級會員
  • **
  • 文章數: 26
    • 檢視個人資料
回覆: 2010NPSC決賽[純粹閒聊]
« 回覆 #1 於: 十二月 12, 2010, 10:16:41 am »

我覺得pB時限不緊
至少我們是WA不是TLE(呃 回家瞬間發現一個腦殘WA點 XD 不過不影響速度!)
我們做法跟評審差不多
除了最後判斷三線交於一點的部份
我們是當發現 當前在找交點的時候 是y的線跟z的線相交的話 去找對應的x線存不存在
假設相交於 (x0, y0, z0) 那該 x 線必定是 (0, y0, z0)
於是 先把所有 x 線的 y 座標離散成 0...S-1 的範圍
接著我們的做法是 開 S 個 vector
以離散後的 y 座標當 index, 把 x 線的 z 座標 push 進相對應的 vector
sort 後, 每次二分搜找尋 (當然求交點時也可以從 z 線的 y 座標遞增順序做 這樣就不用二分搜了)
總複雜度是 O(n^2 lg n) //不是 lg (n^2) 喔
不會TLE~

-

後來問第一名的隊伍 他們是直接用hash
不過把 x, y, z 線都分開來做~ 就變很快了XD

-

評審的意思好像是 y, z 都離散後直接開 [5000][5000] 存起來w
這樣應該超快! 每次輕鬆 O(1) 判斷XD 又不用memset
總時間複雜度就只有 O(n^2) www

-

常數大的 S^2 lg S ... 說不定是 lg (S^2) 啊XD
萬一又用平衡樹維護的話 真的慢到十幾二十倍 不被接受也正常吧(?)
何況那樣空間也是 S^2 呢...還要再加上平衡樹額外的空間
直接對 S^2 個點 sort 的話我們是沒試過就是..
« 上次編輯: 十二月 12, 2010, 10:18:44 am 由 suhorng »
記錄

lini

  • 高級會員
  • ****
  • 文章數: 101
    • 檢視個人資料
回覆: 2010NPSC決賽[純粹閒聊]
« 回覆 #2 於: 十二月 12, 2010, 11:47:09 am »

為了要判斷
5000*5000應該是要歸零的.

只是不用每次都5000*5000

可以比如說某一筆s=4
那就在讀下一筆前 將4*4歸零就好


時限真的很緊
我有去找評審 他們表示說
過的那4隊 全部壓在時限邊緣

我的可能加個優化IO 有機會過去 . (maybe)
code的常數其實也不是很大 . (個位數)
« 上次編輯: 十二月 12, 2010, 11:57:35 am 由 lini »
記錄

wudaiyang

  • 初級會員
  • **
  • 文章數: 23
    • 檢視個人資料
回覆: 2010NPSC決賽[純粹閒聊]
« 回覆 #3 於: 十二月 12, 2010, 12:07:57 pm »

我們這隊是CO S^2lgS
也是WA應該三線焦點找錯
離散之後阿xy座標應該可以開50000標記
這樣不用二分搜也不用sort
(應該是吧也許我有誤解)
聽說n^nlgn被卡掉好像是南一中那隊傳61次= =
記錄

suhorng

  • 初級會員
  • **
  • 文章數: 26
    • 檢視個人資料
回覆: 2010NPSC決賽[純粹閒聊]
« 回覆 #4 於: 十二月 12, 2010, 12:14:16 pm »

不用歸零

int array[5000][5000]; 是開得起來的

我常用的小技巧是

scanf("%d", &T);
while (T) {
     if (array[y][z] == T) printf("exist!\n");
     T--;
}

類似這樣

然後離散後是 5000 5000 喔不是 50000

好吧 也許時限很緊

老實說 WA也不知道是跑了幾秒XD 夠快就好(?)

呃我們WA的點在於 判斷某個數是否在一個sorted陣列中出現過的地方

STL用錯 lol 很好笑很白痴XD (對不起是我寫的Orz)
記錄

lini

  • 高級會員
  • ****
  • 文章數: 101
    • 檢視個人資料
回覆: 2010NPSC決賽[純粹閒聊]
« 回覆 #5 於: 十二月 12, 2010, 01:59:42 pm »

噢 .
大概懂了

是說
我們老師說高中前6 請吃王品  ((要不是為了這個 我也不會跑去找裁判 XD

嗚嗚 . 就差 pB ... (我的第四名 .....)
(( 只剩平價年排了 . . .




搞不好就只錯那個地方噢 XD

等測資等測資 ~~

不管怎樣
建中越來越強囉 0__0



今年題目考的演算法似乎比較基礎 ?
記錄

Nineguan

  • 初級會員
  • **
  • 文章數: 43
    • 檢視個人資料
回覆: 回覆: 2010NPSC決賽[純粹閒聊]
« 回覆 #6 於: 十二月 12, 2010, 02:28:03 pm »

嗚嗚 . 就差 pB ... (我的第四名 .....)
(( 只剩平價年排了 . . .

甚麼是"年排"啊(年級排名?!!XD)

唉差一點  我看我也必須學離散
否則一隊當中只有lini會(另外一隊:wudaiyang)
常常跟不上他的想法 也無法一起Debug
雖然我覺得lini很穩
他想Co甚麼幾乎很少出錯
連離散他都沒CO錯
很可惜TLE=   =
不過學一下也好
這樣或許可以想更快

還有pe怎麼LIS只用 O((nlgn)^2)
我怎麼想都是O((nlgn)^2 * n)
應該是差在DP吧
記錄

tmt514

  • 新手
  • *
  • 文章數: 3
    • 檢視個人資料
回覆: 回覆: 2010NPSC決賽[純粹閒聊]
« 回覆 #7 於: 十二月 12, 2010, 03:24:45 pm »

為了要判斷
5000*5000應該是要歸零的.

只是不用每次都5000*5000

可以比如說某一筆s=4
那就在讀下一筆前 將4*4歸零就好


時限真的很緊
我有去找評審 他們表示說
過的那4隊 全部壓在時限邊緣

我的可能加個優化IO 有機會過去 . (maybe)
code的常數其實也不是很大 . (個位數)

lini同學你好:

我是當時跟你說話的評審,
真得很不好意思,當時候我可能沒有說得很清楚,
我記得我說的是「我們在評審的時候有評到幾個submission的執行時間將近6秒」
這句話並不表示「過的那4隊 全部壓在時限邊緣」

實際在評審的時候,拿到Yes的隊伍,
如果我沒有記錯的話,他們的執行時間應該都沒有超過3秒,有的甚至1秒左右跑出答案

裁判長與我後來有再幫你們測試過了你們上傳的其中幾份程式碼,
第一次的確是在將近6秒的時候得到了WA
第二次的程式碼與第一次差別甚巨,執行到第8秒的時候RE
最後一次所上傳的程式碼都在9秒執行完之後WA

對於我當時所說的話,
可能一時讓你們誤會了,
真的相當抱歉!

NPSC2010眾裁判之一   黃上恩  謹上
記錄

Nineguan

  • 初級會員
  • **
  • 文章數: 43
    • 檢視個人資料
回覆: 2010NPSC決賽[純粹閒聊]
« 回覆 #8 於: 十二月 12, 2010, 03:33:04 pm »

謝謝你裁判大人

我是陪lini跟您說話的人
我是他的隊友

我們有RE喔...
最後也是WA?!!

好吧只能承認我們學藝不精
明年再來吧

還有為什麼RE會回復TLE
去年也是這樣(應該1ms就會RE)
比方說
去年初賽pe檸檬汽水
我們用VB
sub main()
   open"pe.in"for input as #1
   open"pe.out"for output as #2
....
end sub


因為我們自己生側資所以我們有一次把他改成這樣:
sub main()
   open"asd.in"for input as #1
   open"pe.out"for output as #2
....
end sub

結果不小心傳上去=   =

照往年

應該是會"找不到檔案" RE

但是去年裁判回覆TLE

到底在哪個環節出錯

還是RE TLE已經界線很難分

又或者裁判誤會了TLE

所以把RE錯誤訊息一直擺到10秒

然後回覆TLE

那根RE的精神不符合
« 上次編輯: 十二月 12, 2010, 03:40:17 pm 由 Nineguan »
記錄

suhorng

  • 初級會員
  • **
  • 文章數: 26
    • 檢視個人資料
回覆: 2010NPSC決賽[純粹閒聊]
« 回覆 #9 於: 十二月 12, 2010, 03:41:08 pm »

"執行到第8秒的時候RE"

回覆TLE有錯嗎?
記錄

tmt514

  • 新手
  • *
  • 文章數: 3
    • 檢視個人資料
回覆: 2010NPSC決賽[純粹閒聊]
« 回覆 #10 於: 十二月 12, 2010, 04:03:56 pm »

謝謝你裁判大人

我是陪lini跟您說話的人
我是他的隊友

我們有RE喔...
最後也是WA?!!


這題的時間限制是6秒,我們以PC^2裁判執行結果是TLE
前述所說的這幾個情況是把你們隊伍的程式碼從PC^2裡面取出來之後
手動測試所看到的結果。執行時間超過6秒應該判TLE無誤。
記錄

lini

  • 高級會員
  • ****
  • 文章數: 101
    • 檢視個人資料
回覆: 2010NPSC決賽[純粹閒聊]
« 回覆 #11 於: 十二月 12, 2010, 04:07:29 pm »

感謝您的回覆

不好意思誤會您的意思


摁 .

第一次在處理3線共點似乎有些錯誤
而且做了多餘的事

第二次~最後一次基本上沒變

WA .

OK . 等測資出來我再找找看問題在哪 .

回顧一下 我的解法應該沒有問題

看看程式哪裡沒照自己的想法走 .

基本上TLE是memset的問題 這點以後coding的時候會注意

RE基本上可以理解 因為中間有用char, short, unsigned short, int不同的型態( 可能char太小 . .


再次感謝您抽空回覆我們的疑問
記錄

phat

  • 新手
  • *
  • 文章數: 18
    • 檢視個人資料
回覆: 2010NPSC決賽[純粹閒聊]
« 回覆 #12 於: 十二月 12, 2010, 04:19:51 pm »

(大家都在討論pB OAO  插個題外話(?


國中組似乎還沒出現半篇文也還沒有題目(?


不過從記分板看起來這次國中組應該算是頗難(?



然後一堆國中生都有橘色氣球(pG Q



(跑掉
記錄

lini

  • 高級會員
  • ****
  • 文章數: 101
    • 檢視個人資料
回覆: 2010NPSC決賽[純粹閒聊]
« 回覆 #13 於: 十二月 12, 2010, 04:24:40 pm »

似乎是 . .

國中第一名只花半小時就拿到第一 . .

頗嚇人的 XDDD


板中的也拿了超多pG氣球呀 (( 超強的 !!!
記錄

suhorng

  • 初級會員
  • **
  • 文章數: 26
    • 檢視個人資料
回覆: 2010NPSC決賽[純粹閒聊]
« 回覆 #14 於: 十二月 12, 2010, 04:37:47 pm »

(大家都在討論pB OAO  插個題外話(?
然後一堆國中生都有橘色氣球(pG Q
(跑掉

輕鬆洩漏你的身份欸XD
記錄

Nineguan

  • 初級會員
  • **
  • 文章數: 43
    • 檢視個人資料
回覆: 2010NPSC決賽[純粹閒聊]
« 回覆 #15 於: 十二月 12, 2010, 04:39:19 pm »

哇靠真的欸
國中第一名超嚇人的

唉想當初2008年國中決賽那些題目
除了poker要很長的時間(暴力)

剩下的題目也幾乎只是考simple的brute force
喵喵捉老鼠BFS也是基礎板的吧

以現在的實力應該1小時就可以解完吧

結果國中我們還不會BFS
連brute force也寫很慢 還錯幾次=   =
與前段名次擦身而過

學校教的是VB
自然我們就很難去用演算法吧
演算法也是到了高中我們才學的

最接近的一次
也是國中的最後一次
我們就這樣浪費掉
明年還有機會嗎
記錄

phat

  • 新手
  • *
  • 文章數: 18
    • 檢視個人資料
回覆: 2010NPSC決賽[純粹閒聊]
« 回覆 #16 於: 十二月 12, 2010, 04:54:40 pm »

(大家都在討論pB OAO  插個題外話(?
然後一堆國中生都有橘色氣球(pG Q
(跑掉

輕鬆洩漏你的身份欸XD



我覺得這裡大部分人不認識我(點頭



啊啦感覺太少內容



是說這樣pE可以出個加強版,問三條LIS xD

應該可以作到N^2 lg N
« 上次編輯: 十二月 12, 2010, 04:56:11 pm 由 phat »
記錄

lini

  • 高級會員
  • ****
  • 文章數: 101
    • 檢視個人資料
回覆: 2010NPSC決賽[純粹閒聊]
« 回覆 #17 於: 十二月 12, 2010, 05:35:13 pm »

我認識你阿

你不就是住在台北 讀建中 ID是phat的XXX ...



那天

同學看到某人的名牌對我說
「欸 是游XX耶」

長相跟國中時期(誠正?) 有點差距 XDD
記錄

lini

  • 高級會員
  • ****
  • 文章數: 101
    • 檢視個人資料
回覆: 2010NPSC決賽[純粹閒聊]
« 回覆 #18 於: 十二月 12, 2010, 05:35:50 pm »

不過 . .

sagit老師呢 ?

有人知道嗎 ?
記錄

willyliu

  • 新手
  • *
  • 文章數: 13
    • 檢視個人資料
回覆: 2010NPSC決賽[純粹閒聊]
« 回覆 #19 於: 十二月 12, 2010, 09:34:31 pm »

我想請問裁判大人, 你清楚國中組的狀況嗎?

有聽說國中組用封盤的score board算名次的傳聞是真的嗎?
記錄
+ NPSC補完計劃 » 一般 » 綜合討論區
 2010NPSC決賽[純粹閒聊]