<Google><APAC><kickstart><2017.05.07><2017RoundB>

Google APAC kickstart

网址链接
我的所有solution代码和文件请点击

前言

这个比赛的题怎一个变态了得，虽然是第一次参赛，抱着熟悉流程的心态去的，但仍然被虐得一颤一颤的╮(╯_╰)╭
很多题目都有trick，或者(变态的)数学知识

Problem A. Math Encoder

题目介绍

Problem

Professor Math is working on a secret project and is facing a challenge where a list of numbers need to be encoded into a single number in the most efficient manner. After much research, Professor Math finds a 3 step process that can best encode the numbers:

The first step is to find all possible non-empty subsets of the list of numbers and then, for each subset, find the difference between the largest and smallest numbers (that is, the largest minus the smallest) in that subset. Note that if there is only one number in a subset, it is both the largest and the smallest number in that subset. The complete set itself is also considered a subset.
Then add up all the differences to get the final encoded number.
As the number may be large, output the number modulo 10⁹ + 7 (1000000007).

The professor has shared an example and its explanation below. Given a list of numbers, can you help the professor build an efficient function to compute the final encoded number?

题目看得有点晕的直接看例子：

对于输入3 6 7 9的encode如下：

Find all subsets and get the difference between largest & smallest numbers:
[3], largest-smallest = 3 - 3 = 0.
[6], largest-smallest = 6 - 6 = 0.
[7], largest-smallest = 7 - 7 = 0.
[9], largest-smallest = 9 - 9 = 0.
[3, 6], largest-smallest = 6 - 3 = 3.
[3, 7], largest-smallest = 7 - 3 = 4.
[3, 9], largest-smallest = 9 - 3 = 6.
[6, 7], largest-smallest = 7 - 6 = 1.
[6, 9], largest-smallest = 9 - 6 = 3.
[7, 9], largest-smallest = 9 - 7 = 2.
[3, 6, 7], largest-smallest = 7 - 3 = 4.
[3, 6, 9], largest-smallest = 9 - 3 = 6.
[3, 7, 9], largest-smallest = 9 - 3 = 6.
[6, 7, 9], largest-smallest = 9 - 6 = 3.
[3, 6, 7, 9], largest-smallest = 9 - 3 = 6.
Find the sum of the differences calculated in the previous step:
3+4+6+1+3+2+4+6+6+3+6
= 44.
Find the answer modulo 10⁹ + 7 (1000000007):
44 % 1000000007 = 44

题解O(n^2)

首先可以看出来这就是个组合问题，但是组合这种解法太暴力了，复杂度是O(2^n)。
优化到O(n^2)还是比较简单的：思路就是固定左右两端的数(即固定max和min)，去求这样的组合有多少个。例如对上例中的3和9，他们之间有两个数字，对应2^2种组合，所以sum += 2 ^ 2 * (9 - 3)。由此我写出了这样的代码：

View Code

然后悲剧发生了，我还是太黏青了┭┮﹏┭┮，经验不足，只想着O(n^2)的复杂度还不错，于是没有管常数级复杂度，后来debug发现，对于10000个numbers的输入factor会变成2^10000，然后就算了很久很久很久....
所以血泪教训，在每次都要取模，如下：

View Code

优化到O(n)

虽然上面的代码可以通过了，但是革命的道路岂是这么短的？
于是我在想可不可以优化到O(n)，也就是说只遍历numbers一遍。
思考：如果我们用dp的思想来想这道题，那么就是
dp[i] = dp[i - 1] + sum([numbers[i] - numbers[k] * factor for k in range(i)])
- 对于[3, 6, 7, 9]这个例子：
  - dp[0] = 0
  - dp[1] = dp[0] + (6 - 3) * 1 = 3
  - dp[2] = dp[1] + (7 - 3) * 2 + (7 - 6) * 1 = 12
  - dp[3] = dp[2] + (9 - 3) * 4 + (9 - 6) * 2 + (9 - 7) * 1 = 44
上式中每次求dp[i]的时候都要遍历[0, i]，所以时间复杂度是n平方
所以我们思考能不能由dp[i - 1]直接得出dp[i]呢
当然可以呀，对上面那个dp的变化式子找规律：dp[3] = dp[2] + (dp[2] - dp[1]) * 2 + (numbers[i] - numbers[i - 1]) * (4 + 2 + 1)
所以除了保存dp[i - 1]，还要保存dp[i - 1] - dp[i - 2]，我们把它看成dp中的一个局部解
代码如下，还是要记得取模呀(取模真是个神奇的运算)。btw，上面那个O(n^2)的解要跑300多s，这个只要跑1s - -
说实话这个O(n)的算法也是比较trick的- -

View Code

Problem B. Center

相比于这一题，上一题简直不要太简单
这个题简直各种数学知识在里面：坐标变换、求max、极值等等...

题目介绍

Problem

There are N weighted points in a plane. Point i is at (X_i, Y_i) and has weight W_i.

In this problem, we need to find a special center of these points. The center is a point (X, Y) such that the sum of max(|X-X_i|, |Y-Y_i|)*W_i is minimum.

Input

The input starts with one line containing exactly one integer T, which is the number of test cases. T test cases follow.

Each test case begins with one line containing one integer N. N lines follow. Each line contains three space-separated real numbers X_i, Y_i, and W_i. X_i, Y_i and W_i have exactly 2 digits after the decimal point.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the sum of max(|X-X_i|, |Y-Y_i|)*W_i for center (X, Y).

y will be considered correct if it is within an absolute or relative error of 10^-6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

Limits

1 ≤ T ≤ 10.
-1000.00 ≤ X_i ≤ 1000.00.
-1000.00 ≤ Y_i ≤ 1000.00.

Small dataset

1 ≤ N ≤ 100;
W_i = 1.0, for all i.

Large dataset

1 ≤ N ≤ 10000;
1.0 ≤ W_i ≤ 1000.0, for all i.

题解

看到这个题目之后我们首先要分析max(|X-X_i|, |Y-Y_i|)*W_i这个式子，同时优化两个坐标，这肯定是很难的，那么有没有办法把x、y分开来优化呢？这就是很trick的地方了--> 坐标变换！！！
坐标变换
- u = (x + y) / 2
- v = (x - y) / 2

　　从而max(|X-X_i|, |Y-Y_i|)*W_i = max(|u + v - ui - vi|, |u - v - ui + vi|) * wi = ((|u - ui|) + (|v - vi|)) * wi

　　后面这个不等式我不知道怎么证明了，感觉像是高中or大学数学，但是其实质是max(|a + b|, |a - b|) = (|a + b|) + (|a - b|)，这个等式我们可以从a、b的各种情况推导出来- -

接下来的思路是参考100分的大神的- -，其思路解法实在是很变态很大神 - -
min(sum(|u - ui| * wi))和min(sum(|v - vi| * wi))是一样的，下面我们就只考虑max(|u - ui|)了。
接下来就是考虑min(sum(|u - ui| * wi))如何求u了，看到一个大神的解法如下：

View Code

　　实际上就是去找sum(wi) / 2的那个位置

实际上为了求min(sum(|u - ui|))，求最小值的话我们可以先对sum(|u -ui| * wi)求导，绝对值的导数是个分段函数，
(sum(|u -ui| * wi)) ' = sum(wi) + sum(-wj), 其中i是u左边的点，j是u右边的点。这样的话我们为了使导数为0，就是要找一个点，使它左边的所有点的权重和尽量等于右边所有点的权重和。
总结：这思路实在是太BT了 - -。最后给出代码：

def solution():
    f = open('input/B-large-practice.in.txt')
    o = open('input/resultLargeB.out', 'w+')
    lineCnt = 1
    for i in range(int(f.readline())):
        # handling each input
        pointsNum = int(f.readline())
        data, data2 = [], []
        for j in range(pointsNum):
            data.append([float(ele) for ele in f.readline().strip().split()])
        # coordinate transformation
        for x, y, w in data:
            data2.append([(x + y) / 2, (x - y) / 2, w])
        u = median(list(map(lambda x: [x[0], x[2]], data2)))
        v = median(list(map(lambda x: [x[1], x[2]], data2)))

        xs, ys = u + v, u - v
        ans = sum([max(abs(x - xs), abs(y - ys)) * w for x, y, w in data])

        print xs, ys
        print("Case #%d: %f" % (lineCnt, ans))
        o.write('Case #%d: %s' % (lineCnt, ans) + '
')
        lineCnt += 1


def median(data):
    data = sorted(data)
    s = sum(map(lambda x: x[1], data)) / 2.0
    for a, b in data:
        if s <= b: return a
        s -= b

solution()

View Code

所有完整代码见github

满地都是六便士，她却抬头看见了月亮。