NOMS 2014

很久没更新,因为被实验室派出国参加NOMS 2014了。整整一个星期,都在波兰的克拉科夫,收获很多,也认识到了自己很多的不足。趁着还能回忆起,这里稍作记录。

一开始是由于投的论文(在多次被拒之后)中了NOMS下的Workshop,QCMan。由于中的是全文,主办方要求作者出席报告,经实验室同意后,便确定了参会。

接下来花了很多时间办相关的手续,从一开始咨询流程,到学校这边的手续、联系主办方寄邀请函,再到备齐材料到大使馆递申请等等。拿到签证前前后后花了大概两个月。真是非常非常麻烦。接下来机票和酒店等等,费用都是实验室承担。万事俱备,5月4号正式出发。

北京到克拉科夫没有直飞。汉莎航空,先是大概10个小时到慕尼黑机场,再转机到克拉科夫。

IMG_1055

慕尼黑机场,可惜不能出去。这边是G开头的登机口,貌似都是飞欧洲的航班,候机室有无限量供应的免费咖啡、茶水等等。很长很长的走廊,一眼望不到头:

IMG_1056

到克拉科夫已经是深夜12点了。匆匆洗漱后就休息了。

旅馆的早餐,很好吃
IMG_1151

接下来的两天,除了听下会议的keynote(主办方邀请知名专家作报告),基本上都是自由活动了(由于自己不是研究相关方向,以及英语水平的原因,其他作者的报告基本上无法听懂,实在是很惭愧……)。

闲逛时照的一些街景:

往主会场方向的桥上,左边的是一个大气球
IMG_1062

瓦维尔山远眺
IMG_1065

有轨电车
IMG_1057

随处可见的大群鸽子,会留住和平吧
IMG_1067

圣母教堂,游客手册难得有中文版(还是手写的)
IMG_1072

老城区的中央集市广场
IMG_1079

650年历史的亚盖隆大学,哥白尼的母校哦
IMG_1091

第三天,基本上一天都在会场刷题。下午听了同学作的报告。晚上则是主办方组织的晚宴,地点在维利奇卡盐矿

如维基百科所述,这是一个有着千年历史的老盐矿了。到了之后,是由导游带我们一路讲解,游览到2层(总共9层),到达设在地下深处的宴会大厅。

盐矿下的一个雕像
IMG_1106

不得不赞一下这里的导游,在我能听懂的程度内,她对盐矿相关历史的讲解很有趣,看得出她对自己的工作有很深热情。我现在能回忆起来的内容包括:1. 现在盐矿已停止挖掘,但仍在产盐,方式是以抽出积水的形式筛盐,同时地下水也是对盐矿的主要威胁;2. 盐矿下面长期使用马匹,世代在盐矿下繁衍的马竟然回不愿回到地面;3. 很久以前盐矿下就开始使用复杂的机械装置帮助垂直/水平运输物资。

晚宴现场
IMG_1123

整个晚宴也办得很棒。第一次参加这么正式的宴会,不懂礼节也实在没法。同一桌的也有清华和北航的老师学生。

主办方给每个人发的小纪念品(一包盐)
IMG_1124

第四天,主要都是在奥斯威辛集中营参观。

集中营大门,上面的字,含义是“劳动带来自由”
IMG_1130

各国被送往集中营的犹太人数
IMG_1135

毒气罐
IMG_1136

集中营一角
IMG_1139

断头台
IMG_1140

焚尸炉
IMG_1142

二号营——比克瑙集中营
IMG_1144

火车
IMG_1147

大片已经被纳粹烧毁的营房
IMG_1143

被烧毁的毒气淋浴室,尸体(由于太多)会被集中到后面的森林里焚毁
IMG_1148

若是失却历史记录,谁能猜到这里的过去?
IMG_1149

接下来第5天,(很悲剧的)到我上台作报告了。这里不得不说一下,自己的这篇论文。

读研以来,研究的方向是视频QoE评估。实话说,入学之后的第一次例会,当我清楚项目内容后,就放弃读博士了。很明确地了解到,自己所有的研究工作,都完全没有意义。实验室传统的方向是“网络管理”,但如果要做视频QoE,仅仅从传统的网络层面考虑很难出成果,大家却又都不愿意尝试新思路。指导老师也很早就跟我说,你如果要做图像处理,实验室是没人可以指导你的。

不过,我无论如何都想能学点什么。更何况,从小到大我也是在和学校作对,这次也不能例外。

于是,读了冈萨雷斯的数字图像处理(很多不懂),又自学了OpenCV(基本皮毛)。自己一个人钻研,很痛苦,不懂也没人问;但也很享受,因为毕竟是自己选的。最后,正是在完全闭门造车的情况下拼拼凑凑的写出了这么一篇图像处理方向的QoE论文。实话说,其水平之低,我自己都不忍心多读两遍。但是,3次被拒之后,竟然中了。

QCMan会场上,我是下午第二个作报告。在我前面的是一个奥地利学生,后面则是一个比利时学生。他们的英语水平都很好,形象风趣地阐述着自己的思想,论文质量也远比我的要好。

轮到我上台,只能对着稿子念,生硬死板,一开始还由于没有删掉排练记录的时间而NG了好几次。。。
IMG_1155

讲完之后,一位大胡子老师问了我一个问题,还好听懂了,不过回答得也不好(涉及论文缺陷)。。。真的很惭愧,坐下来之后一直在埋怨自己丢人丢到国外来。。。

最后再传几张零碎的照片吧,也感谢您读到这里:
IMG_1159

IMG_1161

IMG_1162

IMG_1163

IMG_1164

ps:回来之后还错过了GCJ Round 1C,看着board上大大的一个0分,好难受。本来比赛才应该是最重要的事。接下来要定期打Codeforces了,很多弱点只有通过比赛才能检验,再也没有任何借口。

[SPOJ 2832]

Find The Determinant III

数论

题意:输入一个最多200*200的行列式a和一个正整数p,求|a|%p。

分析:集训队论文集里《欧几里得算法的应用》的第一道例题。非常巧妙,用GCD思想作模系统下的高斯消元。实现的时候大致要注意以下几点:
(1)尽量减少辗转相除的次数;
(2)尽量少用模运算;
(3)消元过程中算出答案为0提前结束;
(4)尽量避免整行swap;
(5)手动解释输入;
(6)尽量不用long long。

TLE了一整晚后,成功刷入第一版

[POJ 1379]

Run Away

模拟退火

题意:在最大10000*10000平面的上有最多1000个洞,求平面上的某个点,使得其离所有洞的最近距离最大化。输出精度为小数点后1位。

分析:按照模拟退火的思想,在平面上随机取10个点,将单次移动的步长设为算法中的温度,移动方向随机。初始温度设为矩形对角线长的一半,每轮迭代后温度降为之前的0.8。每轮迭代时,对于每个点,按照当前步长尝试移动50次,如果目标点更优则更新位置,否则维持原位。当温度降低到0.001以下时,终止算法,并取10个点中的最优值输出。

ps:非常山寨的实现方式,没有考虑目标位置并非更优时仍进行移动的方案。本题的数据也是很松,只要控制好初始点数,温度下降幅度以及迭代次数,时限范围内很易求得最优位置。

[POJ 1263]

Reflections

计算几何

题意:给出二维平面上一个起始点和光线方向,以及平面上最多25个反射球面,问光线每次反射时击中的球编号。当不再击中球面或是反射了超过10次后终止计算。题目保证起始点不在球内,且不会沿切线方向击中球。

分析:由于数据量不大,可以每次计算出光线方向上与每个球的交点,按距离排序后取最近的一个点,根据入射角和切点算出反射角。迭代以上过程10次即可。

ps:分类表最后一题了。还差得远,继续努力。

[POJ 3336]

ACM Underground

计算几何

题意:给出一个起点和终点坐标,以及最多100条线段和3000个黑点,问从起点出发是否能到达终点。移动过程中存在以下限制:只能沿线段移动,如果遇到交点,可以转移到另一条线段上。如果移动过程中遇到黑点:若黑点在交点处,则无法转移到其他线段;否则无法跨越黑点继续沿线段移动。

分析:数据范围很小,可以首先枚举出所有的点,并对每条线段计算出所有在其上的点,排序,对所有相邻可达点连边,最后从起点出发深搜即可。这里的关键在于,处理某条线上的点时,若在相同位置遇到了黑点和白点,那么需要在后续处理中忽略所有该位置上的点。每次仅当两个相邻点都为白点时才连边,这样可以确保仅能通过有效交点转移到其他线段,且不会越过在单一线段上的黑点。

[POJ 2975] & [POJ 2960]

Nim

博弈

题意:Nim问题的必胜策略为,取当前各堆石子数的异或和,若为0则为必败局面;否则取走部分石子使得异或和变为0,便可使对方陷入必败局面。问题为,给出一个局面,问有多少种不同的必胜策略。

分析:很简单,既然必胜策略已知,那么可以算出需要改变那些位才能转化为必败局面。由于,每次只允许改变一堆石子的数目,目标石子数小于等于当前石子数时对应一种必胜策略。最后算一算有多少个堆满足该条件即可。

稍微增加难度的话,就是下面这题:

S-Nim

博弈

题意:对于基本的Nim问题,增加如下限制:每次取走的石子数必须在集合S中,若剩余石子不足则可以全部取走。问题是,对于某局面,是否存在必胜策略。

分析:对于给定的S集,考虑将剩余石子的数目划分类别。具体来说,将剩余为0或无法一步到达第0类的石子数设为第0类,可以一步到达第0类(但无法到达第1类)的设为第1类,并依次类推:可以一步到达第0…i-1类且无法到达第i类的设为第i类。这样分类之后,便可以将第i类堆与原Nim问题中的堆石子数为i对应起来。其依据在于,第i类总是能一步到达更低的类别,但无法保持当前状态(或者到达更高类别时会在下一步(由对手操作)回到该类)。由此,便可以对当前各堆的类别数取异或和,并按照结果是否为0来判定是否为必败局面。

[POJ 1478]

Island of Logic

枚举

题意:有一个岛上有3种(仅从外观无法分辨的)生物:神(只说真话)、人(白天说真话,晚上说谎话)、鬼(只说谎话)。给你一段长为n的聊天记录,要求尽量推断出更多的事实。聊天记录中最多涉及5个生物。

分析:事实分为两种,(1)生物的种族、(2)当前时间。基本思路是,可以枚举出所有的事实组合,并根据聊天记录来判断可行性。如果可行,则记录该事实组合。记录时,对于各个生物以及时间分别使用一个位相量,以逻辑或的形式记录其所有可能的取值。最后,仅存在唯一可能取值的位相量即为“事实”。

ps:350题了。每做一题在poj上排名都会略微提升,有种在尸体堆里穿行的感觉。(前辈们失敬了)

[POJ 2079]

Triangle

旋转卡壳

题意:给出最多50000个点,可取任意3点作三角形,求这些三角形中得面积最大值。

首先,可以明确的是三角形的三个顶点必定在凸包上。求出凸包后,点的数量减少到O(n^2)算法可解。

然后,需要考虑的是最大面积三角形的三点会以何种形式出现。一开始考虑的是对于所有的对踵边,枚举其对应的所有三角形,但是WA。后来发现,三角形的三边可以都不为对踵边。应该枚举的是各个点对应的最大三角形面积。在求顶点i对应的最大三角形面积时,要依次求出当j取其余n-1个点时对应的最大三角形面积,因此,可以构造如下算法:

0. 初始化顶点i为第一个顶点:
1. 初始化j为i在凸包上的下一个顶点
2. 取k为使area(i,j,k)最大的顶点,更新最大面积
3. 当j!=i时,取j为下一个顶点,回到2.;否则取i为下一个顶点,若未取尽,回到1.

其中第3步计算k时,容易利用旋转卡壳的思想证明如下结论:边(i,j+1)对应的k,必定在边(i,j)对应的k之后。由此,对于某个i,其对应的j和k的总自增次数都是O(n)级别的,总体复杂度便是O(n^2)。

[POJ 2540]

Hotter Colder

半平面交

题意:在大小为10*10的矩形内有一个“最热点”,矩形内离最热点越远越冷。初始位置(0,0),移动50次,每次给出移动的目标位置以及相对之前位置的温度变化情况。对于每次移动,需要计算可能存在最热点的区域面积。

分析:初始整个矩形都是可行的,每次移动结果若是“Hotter”或者“Colder”,相当于将之前的可行区域进行了切分;若是“Same”则可行区域变为线段,面积恒为0。每次切分可以用半平面来表示。求面积时,由于题目数据量很小,依然可以O(n^3)地处理。具体做法是,求出每两条直线间的交点(包括初始矩形对应的4条边线),然后用各半平面方程判可行,得到的可行点便是可行区域的边界点。接下来,取它们的中心,再按极坐标排序,依次求中心与每两相邻点围成三角形的面积,最后求和即可。干净利落的1A解决。

[POJ 3384]

Feng Shui

半平面交

题意:给出一个凸多边形描述,问如何在凸多边形内放两个半径都为r的圆,使两圆覆盖区域并集的面积最大。两圆可以重叠,但重叠部分面积不累加。圆不能超出凸多边形的边界。题目保证有解,若有多解,输出任意一组。

根据题意,目标要使两圆重叠区域最小。很容易推出可行的圆心区域是原凸多边形各边向内“塌缩”r后围成的新多边形。那么,在这个新多边形内,找出距离最远的两个端点即可。

实现起来也不太难,由于数据规模不大(n最多100),直接用了O(n^3)的方法。具体做法是,首先算出各边沿斜率直角方向向内平移r后的新方程,然后求各直线间的交点。由于塌缩后,某些直线会完全位于有效区域之外,因此,对于这O(n^2)个交点,需要再用n条新直线方程判是否有效。最后,在剩余的交点中找出距离最远的两个即可。