Algorithm Kick Start

Google Kick Start 2019 H轮题解

查阅更多的题解,请点击
github传送门(求个start哇)

建议首先阅读:

先对本轮做个小结吧:总共有2098个人参加,其中有2097人有分数;我在本轮rank 260,分数为41,同分是从255名到383名(没有比赛一开始就做,跑去拿快递了,毕竟双十一orz;感觉一开始就做是不是那个255就是我了orz)。

本轮自己感觉B题较难(也是我花了两个小时,连小数据都没过的题。感觉下次可以学聪明点,不能死磕啊~)。从赛后数据(见下图)来看,大多数人也都觉得B题较难,B题小数据集的通过率和C题大数据集通过率是一样的

A. H-index

题目地址

Solution

解法

问题要求的是H-index,记作h,一个人的H-index满足两个条件:

  • 至少有h篇文章的分数不低于h
  • 不存在h+1篇文章的分数都不低于h+1

本身求H-index是一个易解的问题,直接排序即可,但题目是假设这个人在不停写文章,我们求他写了1,2,\cdots, n篇文章时的H-index,总共需要算n次。我们直接做n次排序显然是低效的,这里可维护一个已经求得有序的结果

这里问题是选择怎样的结构/算法来维护之前的结果:注意我们希望维护的历史信息一定是有可能成为解的记录,将前i+1篇的H-index记作h_{i+1},一定有:

h_{i+1}\geq h_i

既然是维护有可能成为解的历史信息,那么将历史中大于h_i的结果保存下来,这里可以用一个小根堆,:当求前i+1篇文章的H-index时,堆中的元素均大于h_i,此时若堆的大小大于h_i,才更新h_{i+1}

复杂度分析

当所有文章的分数都等于10^5时,是最差情况,总共需要\sum_{i\in[1,n]} logi 次op,具体的值可以通过级数来逼近,这里可以给出一个很粗糙的下界: O(nlogn) time.

代码

code

B. Diagonal Puzzle

題目地址

Solution

解法

对于一个n\times n的grids,总共有4*n-2条不同的对角线,一个直观的观察:一条对角线上的点仅需翻转0/1次(eg:翻转1次和3
次结果时等价的,0次和2次是等价的)

那么直观地看,每条对角线翻转或是不翻转,总共是2^{4*n-1}种情况,显然这种解法并不好,一个直观的想法是减少我们的搜索空间,这一点需要有以下观察:

ps:以下来自于官方题解

每个方格有且仅有2个对角线经过:

  • 若该方格为黑色,则经过它的两个对角线比需均翻转 or 均不翻转
  • 若该方格为白色,则经过它的两个对角线必须有且仅有一个翻转

基于上述的观察,可以两种求解思路:

  1. 减少搜索空间
    • 对于影响最大的两个对角线(主对角线和副对角线,这里的解释建议参考xcmyz),总共有4种情况:都不翻转、有一个翻转、均翻转
    • 对于任一情况,主对角线和副主对角线状态已知,其余对角线均于其相交,若交点为白色,则该对角线翻转;否则不翻转

    每种情况均需访问grids中所有位置(检查是否满足全为黑色),所以该解法是O(n^2) time

  2. 图着色(2-color)

    将grids转换为一个带权无向图

    • 顶点为原grids对角线,总共有2^{4*n-1}
    • 边为原grids中的点,经过同一个点的两个对角线之间存在连边,边权为1代表白色,0代表黑色吗,共n^2条边

    顶点染色代表对角线翻转,原问题转换为求该图的最少染色次数,染色过程需满足下述约束:

    • 权为1的两个端点颜色必须不同;为0的边,两个端点必须相同

    该问题可以用dfs求解,O(n^2) time

复杂度分析

O(n^2) time. (ps: 这里官方题解最开始给出的是O(N) time,我觉得不太对,就给他们发了邮件,12.7收到了kick start的感谢邮件,现在官方题解的时间复杂度也修正为了O(N^2) time.)

代码

code

C. Elevanagram

题目地址

Solution

解法

该题如果暴力求解,令sum(A)=\sum_{i\in[1,9]} A_i,总共有!sum(A)组合,这种求解方式无法通过大数据集。

希望减少我们的搜索空间,即排除确定性情况

  • 满足某种条件,则结果一定为Yes/No.

一个容易得到的观察,若A_i均为偶数,则结果一定为Yes

再继续观察,原问题将sum(A)个数划分为正数区(大小为a)和负数区(大小为b),显然有:

  • b=sum(A)/2 (地板除), a=sum(A)-b,

我们希望找到使结果确定的条件,注意一个数mod\ 11的结果\in [-10,10],如果能在sum(A)个数中找到一个子集满足以下条件,那么结果一定为Yes:

  • 对子集求交错和,结果可以构造出集合[-10,10]中的任一一个数,且子集正数区(大小为a1)和负数区(大小为b1)满足b1=sum(sub(A))/2 (地板除), a1=sum(sub(A))-b1

满足上述条件的子集有两种:

  • 至少有两个A_i\geq 10,或者
  • 至少有三个A_i\geq 6

满足这两个条件之一,则结果一定为Yes,其余情况则最多有一个A_i\geq 10 并且最多两个A_i\geq 6,注意这里的过大的A_i并没有什么意义,大多数都被内部加减抵消了,剩下的部分暴力一下就可以过了

复杂度分析

代码

code

11 thoughts on “Google Kick Start 2019 H轮题解”

    1. 在b题中,根据两个影响最大的对角线:主对角线和副对角线,是否翻转,可以得到4种情况:在每一种情况中,无论两个对角线是否翻转,都会看其余的对角线与之相交的部分,是白还是黑,从而确定其余对角线是否翻转,如果你觉得相交不好理解,可以看作是根据主/副对角线上元素状态来确定其余对角线的状态

  1. 您好博主,原题解表述的好像有点问题,主对角线应该指的是最长的对角线,副对角线指的是第二长的的对角线,这是我参考题解,进行了一些改变做出来的解法,https://github.com/xcmyz/prepare_programming_contest/blob/master/%E5%BF%83%E5%BE%97/Diagonal_Puzzle.md

发表评论

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