Landscape Set 1

坐缆车到某个观望台上的景象

WorldFinal08_Landscape_Set1

Landscape Set 2

在Banff某座桥上拍的风景

WorldFinal08_Landscape_Set2

Landscape 3

在宾馆吃饭的地方拍的景色

WorldFinal08_Landscape_Set3

People

WorldFinal08_People

Himalaya Dragoons

Landscape Set 0

四万高空上的景象

WorldFinal08_Landscape_Set0

Banff

中国参赛队驻Banff一条街

WorldFinal08_Banff

Castle

我们住的宾馆

WorldFinal08_Castle

Icefiled

Icefiled及沿途风景

WorldFinal08_IceField

Contest

WorldFinal08_Contest

Stanford

Tsuinghua

MIT

IFMO, Champion，教练Andrew Stankevich

这段时间终于有点空，把final的照片整理了出来
看着这些照片，亦喜亦悲
整理完这一段的回忆
有关ICPC的一切大抵会被打包封藏在记忆的某一个角落

无论是情愿抑或不情愿
被太多复杂情绪萦绕牵扯
已让我在这里停留太久

如若尚有任何心绪起伏
就让我亲手平息这一切暗涌
与过去决绝
再次轻松上路

Enjoy the pain which cannot be avoided.
Be stronger, today and ever.

=================偶是天真纯洁而又心碎的分割线===============

from LynnKaye’s side,

感冒未愈加上sleeping portion效果没过，起床之后稍微有些头疼。虽然来CA之前已经有所预料，不过情况比我想象的要糟。
比赛开始发现B要推下，C估计是搜索，D是模拟，写起来都有些繁，稍微pending。
Lunarmony让我看F，开始没悟出来R和O只差4个，稍微想了些时间。这时peter带着diet coke令人感动的出现在我面前。跟peter讲了下F的思路，让他算下。有个地方忘强调了，WA了一次。
之后看B，感觉是带一堆数进去算，跟peter交流了下，peter令人感动的给出了证明。这个时候虽然一直没有看到board(座位原因。。。)，但是周围很多队已经一堆气球了。不过基本上有6、7道题有思路，也不是很慌。
之后帮A手动打了个表，然后想E。没想出来。。。T_T。。接下来是G，推了段时间，没有发现直接的数学做法，但是确定一些条件之后可以做。跟 Lunarmony交流之后，他觉得可以抖，但是当时D、I都堆在手上，有些匆忙，交流出了点问题。加上我当时没有悟出来怎么求Y的范围(我就是实例化猪。。。-_____-bbb)，决定最后一个半小时保D和I。当时感觉这两道出来肯定就有牌了，只出一题比较悬。之后协助Lunarmony check D，最后没有写完。
事实证明我们队还是后劲不足。后面感觉时间过得好快。
board出来之前，在中大BBS上看到一些消息，说有9个队7+题，稍微有些意外。其中好些欧洲的新面孔。看来这次world final扩容受益最大的还是欧洲。
还有个值得注意的地方就是中国外援队员不少。出来转到U of Wiscon的学长Chason，我看到的还有MIT的IMO金牌，UIUC，以及桌上摆着Chinese-English Dictionary的Stanford -_______-bbb

最近”I’ll be waiting for you”成了(ex?)队内流行用语。。。-_____-bbb
比如被某小朋友抛弃的手机will waiting for you…比如warning中的falling rock will waiting for you…etc…

==================偶是天真纯洁而又正义的分割线==================

You are only a whisper away
But I can’t touch your heart
If the words aren’t enough to bet your soul
I’ll give you the moon
You are always shining sun or rain
Like a violet stone
I close my eyes but you never fade
But you never disappear
I feel alone
Can’t you see me standing on the verge of blue?
I’ll be watching all the stars till they are gone Should I know nothing could make me miss you less?
*Oh I’ll be waiting for you to tell me what is love
I don’t know how to be loved, how to be by your side Morning lights shine in my room
I’m holding dreams of you
It may take no less than this pain
But I can’t stop loving you
Feel my heart
You have never know that you have all of me
Every time I see you I’m falling in love
I can live or I can’t live without you

by Yoshiki, Enternal Melody II

Andrew Stankevich’s Contest #1, ZOJ 2313-2320

Review

code量不大，有些有意思的题目，题目类型多样，难度适中

两道有点意思的数学题(2313, 2316)
两道有点意思的图论(2314, 2318)
三道不同类型的DP(树状、拼接型状态压缩、经典DP)(2315, 2317, 2319)
一道模线性方程组(2320)

Highlight

2313 Chinese Girls’ Amusement(数论)(new)
2314 Reactor Cooling(经典题)
2317 Nice Patterns Strike Back(经典题)
2318 Get Out!(图论)(new)

Detail

2313 Chinese Girls’ Amusement
Description: n(3<=n<=10^2000)个数围成一圈，从第一个数开始，每隔k(1<=k<=n/2)个数mark下，问能把n个数mark掉的最大的k是多少
Solution: 数论题
当k与n互质时，方程kx + ny = 1有解，则kx + ny = d(1<=d<=n)有解。所以要找的是与n互质的最大的k。通过找规律得出，当n为奇数时，k = n / 2，当n为偶数时，k = (n / 4 - 1) * 2 + 1。这个结论可以用手动欧几里德证明。
对于奇数：
gcd(2t + 1, t) = gcd(t, 1) = 1
对于偶数：
gcd(4t, 2t - 1) = gcd(2t - 1, 2t + 1) = gcd(2t + 1, 2) = 1
gcd(4t + 2, 2t - 1) = gcd(2t - 1, 2t + 3) = gcd(2t + 3, 4) = 1

2314 Reactor Cooling
Description: 带上下界的环形流
Solution: 经典题。
添加源点和汇点S, T，若存在边(u, v)，则添加边(S, v), (u, T)，容量为l，(u, v)的容量改为c - l。看S, T的最大流是否为sigma(li)

2315 New Year Bonus Grant
Description: 一棵有n(<=500000)个结点的树，每个结点可以分配给它的某一个子结点1000，或者被它的父结点分配1000，两者最多只能发生一种，求最大的分配方案
Solution: 树状DP。
f(i, none) = sigma(max{f(j, assign), f(j, assigned)})
f(i, assign) = max{f(k, assigned) + max{f(j, assign), f(j, none)}}
f(i, assigned) = 1000 + sigma(max{f(j, none), f(j, assign)})

2316 Matrix Multiplication
Description: 给定一个N*M的矩阵A，其中元素等于0或1，其中1有2 * M个，求T(A)*A中所有元素的和
Solution: 数学题
读入时统计出A中第i列1的个数tot(i)，则：
Sum = sigma(tot(i) * tot(i)) (1<=n<=i)
时间复杂度为O(3 * M)

2317 Nice Patterns Strike Back
Description: 求构造满足任意一个2×2矩阵中不同色的N*M(N<=10^100, M<=5)的黑白矩阵的方案数
Solution: 经典拼接型状态压缩DP
长度为2^k, 起始状态和结束状态为s1, s2的方案数为：
f(2^k, s1, s2) = f(2^(k - 1), s1, s3) * f(2^(k - 1), s4, s2)，其中s3, s4为满足要求状态对
计算出长度为2^k的方案数，然后拼起来
时间复杂度为O(log(N) * 2^5 * 2^5 * P)，其中p为预处理满足要求的状态对的个数，时限5s

2318 Get Out!
Description: 给定n(<=300)个点的位置(xi, yi)，以及圆半径ri，求某一个半径为r0的圆(x0, y0)是否能到达距离这个点无穷远的地方。
Solution: 暂缓发表

2319 Beautiful People
Description: 给定n(100000)个二元组(si, bi)，找出最多的二元组，使得对于任意两个二元组(si, bi), (sj, bj)有si > sj && bi > bj或者相反
Solution: DP
先按照si从小到大，然后找出这个新序列中以bk为keyword的最长上升序列。
时间复杂度O(n * log(n))

2320 Cracking’ RSA
Description: 给定m(<=100)个由前t(<=100)个质数乘出的数，问所有数的组合的乘积中完全平方数的个数
Solution: 求解模线性方程组解的个数
分解质因数，求解一个mod 2的线性方程组的解的个数。注意去掉全为0的解

BAPC2007, ZOJ 2912-2121

Review

比较简单的题:
2915, 2918, 2920, 2921
有一定code量的题:
2913, 2919
有点意思的题:
2912, 2914, 2916, 2917, 2919

Highlight
2912 Average distance(经典题)
2914 Cutting Banknotes(数论)(new)
2916 Lingo(容斥原理)(new)
2917 Splitting the Loot(二分+Huffman Tree)
2919 Hiking(几何+最短路)(new)

Detail

2912 Average distance
Description: 计算一棵树上所有点对的平均距离
Solution: 经典题。
遍历整棵树，统计一条边两边的顶点数，这条边经过的次数就是两边顶点数之积。

2913 Bus Pass
Description: 给定一个无权连通图中G(V, E)(V <= 9999, E <= 99990)的m(<=200)个点，求一个中心点，使得距离这个中心点最远的点的距离最短。
Solution: BFS
将每个Bus Pass的Zone一同进行BFS，直到某一个点能到达所有的Zone为止。
时间复杂度为O(V * 10 * m)，5s时限

2914 Cutting Banknotes
Description: 给定一些面值的note，可以不断细分为两部分，问能否组成一个值X，其中X带两位小数
Solution: 数论题（没想出来这个题。。。-____-bbb）

考虑一般化的问题。设可以将note细分为K份，面值为b1, b2 … bn的note的公约数为d，则可以证明当N足够大时，对于任意的M > N，均存在:
Md = b1×1 + b2×2 + b3×3 + … + bnxn
令Y = K^T * X，只要T足够大，则只要d | Y，则Y能由这些note组成
令d2 = d / K^R，其中d2为整数且不能被K整除，如果X能被d整除，则X能被note表示出来。

本题可以先将X乘以4变成整数，然后考虑K=2的情况即可

2915 Dice Password Security
Description: 给定m(<=7776)个word(3<=len(word)<=10)，从中选出n(<=5)个word，回答q(<=20)个询问：使得words总长度为li(<=50)的组成方法有多少种？
Solution: DP题。

2916 Lingo
Description: 给定一个NxN(<=8)的矩阵，上面有k个没有填的格子，问填m个格子时，有多少概率至少有一行或一列或两条对角线的中的一条被填满
Solution: 容斥原理。
枚举每条线是否被填满，然后计算方案数。注意搜索矩阵时，当前的矩阵状态可以时时维护。复杂度为O(2^18 *
相传还有DP的做法

2917 Splitting the Loot
Description: 给定一个长度为w(<=1000000)的loot，将其分成n(<=50)块，每块的长度不小于给定的wi，split的操作是将一块loot split成两块，且要损失掉p%。求最多剩下多少loot
Solution: 二分剩下的loot，然后用类似huffman的方法(最优的分割方法)求解可行性。注意剩下的为0的情况。

2918 Pachinko
Description: 一个球从一个HxW(<= 100)的矩阵顶端的某一列滚下来，碰到一个obstacle，则以50%的几率向左右两边的column继续下落，如果落到一个gate中，就有一定的winning值，求winning的期望值
Solution: DP题。

令f(c, i, j)为从第c列下落，在第i行，第j列的可能性，则有：

f(i, j) -> 0
g[i - 1][j] == ‘.’ -> f(i, j) += f(i - 1, j)
g[i - 1][j - 1] == ‘*’ -> f(i, j) += f(i - 1, j - 1) * 0.5
g[i - 1][j + 1] == ‘*’ -> f(i, j) += f(i - 1, j + 1) * 0.5

isgate(g[i][j]) -> expectedWinning += winningPoint(g[i][j]) * f(i, j)

时间复杂度为O(H * W * W)

2919 Hiking
Description: 给定半径为r的n(<=1000)个圆，求在圆的范围内的给定两点的最短路
Solution: 几何+最短路（圆内交点不计这一点没想到。。。-______-bbb）
求出所有圆的交点，最短路必定由经过这些交点的线段构成。注意在圆内的交点可以忽略不计，求最短路时用现生成的dijkstra

2920 Ranking
Descrition: 给定一些规则，模拟一个比赛的排名系统
Solution: 规则模拟题
需要注意的是在题目数和罚时相等的时候，the point of comparison between tied teams will be the last point in time where their scores differed。

2921 Stock
Description: 给定n天每天收到的stock xi，卖出价pi(0<=pi<=100)，以及最多可以卖出的stock mi，求最多的收益
Solution: 简单优值替换贪心题
从第一天开始，用一个heap维护一个卖出的价格集合，如果当天有卖出余量，且当天的价格比heap中最小的大，则将其替换掉。

Saratov School Regional Contest 2007, SGU 358-366

Review

难度中档偏简单，而且大部分是DP和模拟。

4道非常简单的题：358，362，363，365
3道比较简单的题：359，361，367
3道稍为有点难度的题：360，364，366

Highlight
360. B++ Interpreter (模拟题)
364. Lemmings (DP)
366. Computer Game (DP)

Detail

358. Median of Medians
Description: 给定三个三元组，先求出每个元组的中位数，再求这三个元组的中位数

359. Pointers
Description: 模拟一组指针操作，包括赋值，指针指定为另一指针的值，指针指定为另一指针地址，输出指针所指的值。4个指针，30条命令。
Solution: 比较简单模拟题。

360. B++ Interpreter
Description: 写一个B++语言的解析器
Solution: 稍微麻烦一点的模拟题，注意function A中调用的function B的arg可能需要替换成输入function A的arg

361. National Flag
Description: 给定一个NxM的矩阵(3<=N, M<=200)，满足任意3×2或2×3的格子中有且仅有2个#，求需要填充的最少的#的任意一个方案
Solution: 注意到3×2的填法最多有C(6, 2) = 15种，且对于任意一种填法，能推出唯一的3×3方案。于是枚举左上角的3×2矩阵，填充整个矩阵，取最小的方案。时间复杂度为O(15 * N * M)

362. Robot-Annihilator
Description: 给定Robot在矩阵中的运动规则，求出Robot的路线
Solution: 简单模拟题

363. Baggage Room
Description: 给定一个有n个窗口的service系统及排队规则，求排队序列
Solution: 简单模拟题。不过题意有点不合常理。

364. Lemmings
Description: 平面中n(n <= 100)个lemming每隔s秒以v=1的速度从一个hole A(x, h)落下，平面中有m(m <= 100)个平板，落到平板上继续按原方向以v=1的速度走，直到落到无限深处或者到达home B(a, b)。当一个lemming在平板上运动时，可以设置它stop，此后遇到它的lemming将改变方向。要求在到达home的lemming最多的条件下，最后一只lemming达到home的时间最少。
Solution: DP题。
将有效的平板(即在home所在的平板及home上面的平板)按照从低到高排序，下落到平板i的lemming有左走和右走两种状态。用Sum(i, dir)表示需要stop的lemming的数目，则有
Sum(i, left) = max{Sum(k, left), Sum(k, right) + 1}
Sum(i, right) = max{Sum(k, right), Sum(k, left) + 1}
同样可以求出时间

365. Ships of the Desert
Description: 求满足先non-descending再non-ascending的位数为s(s <= 20)的数有多少个
Solution: DP题。
f(i, j)表示长度为i，当前数字为j的non-descending的数有多少个
Ans = f(i, j) * f(k, r)，其中i + k <= s, r < j

366. Computer Game
Description: 给定n(n <= 60000)个儿元组(ai, bi), 0 <= ai, bi <= 50，从中选取k(<= min(n, 20))个，令A=sigma(aki), B=sigma(bki)在满足min(|A - B|)的条件下，max |A + B|。
Solution: DP题。
注意到-50 <= ai - bi <= 50，将元组(ai, bi)按照ai - bi之差分成101种，用F(i, j, k)表示到标号为i的元组，总共选取j个，A - B为k时，最大的|A + B|。则
F(i, j, k) = F(i - 1, r, k - i * (j - r)) + S(i, j - r), r <= j
其中S(i, k)表示选取k个标号位i的元组所能获得的最大值

可能有复杂度更低的算法。

367. Contest
Description: 给定n(n <= 1000)个problem p，pi的解决需要时间为ti，且解决的时刻为罚时，problem之间有拓扑序关系，如果pa为pb的前继，则满足ta<tb，求在时间T内，最多能解决的问题数及相应的最少罚时。
Solution: 注意到如果确定要解决m个问题，则按照需要时间从少到多的顺序解决问题，罚时最少。维护一个heap，不断将没有前继问题的problem加入这个heap，每次弹出解决时间最少的problem，最后所得的就是结果。

这套题比较水

Highlight

B 对称点解法
C 进制转换
G 中国剩余定理(new)
H 搜索

A CIVIC DILL MIX
罗马数字处理题

B A Foldy but a Goody
这 个题满有意思的。我的做法是求出fold(len, dir),即长度为len，初始方向为dir的点的偏移量和终点方向。然后由fold(len - 1)的对称拼一下。求答案的时候是以2^k一个一个接起来的，注意转角方向，一个初始为L的节点，是以L,U,L,U这样来变化的。
还有一种做法是求对称点

C Give Me an E
进制转换。注意septillion, sextillion两位不可行，要输出0

E Once Around the Lock
规则给的不甚清楚的模拟题。

D Lemmings, Lemmings Everywhere. But Not For Long
模拟题，我的T了，不想改

F A Puzzling problem
字符串+判断是否有割点(都是用的最土的字符串匹配和BFS)

G And Now, a Remainder from Our Sponsor
中国剩余定理

H Target Practice
判共线+搜索
搜索的剪枝第一是注意只过两个点的line是没有必要记下来的
第二是把状态压成long long表示(一个line穿过的points的个数)