m*********t
发帖数: 527 | 1 http://community.topcoder.com/stat?c=problem_statement&pm=12928
Snake Snuke has N rectangles cut out of paper. The rectangles are labeled 0
through N-1. You are given int[]s X and Y with N elements each. For each i,
the sides of rectangle i have lengths X[i] and Y[i].
Snake Snuke will choose some of his rectangles and place them onto a table,
one rectangle at a time, in any order he likes. Each rectangle (except for
the first one) must overlap the immediately previous one, so at the end
Snuke will have a pile of rectangles. Snuke may rotate the rectangles, but
once placed, the sides of each rectangle must be parallel to the sides of
the table. (I.e., he may only swap the width and height of some rectangles
he places.) After placing all the rectangles, Snuke computes the area that
is covered by all N rectangles. (Formally, the area of their intersection.)
You are also given an int limit. The area computed by Snuke must be greater
than or equal to limit.
Return the largest positive R such that Snuke can select some R of his
rectangles and place them in such a way that the area of their intersection
is at least limit. If there is no such R, return -1 instead.
我觉得这个算是一个 combinatorial optimization 和 computational geometry 结合
的问题。 问题现在是，能不能用 knapsack 类似的 DP 方法做到 polynomial time 解
法？ | c*****n
发帖数: 95 | 2 这题可以O(n3)
遍历所有pair of rectangle, 对于每个pair 可以得到两个(因为可以旋转)相交区域的
lower bound (x' , y'). 这时res = 2
如果x' * y' >= limit
然后对剩下的rectangle 如果其长和宽都大于对应(x', y') 就res++
最后取最大的res
如果所有lower bound < limit, 返回－1
int getNum(int l1, int l2, int w1, int w2, vector& X, vector&
Y, int limit, int i, int j) {
int l = l1 < l2? l1:l2;
int w = w1 < w2? w1:w2;
if(l * w >= limit) {
int res = 2;
for(int k = 0; k < X.size(); k++) {
if(k != i && k != j) {
int kl = X[k];
int kw = Y[k];
if((kl >= l && kw >= w) || (kl >= w && kw >= l)) {
res++;
}
}
}
return res;
} else {
return 1;
}
}
int getmax(vector X, vector Y, int limit) {
int largest = 0;
for(int i = 0; i < X.size(); i++) {
int area = X[i] * Y[i];
if(area > largest) {
largest = area;
}
}
if(largest < limit) {
return -1;
}
int res = 1;
for(int i = 0; i < X.size(); i++) {
int l1 = X[i];
int w1 = Y[i];
for(int j = i + 1; j < X.size(); j++) {
int l2 = X[j];
int w2 = Y[j];
int tmp = getNum(l1, l2, w1, w2, X, Y, limit, i, j);
if(tmp > res) {
res = tmp;
}
tmp = getNum(l1, w2, w1, l2, X, Y, limit, i, j);
if(tmp > res) {
res = tmp;
}
}
}
return res;
} | r****7
发帖数: 2282 | 3 可是knapsack是NP问题啊。。。哪儿有多项式解法
0
,
,
【在 m*********t 的大作中提到】
: http://community.topcoder.com/stat?c=problem_statement&pm=12928
: Snake Snuke has N rectangles cut out of paper. The rectangles are labeled 0
: through N-1. You are given int[]s X and Y with N elements each. For each i,
: the sides of rectangle i have lengths X[i] and Y[i].
: Snake Snuke will choose some of his rectangles and place them onto a table,
: one rectangle at a time, in any order he likes. Each rectangle (except for
: the first one) must overlap the immediately previous one, so at the end
: Snuke will have a pile of rectangles. Snuke may rotate the rectangles, but
: once placed, the sides of each rectangle must be parallel to the sides of
: the table. (I.e., he may only swap the width and height of some rectangles
| r****7
发帖数: 2282 | 4 刚好刷到这题。。。
greedy就可以了
typedef map > RectType;
int PilingRectsDiv2::getmax(vector X, vector Y, int limit) {
size_t sz = X.size();
RectType rects;
int result = -1;
for (size_t i = 0; i < sz; i ++) {
int h = X[i] < Y[i] ? X[i] : Y[i];
int w = X[i] < Y[i] ? Y[i] : X[i];
if (h * w < limit) {
continue;
}
if (rects.find(h) == rects.end()) {
rects[h] = vector(1, w);
} else {
rects[h].push_back(w);
}
}
RectType::iterator it;
for (it = rects.begin(); it != rects.end(); it ++) {
sort(it->second.begin(), it->second.end());
}
for (it = rects.begin(); it != rects.end(); it ++) {
int currH = it->first;
RectType::iterator nit;
int oneResult = 0;
for (nit = it; nit != rects.end(); nit ++) {
// can use binary search to opt
for (size_t i = 0; i < nit->second.size(); i ++) {
if (currH * nit->second[i] >= limit) {
oneResult += nit->second.size() - i;
break;
}
}
}
result = max(result, oneResult);
}
return result;
}
0
,
,
【在 m*********t 的大作中提到】
: http://community.topcoder.com/stat?c=problem_statement&pm=12928
: Snake Snuke has N rectangles cut out of paper. The rectangles are labeled 0
: through N-1. You are given int[]s X and Y with N elements each. For each i,
: the sides of rectangle i have lengths X[i] and Y[i].
: Snake Snuke will choose some of his rectangles and place them onto a table,
: one rectangle at a time, in any order he likes. Each rectangle (except for
: the first one) must overlap the immediately previous one, so at the end
: Snuke will have a pile of rectangles. Snuke may rotate the rectangles, but
: once placed, the sides of each rectangle must be parallel to the sides of
: the table. (I.e., he may only swap the width and height of some rectangles
|
|
