Google Code Jam 2018 Round3 回顾

GCJ2018从Q~R2的回顾在这里,返程飞机(链接)


历程回顾

虽然当天6点就回了家,但是最近脑子一直晕乎乎的。稍微休息了一会儿,等到10点开战。

开题发现A是个送分题,还仔细看了好几遍,确定A确实是送分,写了几行代码,过了。

B描述长的惊人,看了半天好不容易看懂了题目,虽然知道考察点是啥,但是对于怎么构造完全没有想法,直接放弃。

C也看了半天才搞明白啥意思,在纸上画了画想出了$O(N^2)$的方案(其实思路是对的,只是写错了),写了半天各种不对。于是,先写了一个暴力过小数据。

然后看了半天D,完全没想法。

回过头用小数据对跑之前的方案,debug完貌似对了,就提交了一下,貌似网络有点卡,刷了半天刷出来一个√,就关机睡觉了(大概提前了1小时结束,实在没想法,而且也困了)。后来发现其实没交上去,那个勾是之前提交的,尴尬。。。赛后提交了一下,发现还是没过,review了一下发现一个下标写错了,提交过了。

总的来说Round3的难度明显强于之前的,除了A的送分题(可能是官方为了防大家光头吧)。B实际上能随机构造出很多解,这点倒是完全没想到,主要还是数学天赋太低。C虽然勉强能想出来,还是写不对啊。被B、C卡掉很多时间的选手,估计也没时间去处理D了。

今年就这样吧,至少混到衣服了。


问题简析

贴一个GCJ2018新OJ的地址.问题、排行榜、题解全有。下面我们简单过一下思路:

A. Field Trip

其实不难发现每个操作对$X$轴和$Y$轴,其实是相互独立的。这样可以对每个维度单独分析,显然,是每个维度最远的两个点距离的一半。所以,显然答案是:$Ans = ceil(max(max(X) – min(X), max(Y) – min(Y)) / 2) $


B. Name-Preserving Network

这题非常有趣,让你构造一个图,满足:
1. 每个节点有4条边,连接4个不同的节点(没有自环);
2. 图是连通的;
3. 图中每个节点的拓扑特征是唯一,任何两个节点都不相同;

关于条件3指:如果对图中的每个节点重新随机命名,你可以仅仅凭借各个节点间的连接关系,推算出每个节点原来的ID是什么。

先说一下问题的交互过程:

  • 一开始,OJ给你一对数$L$和$R$,你需要构造一个节点在区间$[L, R]$中的图,满足条件1和2。然后,你输出自己构造的图给OJ,即图有几个点,每条边连接了哪两个节点;
  • 然后,OJ会把图里的节点ID重新命名,但不会修改边的连接情况,这个过程是黑箱的,你的程序不知道;
  • 接着,OJ再把改了ID名的每条边,再输出出来。
  • 你需要根据OJ输出的图,推算出OJ把每个节点的ID从什么值改成了什么值。

是不是觉得,这种问题都能在比赛2个半小时内想出思路并成功实现,大佬们太神了。

总体思路上估计大家还是有希望能get到的。无非给每个节点设计一个特征描述,在这个描述下,任何两个节点的特征向量都不相同。这个特征,你可以设计出很多,比如:节点的特征设计成 与节点最短路距离是$D$的节点有$Count_D$个,那么就获得一个$N-1$维的特征向量。

当然,官方题解用的特征构造方法:设每个节点$i$距离为$D_i$的邻居节点集合$Set_i$,对$Set_i$中的节点$v$,其有$n_v$个邻居属于$Set_i$。那么特征向量$Fea[n_v]+=1$.
你可以通过扩展$D_i$从而获得足够分类的空间维度。

特征设计好了,下一步怎么来构造一个合法的图?

这部分是最难的。当然也是最简单的,如果你知道空间中有茫茫多个合法解的话。

方法:随机!恩就是这样,不过你需要通过一些巧妙的构造+迭代的方法,保持图始终满足条件1和2.这样就能很轻松的找到解。


C. Raise the Roof

这题说是有N个柱子,让你对它们排个序,使排序后任意相邻的3根柱子顶的平面总能盖住排在这个3个柱子之前的柱子。输入保证一定有解。

这个题看数据量是希望找一个$O(N^2)$的方法,但实际上$O(N^3)$也可以行。

思路:逆序找,假设你已经找到最后3个柱子,那么把最后一个柱子去掉,在剩下的柱子里找一个,使这个柱子和另外两个柱子能盖住剩下的柱子即可。这部分暴力$O(N^3)$即可。
最后三个柱子怎么找?显然是最高且角度与Z平面夹角最小的越好(当然,并不是解一定要这样,而是至少有个可行解满足这个条件。)。
– 最后一个柱子:找最高的一个$O(N)$。
– 倒数第二个柱子:找和最后一个柱子构成的线段与Z平面夹角最小的柱子$O(N)$。
– 倒数第3个柱子按之前的思路找就可以,枚举每个柱子,找到一个能使最后3个柱子顶起的平面遮住其他柱子即可。

如何优化到$O(N^2)$,每次找倒数第三个柱子时,找所构成平面与$Z$轴夹角最小的那个,这样找下一个柱子,只需要O(N)的复杂度,总复杂度O(N^2)。
几何题注意一些误差问题和边界,不然还是很容易跪的。


D. Fence Construction

简单说平面图上有一些线段,这些线段最多相交于定点。你可以按某个顺序画这些线段。要求:
1. 画线段是通过一个点状机器画的,这个点状机器必须在平面上,且只能在平面内移动,同时移动的时候不能穿过已经画好的线段;
2. 画线段的过程可以理解为机器已自己为中心,放出扫描线,这个线从线段的一端扫到另一端,且扫描的路径不会被别的线段遮挡;
3. 画线段的顺序是可以随意设定的,但存在一个$K$长子序列,必须按照官方给定的顺序来(子序列:元素必须保序,但可以不连续);
求一个可行解。

显然,如果,所有的线段画完后,整个图中无环的话,你可以任意顺序画,因为机器总存在路径在平面上连通任何位置。
主要问题在于有环或者有环中环怎么办?

如果,知道平面图的概念可能这个问题就比较容易抽象了。将封闭区间抽象成点,而将这些区间的边界线段(即我们要花的这些线段)抽想成边,即获得一个对偶的图。(做过相关网络流问题的同学可能更容易理解一些,如果还是想象不出来,可以看看wiki

首先,对于那些不是封闭区间边界上的线段,这些线段在一个区间被封闭前都可以任意时刻进入画上的,我们可以对偶成这个封闭区间自己对自己的一条连边。

那么核心问题就变成,对偶图里从任一点出发遍历所有的边至少一次,满足被要求的$K$条边最后一次路过的顺序满足官方给定的顺序。(可以理解成你可以用两种方式经过每条边,一种是走过一条没被染色的边,并不染色这条边;另一种是走过一条没染色的边且对其染色).或者更简单的理解就是,一个无向图(可能有子环),每次可以删除一条边,要求删完后剩下的边是连通的,要求一些边必须满足某种顺序删除。

恩,模型有了,下面怎么做呢?

从数据看$O(N^3)$足够了(甚至$O(N^4)$都可能够)。按官方给定的顺序贪心删,如果不能删,那么这个边一定是割边,那么把另一头按合法顺序删掉,再删给定的边。求割边在$O(N)$复杂度内,枚举边在$O(N^2)$,删除割边的一头所有的边,直接用bfs的拓扑序删。所以理论上$O(N^2)$差不多够了。($N$是边的个数)。


总结

今年GCJ总体说还行,工作后也不刷题了,有这结果还挺满足的。后来发现自己每场的名次居然是越来越好的。感觉比读书时的状态还要好。

《Google Code Jam 2018 Round3 回顾》

不知道明年还有没心情做了。明年再说吧。。。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.