10762 - Treasure Castle
Moderator: Board moderators
10762 - Treasure Castle
I like this problem but unfortunately don't know how to solve it. Could you explain the idea of the solution?
The main ideia is: create any path and try to make it better.
to create a path you can walk by the walls from the entrance until the treasure. This path will be hardly the optimal.
to optimize the path you may apply 2 optimizations:
first: delete colinear adjacent points
second: Optimize the "U"'s. An "U" means 3 segments with U shape (e.g. UP, LEFT, DOWN). An U can be optimized as reducing its height or deleting one of its segments.
you may do that until we cant do any optimizations.
to create a path you can walk by the walls from the entrance until the treasure. This path will be hardly the optimal.
to optimize the path you may apply 2 optimizations:
first: delete colinear adjacent points
second: Optimize the "U"'s. An "U" means 3 segments with U shape (e.g. UP, LEFT, DOWN). An U can be optimized as reducing its height or deleting one of its segments.
you may do that until we cant do any optimizations.
-
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
-
- Experienced poster
- Posts: 123
- Joined: Thu Feb 10, 2005 4:46 am
-
- Experienced poster
- Posts: 123
- Joined: Thu Feb 10, 2005 4:46 am
edans,
Just implemented your method at O(N^2). The only optimization was doubly linked list for path (it's easier to write anyway). After removing run-time check-ups got 0.000 sec with 350 lines of rough code and lots of small oftenly called routines. How can this be??? Is there at least one spiral or snake test for N>=1000?
Just implemented your method at O(N^2). The only optimization was doubly linked list for path (it's easier to write anyway). After removing run-time check-ups got 0.000 sec with 350 lines of rough code and lots of small oftenly called routines. How can this be??? Is there at least one spiral or snake test for N>=1000?
To be the best you must become the best!
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
The description is extremely misleading (or equivalently the input is extremely weak). I assumed that N<128 and got accepted in 0.002 with an O(N^4), which means that N is probably even much smaller.
I doubt that this problem is solvable in time for values of N in the thousands. I spent a lot of time thinking about this problem, so I realy feel cheated by such small input...
I doubt that this problem is solvable in time for values of N in the thousands. I spent a lot of time thinking about this problem, so I realy feel cheated by such small input...
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.
-
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
Maybe it's because I don't understand how it's done in O(N^2), so it is just based on an estimation and the fact that none of the accepted programs had to prove themselves on input that big.
I'd be more than happy if you could explain me your algorithm and take away my doubts.
I'd be more than happy if you could explain me your algorithm and take away my doubts.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.
-
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
The most straightforward solution is a flood fill. But here there are 10000 * 10000 grid points - too many.
The key thought is to see that most grid points are useless - we can create a new grid erasing all those lines that do not cross any castle. There will be O(n^2) new grid points and properly implemented flood fill will run in O(n^2).
The key thought is to see that most grid points are useless - we can create a new grid erasing all those lines that do not cross any castle. There will be O(n^2) new grid points and properly implemented flood fill will run in O(n^2).
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
Duh. [Knocks himself on the head with a hammer]
Yes of course you're right. I also implemented this 'reduced grid', but then erroniously rejected flood fill and did a simple Dijkstra instead. But now that I think about it again, I understand that flood fill will always give the shortest distance to the entrance point (because the walls form a polygon so there are no interior walls).
Thanks for enlightening me, I was being stupid.
Yes of course you're right. I also implemented this 'reduced grid', but then erroniously rejected flood fill and did a simple Dijkstra instead. But now that I think about it again, I understand that flood fill will always give the shortest distance to the entrance point (because the walls form a polygon so there are no interior walls).
Thanks for enlightening me, I was being stupid.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.
The reduced grid is no doubt one of the first approaches those came to my mind after I read the problem (almost 1.5 years ago?). But I missed the point that flood fill on this grid will work. Don't know what I was thinking all these months. Thanks for pointing that out, Krzysztof.
(And the ':' character costs me almost 10 WA. Sigh...)
Now 98 down in v107.
I finally get one volume to be tied with the top of the world
(And the ':' character costs me almost 10 WA. Sigh...)
Now 98 down in v107.
I finally get one volume to be tied with the top of the world
-
- New poster
- Posts: 2
- Joined: Sat Jan 12, 2008 3:17 am
- Location: Brazil
Re: 10762 - Treasure Castle
I'm trying to solve this problem but i only get TLE. A changed my algorithm several times and my final algorithm is the best in performance. I implemented the A-star algorithm, with the manhatanian distance plus the number of steps being the value inserted in the priority queue. To skip the irrelevant points, i used the point-in-polygon algorithm. After the optimization, i still got i TLE. My code follows below.
Code: Select all
#include<iostream>
#include<vector>
#include<cmath>
#include<deque>
#include<map>
#include<set>
#define INSIDE 1
#define OUTSIDE 0
#define BOUNDARY -1
#define MAXV 10000
#define INF 0x7FFFFFFF
using namespace std;
const double EPS = 1e-10;
inline int cmp(double x, double y = 0, double tol = EPS)
{ return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1; }
struct Point
{
double x, y;
Point(double x=0.0, double y=0.0):x(x), y(y){}
};
typedef vector<Point> Polygon;
typedef pair<Point, int> pi;
Point entrance, treasure;
/* Produto interno dos vetores AB e BC */
double dot(Point &a, Point &b, Point &c)
{
Point ab((b.x-a.x), (b.y-a.y));
Point bc((c.x-b.x), (c.y-b.y));
return (ab.x * bc.x + ab.y * bc.y);
}
/* Produto vetorial dos vetores AB e AC -> AB x AC */
double cross(Point &a, Point &b, Point &c)
{
Point ab((b.x-a.x), (b.y-a.y));
Point ac((c.x-a.x), (c.y-a.y));
return (ab.x * ac.y - ab.y * ac.x);
}
double euclidianDist(Point &a, Point &b)
{
return sqrt((double)pow((a.x-b.x), 2.0) + (double)pow((a.y-b.y), 2.0));
}
/* Distancia do ponto p ao segmento formado por AB */
double distPointToSegment(Point &a, Point &b, Point &c)
{
double dist = cross(a, b, c) / euclidianDist(a, b);
int dot1 = dot(a,b,c);
if (dot1 > 0) return euclidianDist(b,c);
int dot2 = dot(b, a, c);
if (dot2 > 0) return euclidianDist(a,c);
return abs(dist);
}
int inPolygon(Polygon &polygon, Point p)
{
int counter = 0;
int N = polygon.size();
double xinters;
Point p1 = polygon[0];
for (int i=1; i<=N ;i++)
{
Point p2 = polygon[i % N];
double dist = distPointToSegment(p1, p2, p);
if (cmp(dist) == 0)
return BOUNDARY;
if (p.y > min(p1.y,p2.y))
{
if (p.y <= max(p1.y,p2.y))
{
if (p.x <= max(p1.x,p2.x))
{
if (p1.y != p2.y)
{
xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
if (p1.x == p2.x || p.x <= xinters)
counter++;
}
}
}
}
p1 = p2;
}
if (!(counter & 1))
return(OUTSIDE);
else
return(INSIDE);
}
struct CmpPi
{
bool operator()(const pi &a, const pi &b)
{
return (a.second <= b.second);
}
};
/* Distancia Manhataniana */
int calculDist(Point &p)
{
return (abs(p.x - treasure.x) + abs(p.y - treasure.y));
}
void insertQueue(map<int, map<int,int> > &castle, Polygon &poly, map<int, bool> &segX, map<int,bool> &segY, Point next, Point nextHalf, Point ¤t, set<pi, CmpPi> &fila)
{
if (castle[(int)next.x+MAXV][(int)next.y+MAXV] && castle[(int)next.x+MAXV][(int)next.y+MAXV] <= castle[(int)current.x+MAXV][(int)current.y+MAXV]+1)
return;
if ( (segX[next.x] || segY[next.y]) &&
(inPolygon(poly, next) == OUTSIDE || inPolygon(poly, nextHalf) == OUTSIDE))
return;
fila.insert(pi(next, castle[(int)current.x+MAXV][(int)current.y+MAXV]+1 + calculDist(next) ));
castle[(int)next.x+MAXV][(int)next.y+MAXV] = castle[(int)current.x+MAXV][(int)current.y+MAXV]+1;
}
int aStar(Polygon &poly, map<int, bool> &segX, map<int,bool> &segY)
{
map<int, map<int,int> > castle;
set<pi, CmpPi> fila;
fila.insert(pi(entrance,calculDist(entrance)));
castle[(int)entrance.x+MAXV][(int)entrance.y+MAXV] = 0;
int minimo = INF;
while (!fila.empty())
{
pi par = *fila.begin();
Point current = par.first;
//printf("Entrei (%lf, %lf)\n", current.x, current.y);
fila.erase(fila.begin());
if (par.second >= minimo) continue;
if (current.x == treasure.x && current.y == treasure.y)
{
if (castle[(int)current.x+MAXV][(int)current.y+MAXV] < minimo)
minimo = castle[(int)current.x+MAXV][(int)current.y+MAXV];
continue;
}
insertQueue(castle, poly, segX, segY, Point(current.x+1, current.y), Point(current.x+0.5, current.y), current, fila);
insertQueue(castle, poly, segX, segY, Point(current.x, current.y-1), Point(current.x, current.y-0.5), current, fila);
insertQueue(castle, poly, segX, segY, Point(current.x-1, current.y), Point(current.x-0.5, current.y), current, fila);
insertQueue(castle, poly, segX, segY, Point(current.x, current.y+1), Point(current.x, current.y-0.5), current, fila);
}
return minimo;
}
int main()
{
//long st = clock();
int id = 0;
while(true)
{
int N;
id++;
scanf("%d", &N);
if (!N) break;
Polygon poly(N);
map<int, bool> segX;
map<int, bool> segY;
for (int i = 0; i < N; i++)
{
scanf("%lf %lf", &poly[i].x, &poly[i].y);
segX[poly[i].x] = true;
segY[poly[i].y] = true;
}
scanf("%lf %lf", &entrance.x, &entrance.y);
scanf("%lf %lf", &treasure.x, &treasure.y);
printf("Castle %d: %d\n", id, aStar(poly, segX, segY));
}
//cout << (double)((double)(clock()-st) / (double)CLOCKS_PER_SEC) << endl;
}