## 929 - Number Maze

Moderator: Board moderators

### Re: 929 - Number Maze

Did you read the rest of this thread? 10 normal queues in a ring to make a priority queue for this problem is fast enough.
brianfry713
Guru

Posts: 1771
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 929 - Number Maze

In case of TLE, the only comment I've seen on the forum for improving the speed of problem 929, was to split the queue in 10x queues (based on the initial weight of the edges). This is a strange hack, that - to my understanding - may improve the speed performance only because 10x queues have a smaller length than one queue. I do not recommend it, especially as Dijkstra works on the weights of the NODES, so the initial weight of the EDGES is irrelevant.

1. I got AC with a basic priority_queue (not the STL one), a basic modification of <multiset> such all operations run in less than O(ln(n)) - I especially mean the "alter" method.
2. Also important to note is that compared to Cormen's Dijkstra, where queue is fed with all node values at the beginning, to save queue length you can opt to insert the node in the queue, only when it first changes value. This is very useful, because nodes share only maximum 4 connections, so most of the time the further-away nodes will not be needed, so instead of having all nodes in the queue (~ n^2), I will only keep the "border" (~n) -> thus we save a factor of O(n) for the queue length.

Given the large number of "alter" operations, probably the best option would be to implement a Fibonacci-heap.
vpanait
New poster

Posts: 17
Joined: Sun Apr 01, 2012 11:01 am

### Re: 929 - Number Maze

My code passes all of the sample i/o that I have seen and still gives ``Wrong Answer".
Code: Select all
`Code removed after AC, problem in deleting from the heap.`

pranon
New poster

Posts: 14
Joined: Mon Jul 23, 2012 2:39 pm

### Re: 929 - Number Maze

Input:
Code: Select all
`133164 6 9 7 6 0 3 4 6 0 8 5 1 2 1 89 6 0 3 8 7 1 3 3 4 1 2 9 5 5 34 4 3 0 6 6 6 2 9 6 7 2 1 0 1 06 1 3 6 0 4 9 5 1 3 7 0 8 2 5 48 8 6 4 7 4 6 6 1 5 8 2 5 1 2 34 7 0 4 2 1 9 5 4 8 5 5 2 0 9 29 8 6 6 2 4 4 5 1 4 9 8 6 3 2 01 4 7 5 5 8 0 0 7 5 5 1 7 6 4 84 2 6 9 7 0 4 0 5 4 9 3 7 3 3 09 2 5 6 1 5 8 0 2 3 1 0 2 5 0 68 7 7 7 9 2 9 6 8 0 9 7 3 5 8 47 3 1 0 1 9 0 3 5 2 5 7 9 8 5 95 3 8 6 7 8 3 5 8 2 2 4 9 2 8 76 1 9 9 1 0 2 8 4 0 7 5 8 2 5 57 3 1 4 3 4 1 4 9 4 0 8 8 8 7 42 7 5 5 9 0 3 3 0 0 8 0 4 5 5 21 8 8 6 5 0 0 6 6 0 6 4 1 4 1 33 6 8 2 6 3 7 8 3 7 8 7 3 5 1 66 0 2 1 2 3 7 8 5 3 4 6 9 5 1 24 9 6 2 4 3 1 7 3 1 7 6 9 8 4 50 6 8 2 1 7 2 7 2 7 3 2 4 5 6 86 5 3 1 8 6 0 1 7 9 9 8 8 3 5 02 3 3 3 2 7 0 5 4 6 7 1 3 5 1 10 4 4 1 0 5 4 0 4 4 8 4 9 4 7 39 2 7 2 9 9 7 6 7 6 7 0 1 8 4 23 8 5 3 5 9 5 2 5 4 8 7 0 5 0 17 9 3 9 1 2 5 8 8 2 1 2 2 5 6 55 1 1 1 0 6 5 6 2 3 3 2 1 5 4 85 9 9 6 2 4 4 2 8 7 4 1 2 0 8 83 9 1 4 8 6 2 0 1 5 5 2 0 9 3 70 2 3 2 7 0 7 7 7 1 8 0 4 7 0 78 3 3 6 1 5 9 2 2 4 5 5 5 8 2 72 6 2 1 8 9 9 5 0 7 7 6 6 9 4 5`
AC output: 123
brianfry713
Guru

Posts: 1771
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 929 - Number Maze

cuttttt
Last edited by mahade hasan on Fri Nov 16, 2012 9:07 am, edited 1 time in total.
we r surrounded by happiness
need eyes to feel it!

Learning poster

Posts: 63
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 929 - Number Maze

brianfry713
Guru

Posts: 1771
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 929 - Number Maze

getting Wa.....
but i can't figure but where my logic doesn't work..........

Code: Select all
`#include<stdio.h>#include<iostream>#include<queue>#include<vector>using namespace std;int Mat[1004][1004],Value[1004][1004];struct data {    int city, dist,city2;    bool operator < ( const data& p ) const {        return dist > p.dist;    }};int main(){   int I,K,L,M,N,Case=0,R,C;      scanf("%d",&Case);   while(Case--)   {        scanf("%d %d",&R,&C);      for(I=1;I<=R;I++)      for(K=1;K<=C;K++)      {            scanf("%d",&Mat[I][K]);            Value[I][K]=10000;      }      data A, B;      A.city=1,A.dist=Mat[1][1],A.city2=1;      Value[1][1]=Mat[1][1];      priority_queue<data>Q;      Q.push(A);            while(!Q.empty())      {         A=Q.top();         Q.pop();         //if(A.city==R&&A.city2==C) break;                  if(A.city-1>0&&Value[A.city-1][A.city2]>Mat[A.city-1][A.city2]+A.dist)         {            B.city=A.city-1,B.city2=A.city2;            Value[A.city-1][A.city2]=Mat[A.city-1][A.city2]+A.dist;            B.dist=Value[A.city-1][A.city2];            Q.push(B);            //if(B.city==R&&B.city2==C) break;         }         if(A.city+1<=R&&Value[A.city+1][A.city2]>Mat[A.city+1][A.city2]+A.dist)         {            B.city=A.city+1,B.city2=A.city2;            Value[A.city+1][A.city2]=Mat[A.city+1][A.city2]+A.dist;            B.dist=Value[A.city+1][A.city2];            Q.push(B);            //if(B.city==R&&B.city2==C) break;         }                  if(A.city2-1>0&&Value[A.city][A.city2-1]>Mat[A.city][A.city2-1]+A.dist)         {            B.city=A.city,B.city2=A.city2-1;            Value[A.city][A.city2-1]=Mat[A.city][A.city2-1]+A.dist;            B.dist=Value[A.city][A.city2-1];            Q.push(B);            //if(B.city==R&&B.city2==C) break;         }         if(A.city2+1<=C&&Value[A.city][A.city2+1]>Mat[A.city][A.city2+1]+A.dist)         {            B.city=A.city,B.city2=A.city2+1;            Value[A.city][A.city2+1]=Mat[A.city][A.city2+1]+A.dist;            B.dist=Value[A.city][A.city2+1];            Q.push(B);            //if(B.city==R&&B.city2==C) break;         }      }               printf("%d\n",Value[R][C]);   }   return 0;}`

we r surrounded by happiness
need eyes to feel it!

Learning poster

Posts: 63
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 929 - Number Maze

brianfry713 wrote:Input:
Code: Select all
`133164 6 9 7 6 0 3 4 6 0 8 5 1 2 1 89 6 0 3 8 7 1 3 3 4 1 2 9 5 5 34 4 3 0 6 6 6 2 9 6 7 2 1 0 1 06 1 3 6 0 4 9 5 1 3 7 0 8 2 5 48 8 6 4 7 4 6 6 1 5 8 2 5 1 2 34 7 0 4 2 1 9 5 4 8 5 5 2 0 9 29 8 6 6 2 4 4 5 1 4 9 8 6 3 2 01 4 7 5 5 8 0 0 7 5 5 1 7 6 4 84 2 6 9 7 0 4 0 5 4 9 3 7 3 3 09 2 5 6 1 5 8 0 2 3 1 0 2 5 0 68 7 7 7 9 2 9 6 8 0 9 7 3 5 8 47 3 1 0 1 9 0 3 5 2 5 7 9 8 5 95 3 8 6 7 8 3 5 8 2 2 4 9 2 8 76 1 9 9 1 0 2 8 4 0 7 5 8 2 5 57 3 1 4 3 4 1 4 9 4 0 8 8 8 7 42 7 5 5 9 0 3 3 0 0 8 0 4 5 5 21 8 8 6 5 0 0 6 6 0 6 4 1 4 1 33 6 8 2 6 3 7 8 3 7 8 7 3 5 1 66 0 2 1 2 3 7 8 5 3 4 6 9 5 1 24 9 6 2 4 3 1 7 3 1 7 6 9 8 4 50 6 8 2 1 7 2 7 2 7 3 2 4 5 6 86 5 3 1 8 6 0 1 7 9 9 8 8 3 5 02 3 3 3 2 7 0 5 4 6 7 1 3 5 1 10 4 4 1 0 5 4 0 4 4 8 4 9 4 7 39 2 7 2 9 9 7 6 7 6 7 0 1 8 4 23 8 5 3 5 9 5 2 5 4 8 7 0 5 0 17 9 3 9 1 2 5 8 8 2 1 2 2 5 6 55 1 1 1 0 6 5 6 2 3 3 2 1 5 4 85 9 9 6 2 4 4 2 8 7 4 1 2 0 8 83 9 1 4 8 6 2 0 1 5 5 2 0 9 3 70 2 3 2 7 0 7 7 7 1 8 0 4 7 0 78 3 3 6 1 5 9 2 2 4 5 5 5 8 2 72 6 2 1 8 9 9 5 0 7 7 6 6 9 4 5`
AC output: 123
brianfry713
Guru

Posts: 1771
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 929 - Number Maze

brianfry713 wrote:
brianfry713 wrote:Input:
Code: Select all
`133164 6 9 7 6 0 3 4 6 0 8 5 1 2 1 89 6 0 3 8 7 1 3 3 4 1 2 9 5 5 34 4 3 0 6 6 6 2 9 6 7 2 1 0 1 06 1 3 6 0 4 9 5 1 3 7 0 8 2 5 48 8 6 4 7 4 6 6 1 5 8 2 5 1 2 34 7 0 4 2 1 9 5 4 8 5 5 2 0 9 29 8 6 6 2 4 4 5 1 4 9 8 6 3 2 01 4 7 5 5 8 0 0 7 5 5 1 7 6 4 84 2 6 9 7 0 4 0 5 4 9 3 7 3 3 09 2 5 6 1 5 8 0 2 3 1 0 2 5 0 68 7 7 7 9 2 9 6 8 0 9 7 3 5 8 47 3 1 0 1 9 0 3 5 2 5 7 9 8 5 95 3 8 6 7 8 3 5 8 2 2 4 9 2 8 76 1 9 9 1 0 2 8 4 0 7 5 8 2 5 57 3 1 4 3 4 1 4 9 4 0 8 8 8 7 42 7 5 5 9 0 3 3 0 0 8 0 4 5 5 21 8 8 6 5 0 0 6 6 0 6 4 1 4 1 33 6 8 2 6 3 7 8 3 7 8 7 3 5 1 66 0 2 1 2 3 7 8 5 3 4 6 9 5 1 24 9 6 2 4 3 1 7 3 1 7 6 9 8 4 50 6 8 2 1 7 2 7 2 7 3 2 4 5 6 86 5 3 1 8 6 0 1 7 9 9 8 8 3 5 02 3 3 3 2 7 0 5 4 6 7 1 3 5 1 10 4 4 1 0 5 4 0 4 4 8 4 9 4 7 39 2 7 2 9 9 7 6 7 6 7 0 1 8 4 23 8 5 3 5 9 5 2 5 4 8 7 0 5 0 17 9 3 9 1 2 5 8 8 2 1 2 2 5 6 55 1 1 1 0 6 5 6 2 3 3 2 1 5 4 85 9 9 6 2 4 4 2 8 7 4 1 2 0 8 83 9 1 4 8 6 2 0 1 5 5 2 0 9 3 70 2 3 2 7 0 7 7 7 1 8 0 4 7 0 78 3 3 6 1 5 9 2 2 4 5 5 5 8 2 72 6 2 1 8 9 9 5 0 7 7 6 6 9 4 5`
AC output: 123

i knew that !!!
but Don't know where my logic doesn't work????
we r surrounded by happiness
need eyes to feel it!