## 929 - Number Maze

Moderator: Board moderators

### 929 - Number Maze

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

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

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.

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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

----
sory for my poor english

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

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

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

### ok, let's discuss it here

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]
#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
nut
New poster

Posts: 4
Joined: Sat Nov 11, 2006 3:43 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]#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

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

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

### now WA

I fixed some things, and now I get WA not MLE, now the code looks like this:
[code]
#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
nut
New poster

Posts: 4
Joined: Sat Nov 11, 2006 3:43 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
`1450 2 1 9 91 9 1 0 01 1 1 9 09 9 9 9 0`

----
Sory for my poor English.

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

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.
sclo
Guru

Posts: 519
Joined: Mon Jan 23, 2006 10:45 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).

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

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
Emilio
Experienced poster

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

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
mogers
New poster

Posts: 27
Joined: Tue May 30, 2006 5:09 pm
Location: Porto, Portugal

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.

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

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 Very nice ideia indeed. I'll try it out
mogers
New poster

Posts: 27
Joined: Tue May 30, 2006 5:09 pm
Location: Porto, Portugal

Next