2011年7月26日星期二

[溫故知新,數論] Prmitive Root modulo n

(以下定義/定理或者未夠嚴僅... 數學人請見諒...)

記錄一下每年 "瞬耳即忘" 的數論知識...
雖然網上有很多 material
不過還是親手記下才更深刻
亦好讓日後能循著相似的思路重溫

先來的是在往年的 Training Record 就有提過...
而且(包括算法競賽)應用極廣的:

Theorem 1 (Euler's Totient Theorem)
若 (a, n) = 1
a
Φ(n) ≡ 1 (mod n)


Definition 1 (Multiplicative Order)
a 的 (multiplicative) order modulo n 是最小的 h
使得 ah ≡ 1 (mod n)
以下為 (hopefully) 較直觀的解說:
a 的 order 就是 {xi} 的最小循環節
其中 x1 := 1 (mod m), xk :=  xk-1 × a (mod n)


Definition 2 (Primitive Root)

2011年7月1日星期五

隨筆 2011-07-01 - Finals 過後...

不是考試的 Finals...
是 ACM World Finals...

World Finals 戰記一直沒心情寫
因為太遺憾吧...
(話說當日正賽過後回到房間我居然哭了... 都多少年沒有事情讓我哭過了...)

在 Joe 發佈戰記那一天
才有一點刺激讓我花幾個小時一口氣寫了一大堆...
不過那才記述了三份一至二份之一...
然後又因沒心情 +種種事務繁忙一直沒有再寫...

就這樣, 居然一拖便拖了一個月時間...



今年是 CUHK 的尖峰吧...?

2011年5月30日星期一

[ACM ICPC] World Finals 2011 : Day 2 熱身

(近兩日上網速度大覆降低...)
(相片後補...)

是日活動全部在酒店舉行
但行程相當緊湊



Opening Ceremony
跟以往差不多



Contest Orientation
試了 stack size 等等的東西
貌似拿了個還可以的 rank 3

2011年5月29日星期日

[ACM ICPC] World Finals 2011 : Day 1 SeaWorld Orlando※Welcoming

天氣仍是極好

IBM tech talk @ SeaWorld      @@
Whale show



看了各種海洋生物
拍了頗多 相片 / 影片

雲宵飛車 : Manta, Kraken 非常恐怖

2011年5月28日星期六

[ACM ICPC] World Finals 2011 : Day 0 Training※Florida Mall※Registration


早上 7:30am



今天的早餐是 Omelet
很貴........



9am~2pm - Training: Pacific Northwest 2010
有點不順利
大量TLE (雖然很懷疑 on site 時間應該更加寛鬆)

嗯... 這次應該是人生中最後一次ACM Training...
ACM 生涯快要結束了...
稍有感觸...

2011年5月27日星期五

[ACM ICPC] World Finals 2011 : Day -1 Training※Disneyland

Slept at 12am, woke up at 7:30am...

Training : 9am~1:30pm - World Finals 2007

A bit tired... maybe jet lag
but seems that a coffee is a must for waking me up early in the morning...

2011年5月26日星期四

[ACM ICPC] World Finals 2011 : Day -2 抵步

雖然在香港出發前出現一些波折遲了點登機
但最後我們以及所有行李總算平抵抵步

花了大約24小時
終於到達酒店... Peabody@Orlando



我們的行程是這樣的:
  • Hong Kong → Chicago (~14.5 HR)
  • 等候轉機 (~4 HR)
  • Chicago → Orlando (~3 HR)
  • Immigration + Taxi to hotel (~1 HR)
(略過某些等候的時間)

2011年5月20日星期五

隨筆 2011-05-20

相信自己
相信隊友


Time to World Final: 9 days, 15 hours, 52 minutes, 24 seconds

2011年5月18日星期三

SRM 504.5 Live

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

- 完

2011年5月4日星期三

隨筆 2011-05-04

術式:嘈音攻擊
效果:目標各項能力值下降 70%、憤怒值上昇 50%

2011年4月5日星期二

Hefei 2009 Problem H - Chinese Paper Cutting

Hefei 2009 Problem H AC 留念...
LOC ~= 280



題目大意(嚴謹細節略去):
給一長方形紙張,T 個操作,操作分兩種:
  1. 垂直/打橫對摺
  2. 沿著某些連續的水平/垂直線段栽剪
在每個栽剪操作後,若果紙張被分為多個部份,只保留面積最大的部份。
在所有操作完成後,還原所有對摺操作。

求最終剩餘的紙張部份。

2011年3月24日星期四

2011-03-23 Team Training - World Finals 2004

2011-03-23 Wed
HKG Time - 1900 to 2400

啱啱尋晚係 research deadline 後
第二次正式齊腳 training

今次做 World Finals 2004
悲劇呀!

2011年3月20日星期日

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 中獎了-.-

2011年3月3日星期四

[2D Geomtry] 二維線段交點

在本篇 entry 我們談一談二維線段交點求解方法
本人認為,最後討論的 "三角形面積方法" 的解相當優美



直線方程組方法


中學時期,我們都學過用聯立方程組求 線 / 線交點:

A x + B y = C
D x + E y = F

可這個方法缺點是
用代入法 (substitution) 或消元法  (elimination) 求出的一般解
在 x系數 = 0 或 y系數 = 0 的情況需要特別分開處理

我們亦不能單從 solution
簡單判斷交點 Q 是否在線段 AB 或 CD 之內



向量方法


這是在 year 1 暑假 ACM training 時學會的
感覺相當強大、漂亮

將兩條線段表示成:

P1 = A + s AB -------- (1)
P2 = C + t CD -------- (2)

其中 s, t 分別是 線段AB,CD 的參數

2011年2月27日星期日

SRM 498 - Live

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

2011年2月17日星期四

隨筆 2011-02-17 - 亂七八糟的寫一篇...

有時候真的發覺「成事在天」

Paper的事... 也由不得我擔心太多



先前 Conference paper deadline 跟 ICPC World Finals 撞期了
後來 World Finals 又因為埃及政治事件需要延期...

在我來看,算是好事

2011年2月5日星期六

[UVa] Sixth Contest of Newbies

Links:


余以為絕對是值得花時間做的一SET題目...

題目質素高
時限相當緊
Test Data 亦相當狠 (很多 set...)
(題目也相當 "陰"...)

雖然具備基本知識,理論上新手都可以解出起碼三題
不過... 這都包含相當多細節,不是一般的題目呀...



題解概要:

A: Soya Milk - 簡單2D幾何
分兩種情況:水平線 touch length/height

B: Closest Fractions - 枚舉
Contest 時 RP較高
預處理GCD後 O(1000^2) 暴試 0.9xx sec 水過了

2011年1月27日星期四

Codeforces #57

2010-02-26 Wed
HKG Time - 0000 to 0200

終於... 在一次 individual contest 做到少人完成的難題目了...!



題解概要:

2011年1月2日星期日

HDU 3748 Equivalent mass

Problem Statement:
  • Given N elements, A[N], determine if it is possible to pick exactly K of them s.t. the sum is V. But you cannot pick Xth and Yth simultaneously, for some given pairs (X, Y). There are M such pairs.

Constraints:
  • 1 <= N <= 32
  • 1 <= A[i], V <= 10^9
  • 0 <= M <= 6
  • 0 <= K <= N