c********l
发帖数: 8138 | 1 Google code jam上的算法题：
我目前能想到的算法是O(k * 2^n * 2^n)
也就是说，求出所有组合在k=1, k=2, k=3....直到k=k时的最小正方形覆盖
但这个复杂度实在太大了，有没有更简便的算法？
Problem
You are given n points in the plane. You are asked to cover these points
with k squares.
The squares must all be the same size, and their edges must all be parallel
to the coordinate axes.
A point is covered by a square if it lies inside the square, or on an edge
of the square.
Squares can overlap.
Find the minimum length for the squares' edges such that you can cover the n
points with k squares.
Input
The first line of input gives the number of cases, N. N test cases follow.
The first line of each test contains two positive integers n and k. Each of
the next n lines contains a point as two integers separated by exactly one
space. No point will occur more than once within a test case.
Output
For each test case, you should output one line containing "Case #X: Y" (
quotes for clarity), where X is the number of the test case, starting from 1
, and Y is the minimum length for the squares' edges for that test case.
Limits
The points' coordinates are non-negative integers smaller than 64000.
1 ≤ N ≤ 10
Small dataset
1 ≤ k < n ≤ 7
Large dataset
1 ≤ k < n ≤ 15
Sample
Input
2
5 2
1 1
2 2
3 3
6 6
7 8
3 2
3 3
3 6
6 9
Output
Case #1: 2
Case #2: 3 | d******e
发帖数: 2265 | 2 you should be able
for n points:
init n sq with l ＝ 0
then sort along x， or y
then try to merge the sq until the number of sq less then to k， with dp
appraoch.
then provide the least k
parallel
【在 c********l 的大作中提到】
: Google code jam上的算法题：
: 我目前能想到的算法是O(k * 2^n * 2^n)
: 也就是说，求出所有组合在k=1, k=2, k=3....直到k=k时的最小正方形覆盖
: 但这个复杂度实在太大了，有没有更简便的算法？
: Problem
: You are given n points in the plane. You are asked to cover these points
: with k squares.
: The squares must all be the same size, and their edges must all be parallel
: to the coordinate axes.
: A point is covered by a square if it lies inside the square, or on an edge
| c********l
发帖数: 8138 | 3 merge那一步,greedy算法就足够了吗？
每一轮的DP:
计算每一个点到附近点/矩形的距离，然后把相应的点/矩形扩大，得到一个新的矩形
然后计算新的矩形的最短大小，选取该分支
？
【在 d******e 的大作中提到】
: you should be able
: for n points:
: init n sq with l ＝ 0
: then sort along x， or y
: then try to merge the sq until the number of sq less then to k， with dp
: appraoch.
: then provide the least k
:
: parallel
| h**6
发帖数: 4160 | 4 这是一道经典的覆盖问题，用二分法可解，复杂度O(log(max edge) * n^2 * 2^n)
1. 先做二分，对于任意边长，求出覆盖这n个点需要的正方形数，大于k则增大边长，
小于k则减小边长。
2. 数学证明，覆盖给定两点的最小正方形的左下角必定位于这四个坐标之一：(x1,y1)
, (x1,y2), (x2,y1), (x2,y2). 覆盖n个点的任意子集的最小正方形的左下角必定位于
这n^2个坐标之一，(x1...n, y1...n).
3. 给定边长和n^2个左下角坐标，找出这n^2个正方形各覆盖了多少点。互相包含的覆
盖集合可略去，得到不超过n^2个覆盖集合。
4. 动态规划，最少用多少个覆盖集合能够达到全覆盖。 | h**6
发帖数: 4160 | 5 其实仅仅把第四步拿出来，就是一道高于面试难度的动态规划题了。 |
|
