SRM 504.5 Live

900 - 將 1/3 跟 1/2 弄反了
最後十分鐘才發現
隨即通過sample
然後最後幾分鐘才發現我的算法是 O(N^3), TLE
(估計 n>=500 可以approximate ?)

- 完

SRM 500 - Live

500大賽...
很難的一SET題目

250 我花了 45+ 分鐘才通過 sample...
不過縱使通過 sample 也不代表甚麼...
預期會有大量 fail system test 出現...
對自己的 submission 也沒有大期望...........

其後我看了 500
長方形的四個角落是整數座標
所以，我想大概算法是先預處理每一個格子
[x, x+1) × [y, y+1)
所包括的線段總長度吧
DFS 就好了，深度大約去到第六層
有想法，式子也準備好
但沒有足夠時間實現，更別說測試了...

但感覺 500 若能通過 sample
比起 250，應該有更大機會通過 system test

Petr 等一眾高手完成了全部 3 題...

---

rng_58 單做 1000 Rank 6th

Judge 完了
250 通過了
Rank 4th in room → 沒錢分 sosad

---

甚麼?!
lucky draw 中獎了-.-

SRM 498 - Live

So many familiar handles in my room...
This time 250 and 450 are very easy, but I solved them so slowly... :(

SRM 495

藍色留念...

http://www.topcoder.com/stat?c=round_overview&er=5&rd=14424

SRM 492

250 大失敗...orz
(原先可以秒殺既幾何題目 turn out 做得極慢)
integer division / multiplication 的正負號使我頭暈了
應該一開始就用 floating point number comparison

SRM 491 ※ Codeforces 47

[這篇 Entry 怨言居多... 慎入]

前排 ACM ICPC Regional 忙了一排... 現在還是很忙...-_-
── 最近我才意識到... 我只剩下不到兩個半月時間完成下一份 Research Project
但有 online contest 的話，我還是會盡力抽空去打
(縱使狀態不好, 仍盡量堅持打... 要習慣在狀態不好時 code...)

近來的 Online contest 都很不順利...

---

先是星期六晚 (1am) 的 SRM 491...
這場賽事題目很有意思... 我意思是題目對我來說很難...
雖然很多人提交 600 跟 900，但 sample 比較弱...
最後不少人被 Cha 或 Fail System Test
System Test 時有 "Problem"，本來說約有 10% 的 submission judge 錯了
後來等了兩三小時還未完成...

至Test 終於完成時
才聞說 Challenge Phase 臨近最後幾分鐘 Server 有事故
以致某些人的 Challenge 有問題...
至今(都兩三天了) Admin 還未做更新 Rating 與否的決定
(看來 Un-rated 的機會較大...)

>The match will be rated.
GOOD!!

SRM 486 - Live

今次係 300 + 450 + 1000
又係峰迴路轉既一場 SRM

---

300
自問速度還可以
而且code得幾靚仔
又有隨機作大 case 調試速度

450
一打開, 睇完題目 + 考慮呢題既分數
令我覺得, google 下會搵到答案
(睇完題意, 有 linearity of expectation + DP 感覺)
點知搵黎搵去, 都只係搵到 theoratical expected number of exchanges

又研究下 Case 3 = 144 / 13 究竟有咩玄機...
又戳下, 答案同 number of inversion 有乜關係

諗下... google 下... 又諗下... 又 google 下
突然間愈見愈多人交... /_\
時間漸漸消逝

Member SRM 485 - 被MO屈機

250 開始得好慢
再一次是，挺快想出算法
但 code 的時間花了很久...
Rush 250 的速度居然比以前了，為甚麼呢？

不管如何，這個奇怪的算法...
是 based on 一些 observation
但後想清楚，我只是碰巧想對了：
我當初想漏了一些條件
但因為有 odd/even 的限制，我的算法才正確

---

500... 全間 904 都沒有人能做出來
對我而言，只能想出暴力方法
不過顯然對於 W, H <= 50 而言，暴力太慢了...

waihon 則直覺認為暴搜能過，因為 RectangleAvoiding 條件苛刻

SRM 483 - 0分 悲劇

 "期待"已久的 Rating 大跌的時機終於來了...
極度低落中...

---

賽情：

比賽一開始
便緊張得錯誤開啟了 500... -_-
看完 250 是一道比較直接的整數除法 (好似係)
稍為冷靜以後, 總算把 250 慢慢的 (202.xx) 搞定...

然後開 500... 想了又想, 想出了算法: DP + bit pattern

中段開了 Division Summary 看...
很多人提交了 900... 有很多甚至時 800 以一的提交...

但自己把心一橫, 堅持做 500
比賽臨終時, 才發現 Transition 錯了...
不能只 consider 上一格 array element

再看看 Division Summary 及 Room Summary
悲劇了... 大量 900 的 Submission...
現在的 Challenge Phase, 絕大部份的 900 依然屹立不倒

SRM 481

一進房... Room3...
4個紅色 target ?!!!

難得做起 500... 極極被炒 Cha 了...
原因：overflow........!! 極灰中..............

而250... 明明算法基本上是剎那間想出...
奈何推導 + Coding 過程都很慢....
卡 sample (但這比起 Fail System Test 要好)
還好最後以 191.98 通過

是次 rating 微升19
(天... 升得好慢... 有預感很快會 "rating一舖清"...)

---

按：
Well, 原來 500 還有另一個地方錯了...
所以, 而家個心舒服番少少 @@
Sample 太不厚道...

code 250 時... 以為 sample 很厚道...
但原來有暗伏... parity...
不少使用 O(1) 算法的人都因此錯了...
而寫 for-loop version 的自己, 就沒有碰到這個問題

SRM 479

同房又見 rng_58 ...

---

250 是一道 模擬+貪心
實踐算法花了相當長的時間（主要是卡在 index）
（眾參賽者的 submission 亦相當慢）

500 的數據範圍很大，就我而言是毫無頭緒
到中後期... 見這麼多人 (約 150 ／ 600) submit 500
看來這次要下跌了...

1000 就更不用說了... 懶得開
（最後沒有人解掉此題）

---

Challenge Phase 期間
發現一個複雜度 O(44777777 × 50 × 2) 的 solution
猶疑了一兩分鐘，把 code 關掉再開...
始終自己分數太低... 還是 不敢 Cha

後來這段 code 被Cha 至 TLE 了...

SRM 478

不錯!! 雖然 ratiing 只是微昇
但, 終於到達 90 percentile 了!!
(rating 亦創下新高)

只是... 過程有點悲劇...

---

250

看到 problem statement 的第一個字 ── Rabbit
出題者是誰... 心裏大概有個譜... 知道要小心應對...
讀完整題以後... 果然沒有平日SRM般... 算法即時浮現的感覺...

由那兩條詭異的算式...
只能估計是數學題...

在沒有 idea 的情況下
挑了 init = 1 的情況
暴力 simulate 頭幾個 step 的所有 configuration...
發現... e?!
這, 花了 5 分鐘左右

然後... 考慮 init 不等於 1 時讓怎麼處理...
這, 花了 5 分鐘左右

然後... 在算法基本上成形的狀況下...
寫 code... run...
然而... 運行 sample 2 和 3
跟 correct output 比較... 死活相差 1...

SRM 477

250

唔知做乜事... 好慢!!
209.55

500

大約係, 要你喺一個以數字為 node 既 graph
搵最多既 edge s.t. 啲 edge 冇公共交點

超強烈既 Bipartite Matching 既感覺!!

SRM 475 ∩ Individual Training

本篇 entry 不是解題報告...

---

今天是 coding training
碰巧是 (非常棒的) SRM time slot
於是把 SRM 當作這次 training

大家一起在 lab SRM... 挺有氣氛的

在 SRM 開始前... tc 的 server 還是有點問題...
還好，最後大家都能順利登入

當分房完畢，按下 "Enter" 後...
發現同房有一個 target 紅色... 然後過了半秒才反應過來...

「又係 rng_58 ?!」

坐在我身旁的 those 很冷靜：「e? 入得喇？」
過了半秒，他亦驚呼：

「rng_58 ?!」

在比賽開始前 1分鐘
rng_58 突然說： "unsual point values..."

噢... 三條題目... 分數分別是 300、600、900...

[練習] SRM 473

250

Bounded ⇔ 走四個循環 返回起點

---

500

圓周上平分佈的N點中，任取三點成一直角三角形
⇔ 其中兩點連起來是直徑

所以問題轉化為統計直徑數目，M
答案 := M × (N - 2)

直接應用公式 + while-loop mark visited 選點
在最壞情況會很慢 (？)
建議實現一種類似 Linked List 的 Disjoint Set

FOR(i,0,n) parent[i] = i;
FOR(i,0,m) {
LL j = (a*i*i + b*i + c) % n;
j = find(j); // Find parent
vis[j] = 1;
parent[j] = find((j+1)%n);
}

Topcoder Open 2010 - Round 2

上一次 Round 1 跟 rng_58 同房
今次 Round 2 跟 ACRush 同房

比較慢地把 250 做出來

而那 500 的算法... Ad-hoc 到不得了
在完結前 2 min 才通過樣例並提交
結果被 cha

瓜了...

諷刺的是 rating 微升...
是因為本來的 rating 就很低的關係吧...

---

250

判定 Connecteness
Connected ⇒ Graph 是 Euler Cycle ⇒ 邊權值總和
(這裏我對於 Odd/Even degree 想了一陣子...)
Disconnected ⇒ Return -1

---

500

有好幾種算法... bsearch, monotonicity, by case 處理...

說一下 bsearch 的...

Generate 所有 由單數 digit 組成的數字 - A[N] (N = O(5⁸))
對於 i := 0 to N-1
(二分)查找最少的 A[j]
使得 A[i] + A[j] >= X
記錄最小的 A[i] + A[j]

⇒ O(N lg N)

──自己居然連如此標準 + 簡單的算法都想不出...
實在要好好反省一下... ... ... ...