929 - Number Maze

All about problems in Volume 9. 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
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

929 - Number Maze

Post by Jan » Sun Oct 29, 2006 10:45 am

I m using bfs with priority queue(STL). But I m getting TLE. Is there any better idea?
Ami ekhono shopno dekhi...
HomePage

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

Post by little joey » Sun Oct 29, 2006 11:07 am

That's the right approach for general graphs, but Ruben did a good job by exploiting the properties of this specific graph and letting the standard solutions get TLE. Think about it.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sun Oct 29, 2006 8:07 pm

Djkstra + priority queue(not STL) could solve it with 4 ~ 6 sec.
STL is too slow.

----
sory for my poor english

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Oct 30, 2006 3:26 pm

Thank you both. I have got it Accepted.
Ami ekhono shopno dekhi...
HomePage

nut
New poster
Posts: 4
Joined: Sat Nov 11, 2006 3:43 pm
Location: Madrid, Spain

ok, let's discuss it here

Post by nut » Sat Nov 11, 2006 7:38 pm

Actually, thanks for your help. I just didn't cheked up and left (oops), but it didn't affect to MLE.

Now it looks lile:

Code: Select all

#include <stdio.h>
#include <stdlib.h>

#define N 1000
#define LONG_MAX 2147483647 
#define MAX 10

class Queue
{
public:
  int x,y;
  Queue *next;
  Queue *prev;
  Queue *last;
  Queue *first;
  int numel;
public:
  Queue() 
  {
    numel = 0;
    first = this;
    next = this;
    prev = this;
    last = this;
  };
  
  void Push(int x, int y) // a

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sat Nov 11, 2006 8:21 pm

Even though you got a way out of MLE, i think you'll get TLE.
I tried your code with STL Queue, and got TLE. This is the code.

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
using namespace std;

#define N 1000

char maze[N][N];
long v[N][N];
int cases, m, n;
long count;

typedef pair<int, int> Point;

int main()
{
   scanf("%d", &cases);
   for (int i=0; i<cases; i++)
      {
         queue<Point> q;
         scanf("%d%d",&n,&m);
         count = 0;
         for (int j=0;j<n;j++)
            for (int k=0;k<m;k++)
               {
                  scanf("%d", &maze[j][k]);
                  v[j][k] = LONG_MAX ;
               }
         v[0][0] = maze[0][0];
         q.push(Point(0,0));

         while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            count--;
            // a

nut
New poster
Posts: 4
Joined: Sat Nov 11, 2006 3:43 pm
Location: Madrid, Spain

Post by nut » Sun Nov 12, 2006 12:07 pm

rio wrote:Even though you got a way out of MLE, i think you'll get TLE.
I tried your code with STL Queue, and got TLE. This is the code.

In your code, same places could be expanded (queued) several times.
And it is determing min-distance for all the places.
Actually, a used 10 queues in order to not waste time searching for min distance. So a could examine these 10 queues and extract the min distance in constant time.
But you're right about queuing the same element many times. I'll fix it. Thanks

nut
New poster
Posts: 4
Joined: Sat Nov 11, 2006 3:43 pm
Location: Madrid, Spain

now WA

Post by nut » Sun Nov 12, 2006 12:34 pm

I fixed some things, and now I get WA not MLE, now the code looks like this:

Code: Select all

#include <stdio.h>
#include <stdlib.h>

#define N 1000
#define LONG_MAX 2147483647 
#define MAX 10

class Queue
{
public:
  int x,y;
  Queue *next;
  Queue *prev;
  Queue *last;
  Queue *first;
  int numel;
public:
  Queue() 
  {
    numel = 0;
    first = this;
    next = this;
    prev = this;
    last = this;
  };
  
  void Push(int x, int y) // a

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sun Nov 12, 2006 1:50 pm

The algorithm seems to be wrong. Your approuch (v[x][y] = -1) is not right.
To see where your algorithm is wrong, consider this case.

Code: Select all

1
4
5
0 2 1 9 9
1 9 1 0 0
1 1 1 9 0
9 9 9 9 0
Your code outputs 5 (the answer is 4).

----
Sory for my poor English.

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

Post by sclo » Sun Nov 26, 2006 12:43 pm

I got AC using 10 STL queues to simulate dijkstra, but my time of 8.842 secs is quite bad. I think if you implement dijkstra using your own binary heap instead of STL priority_queue, it will run even faster.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sun Nov 26, 2006 2:23 pm

Implementing priority_queue with 10 queues(not STL) is what I did to get 0.936 secs.
It is much faster than using the heap (using heap(not STL) took 3 ~ 4 secs).
It enables queueing/taking out element with O(1).

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Mon Nov 27, 2006 11:10 pm

You can get AC with only one priority_queue(STL). Although I have got AC in 9.641 secs.
You must optimize your code to get AC with only one priority_queue(STL) ;)
Ah, on the other hand, I like the idea of 10 priority queues. Maybe I'll try it later :)

mogers
New poster
Posts: 29
Joined: Tue May 30, 2006 5:09 pm
Location: Porto, Portugal

Post by mogers » Fri Dec 01, 2006 2:17 am

I didnt solve this problem yet (I'm not familiar with priority_queue's non STL yet), but I was thinking in dijkstra with a heap...

Could you explain how you implement a priority queue with 10 queues ?
Or just give me a link to somewhere that explains it ?

thanks

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Fri Dec 01, 2006 3:02 am

Little hint for implementing a priority queue with 10 queues :

If you queued out a element from the i th queue, and expand it, and its adjacent element had value '6', you just need to queue it in (i + 6)%10 th queue.
In this way, you don't need to queue distance information.
(It's like a ring, so I used "ring_queue" for the queues variable name)

----
Sory for my poor English.

mogers
New poster
Posts: 29
Joined: Tue May 30, 2006 5:09 pm
Location: Porto, Portugal

Post by mogers » Fri Dec 01, 2006 2:16 pm

rio wrote:Little hint for implementing a priority queue with 10 queues :

If you queued out a element from the i th queue, and expand it, and its adjacent element had value '6', you just need to queue it in (i + 6)%10 th queue.
In this way, you don't need to queue distance information.
(It's like a ring, so I used "ring_queue" for the queues variable name)
Thank you Rio, i got it :D Very nice ideia indeed. I'll try it out :)

Post Reply

Return to “Volume 9 (900-999)”