10762 - Treasure Castle

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

10762 - Treasure Castle

Post by BiK » Wed Nov 10, 2004 8:35 pm

I like this problem but unfortunately don't know how to solve it. Could you explain the idea of the solution?

edans
New poster
Posts: 1
Joined: Sat Jun 12, 2004 7:20 pm
Contact:

Post by edans » Thu Nov 11, 2004 4:05 am

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.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Fri Nov 19, 2004 8:49 pm

I used a different approach - a simple BFS. The only thing you have to do is to skip irrelevant points. The solution works in O(n^2), where n is the number of castles.

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Fri Feb 18, 2005 9:07 pm

edans,

How do you check that reducing U-turn will not cause crossing some wall? I don't think that N^2 solution was author's intention... Also all AC solutions run at very low times. What was time complexity of your solution? And do you have AC now?
To be the best you must become the best!

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Mon Feb 21, 2005 3:18 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?
To be the best you must become the best!

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Feb 28, 2006 3:54 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... :evil:
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Tue Feb 28, 2006 4:22 pm

O(n^2) will work fine even for n = 5000. Why do you doubt it?
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...

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Feb 28, 2006 5:44 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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Tue Feb 28, 2006 6:01 pm

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).
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...

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Feb 28, 2006 6:42 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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Tue Apr 04, 2006 11:46 am

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 :)

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Wed Oct 11, 2006 10:38 pm

I've just used assert to check the inputsize. I got AC with only a gridsize of 10x10. The input is extremely weak. Actually, it should be 8x8 because I used both +inf and -inf also as grid points.

viniciusjssouza
New poster
Posts: 2
Joined: Sat Jan 12, 2008 3:17 am
Location: Brazil

Re: 10762 - Treasure Castle

Post by viniciusjssouza » Fri Dec 18, 2009 6:57 pm

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 &current, 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;
} 



Post Reply

Return to “Volume 107 (10700-10799)”