Google Code Jam 2018 回顾 10月 8, 2018
contest
0 条评论

  • GCJ2018(Google Code Jam 2018)今年突然改了平台，从原来在选手本地机器跑测试再提交结果文件由服务器判别正确性，改成了选手提交代码，跑数据+测试都在平台上完成。整体来说这个变动不算太大，如果说有啥影响的话，只能说以前可以有效利用多核多线程加速，而现在不能用了。现在更像ACM的赛制一些。

  • 今年比较好的是比赛基本都刷在了周六周日不加班的时候，所以，就抽空做了一下。下面说说参与历程吧。

Qualification Round

  • 总的来说不算太难，不过想AK的话，还是得写一些恶心的代码。

A. Saving The Universe Again

没啥好说的，显然优先把最后一个能找到的"CS"改成"SC"即可。因为数据量不大，直接模拟即可。

B. Trouble Sort

排序完成时，一定满足$L[i] <= L[i+2] $。即奇数位置和偶数位置分别是排好序的（别用冒泡排序哦）。
所以，用sort分别对$[L[0],L[2],L[4],....,L[2k]]$与 $[L[1],L[3],L[5],....,L[2k+1]]$排序，然后归并后，遍历一遍即可。
因为，大部分语言都有各自的sort库，所以不算麻烦。

C. Go, Gopher!

一个交互题，选择一个位置，等概率命中周围$3 3$内的每一个位置，要让一个矩形区域内每一个格子至少命中一次。因为有1000次机会，但矩形面积只有200这么大，所以只要设计一个不那么坏的方法即可。
策略：矩形的长宽经可能接近，比如$10 20$就比$8 * 25$更好。每次测试点尽可能选择周围9个格子未命中比较多的位置进行测试。
这样就能过了，没仔细算过期望是多少。但是简单跑测了1000次基本在400~500次左右完成。

D. Cubic UFO

看起来复杂，其实也算比较简单。大概就是怎么转立方体，使其投影面积恰好和要求的面积相等。
显然，投影是一个凸包，定点一定是立方体8个点之一，所以转好后，把8个定点分别投影，然后求一下凸包面积即可。
小数据只用旋转一个轴即可，大数据需要转两个轴，由于是个凸问题，所以找到最大投影面积的姿态后，可以二分来微调角度。
可惜，最后输出结果时，没注意转置，不小心把XYZ轴按列向量输出了，直接挂了大数据，尴尬。（小数据能过是因为，XYZ列向量构成的矩阵恰好是XYZ行向量构成矩阵的逆，而只转一个轴，逆矩阵也是一个解，所以就过了）

  • 不过Qualification只要很少的分就能晋级，所以无压力晋级啦。

Round 1A

  • Round1的三场晋级赛难度排序，个人认为应该是Round 1B > Round 1A > Round 1C。可能因人而异吧，毕竟每个人脑回路不同。
  • 1A这场的时间，恰好不用加班，:)

A. Waffle Choppers

看完了可能会觉得很复杂，毕竟既要横切也要竖切。
不过很快发现，降一维似乎就很简单（即只横切或只竖切），在进一步发现，在一维的时候，切法几乎是唯一的（如果不考虑一段空格的出现的话）！太唬人了吧 = =
既然一维是唯一的解，那二维岂不是要么没解要么只有唯一解咯？
这样就简单多了，先解要切哪些行，再解要切哪些列，解完后两者组合起来校验即可。

B. Bit Party

二分，看起来没太多要解释的地方。

C. Edgy Baking

假设每个矩形高宽为H和W，不失一般性，假设$H<=W$。那么两个选择，如果不切贡献权重$2H+2W$如果切可以贡献权重$2H+2W+2H$ ~ $2H+2W+2sqrt(H^2+W^2)$。
对于每个矩形可选切与不切，可设计状态f(ith, length)表示前ith个矩形规划完，最小总长是length的条件下其状态可达到的最大长度是f(ith, length)。
剩下的就是标准的背包。
只要存在区间$[length, f(N,length)]$包含P那么就是P，否则$ans=max({f(N,length)})$.

  • 无压力继续晋级。

Round 1B & 1C

  • 虽然没有参与，但是过一下题吧。
  • 1B确实有些恶心啊，感觉真参与了可能做不完，大部分要想很久才能想通。

1B-A. Rounding Error

这个问题比较好玩，给你N和序列$[ci]$，都是正整数。说把正整数N分成若干的正整数ai满足$ai>=ci$，计算$qi = round(ai / N)$（round是四舍五入到整数）,目标使$\sum_1^N qi$最大。
这问题相对还是比较好想的，只要构造尽可能多的ai能恰好以"xxx.5"的格式5入就行，因为ai数量是固定的，而每个ai不是4舍就是5入。所以"xxx.0~xxx.499999999.."都是一个坑比级别的，需要尽可能避免出现。而对于5入的部分，“能省则省”，即尽可能接近0.5，而不要超过太多，比如$[0.9,0.9,0.9,0.9,0.9,0.5]$就不如$[0.5,0.5,0.5,0.5,0.5,2.5]$好。
总结发现，每个ai尽可能接近xxx.5就是最优，那么就简单了，目标就是构造尽可能多的xxx.5。
显然可以贪心，按构造成本，优化每个ai。成本计算$cost[i] = ci - floor(ci) < 0.5 ? floor(ci) + 0.5 - ci : ceil(ci) + 0.5 - ci$，把每个ai构造成恰好qi的小数部分超过0.5即可。对于剩余的数全部加给某个ax即可。

1B-B. Mysterious Road Signs

这是个看起来不复杂实际也不太好做（or证明）的问题。
既然是连续子序列，每一项要么满足Di + Ai = M；要么满足Di - Bi = N。
实际上可以理解成一个二分图，Di + Ai是左边节点的编号，Di - Bi是右边节点的编号，每加入一项，实际就加了一条边。
一个合法的子序列满足：构成的二分图最大匹配$MaxMatch<=2$。
证明：二分图最大匹配 等于 最小点覆盖，显然本题中最小点覆盖<=2才合法。
那么直接双指针维护一段最长的合法序列，再用平均$O(1)$的维护方法加入或删除每个节点即可。

1B-C. Transmutation

恩，这个自己就没想通怎么搞。看了答案才似懂非懂。
二分结果，然后用催债的方式依次递归每个节点，其核心思想是每个节点在每轮催债递归不应该被遍历超过M次，超过了说明有不可解的环。
证明：还没想出简单易懂的解释方法， = =！

  • 总之1B实在是有点恶心，还好1A那场就晋级了，不然要凉凉。
  • 与1B截然相反，1C又非常简单了。简单串一下。

1C-A. A Whole New Word

直接构造一个Trie树搜一下就好了。

1C-B. Lollipop Shop

哪怕不会计算期望，也应该能想到方案。
每次统计已发生的结果，选出观测值中概率最小的出售即可。

1C-C. Ant Stack

$O(nlogn)$的最长上升子序列一个思路。

Round 2

  • Round 2，有点尴尬，先水了A，然后看B、C一开始都没啥想法，本来已经绝望，看了D却发现会做，惊呆。
  • 赛后发现，有个A、D大数据的分，实际已经够晋级了。。。（估计很多人没想到D会那么简单，直接卡死在BC上才没晋级的吧，略尴尬啊）
  • 做完D后，心态大变，发现C又会了。做完C，准备水一下B的小数据，结果写了个尴尬的bug，恰好时间不够提交。反正也晋级了，释然。
  • 过一下思路吧。

A. Falling Balls

不难发现最后落在一个格子里的球一定来自连续的格子里。知道这点就不难了。
直接构造答案，即可。

B. Graceful Chainsaw Jugglers

小数据背包，大数据不会--（吐槽，其实后来把小数据的方法贴了一下，莫名过了大数据，到底是gg的OJ，速度真是快 = =）
看官方的报告应该是$O(R^{4/3} B^{4/3})$的方法，实际大家都是O(R^2 B^2)的方法过了。
难怪那么多满分，坑！

C. Costume Change

给你$N^2$的矩阵G（$N<=100$），每个格子有一个数$g(i,j) \in [ -N,..,-2,-1,1,2,...,N ]$。问你修改最少多少个数，使其每行每列没有相同的数。
这玩意其实是个裸体，没刷过同类题的可能很难想到（没想到gg也沦落到出原题的地步了）
对矩阵G中每种相同的数单独提出来建二分图，做最大匹配。（如当前数规划的数为-1，发现$g(1,3)=-1$那么对二分图中x=1，y=3的两个节点建边）
这个最大匹配数就是这个数最终能留下不冲突的最大可能的个数。（因为对于一种数，一行一列只能出现一个，这和二分图的匹配恰好对偶）
最后对每种数求个和就行，这就是不用改的，剩下的都要改。
那么，都要改的一定能改么?

  • 一定能！因为你一行一列总共只有$2N-1$个格子，却有$2N$种不同的数， = =！

D. Gridception

因为最后递归的很深，实际上相对于$R C$这么小的矩形，需要考虑的有效情况无非就$2^4$种。
对每种构造一个 $2R 2C$ 的大矩形，直接在里面遍历每个位置，找 $R C$ 矩形里的最大连通块即可。
我用了 $O(2^4 R^2 * C^2)$ 的暴力过的。实际答案也是如此。

Round 3

历程回顾

虽然当天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总体说还行，工作后也不刷题了，有这结果还挺满足的。后来发现自己每场的名次居然是越来越好的。感觉比读书时的状态还要好。

Post Views: 4,150