929 - Number Maze

[Jan]

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

[little joey]

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.

[rio]

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

----
sory for my poor english

[Jan]

Thank you both. I have got it Accepted.

[nut]

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

[rio]

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]

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]

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

[rio]

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]

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.

[rio]

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]

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]

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

[rio]

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]

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