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

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

Re: 929 - Number Maze

Post by brianfry713 » Mon Apr 09, 2012 8:02 am

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.
Check input and AC output for thousands of problems on uDebug!

vpanait
New poster
Posts: 17
Joined: Sun Apr 01, 2012 11:01 am

Re: 929 - Number Maze

Post by vpanait » Tue Jul 17, 2012 4:55 pm

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.

Two advises:
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.

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

Re: 929 - Number Maze

Post by pranon » Tue Jul 31, 2012 9:37 am

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.
Thanks in advance.

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

Re: 929 - Number Maze

Post by brianfry713 » Wed Aug 01, 2012 10:22 pm

Input:

Code: Select all

1
33
16
4 6 9 7 6 0 3 4 6 0 8 5 1 2 1 8
9 6 0 3 8 7 1 3 3 4 1 2 9 5 5 3
4 4 3 0 6 6 6 2 9 6 7 2 1 0 1 0
6 1 3 6 0 4 9 5 1 3 7 0 8 2 5 4
8 8 6 4 7 4 6 6 1 5 8 2 5 1 2 3
4 7 0 4 2 1 9 5 4 8 5 5 2 0 9 2
9 8 6 6 2 4 4 5 1 4 9 8 6 3 2 0
1 4 7 5 5 8 0 0 7 5 5 1 7 6 4 8
4 2 6 9 7 0 4 0 5 4 9 3 7 3 3 0
9 2 5 6 1 5 8 0 2 3 1 0 2 5 0 6
8 7 7 7 9 2 9 6 8 0 9 7 3 5 8 4
7 3 1 0 1 9 0 3 5 2 5 7 9 8 5 9
5 3 8 6 7 8 3 5 8 2 2 4 9 2 8 7
6 1 9 9 1 0 2 8 4 0 7 5 8 2 5 5
7 3 1 4 3 4 1 4 9 4 0 8 8 8 7 4
2 7 5 5 9 0 3 3 0 0 8 0 4 5 5 2
1 8 8 6 5 0 0 6 6 0 6 4 1 4 1 3
3 6 8 2 6 3 7 8 3 7 8 7 3 5 1 6
6 0 2 1 2 3 7 8 5 3 4 6 9 5 1 2
4 9 6 2 4 3 1 7 3 1 7 6 9 8 4 5
0 6 8 2 1 7 2 7 2 7 3 2 4 5 6 8
6 5 3 1 8 6 0 1 7 9 9 8 8 3 5 0
2 3 3 3 2 7 0 5 4 6 7 1 3 5 1 1
0 4 4 1 0 5 4 0 4 4 8 4 9 4 7 3
9 2 7 2 9 9 7 6 7 6 7 0 1 8 4 2
3 8 5 3 5 9 5 2 5 4 8 7 0 5 0 1
7 9 3 9 1 2 5 8 8 2 1 2 2 5 6 5
5 1 1 1 0 6 5 6 2 3 3 2 1 5 4 8
5 9 9 6 2 4 4 2 8 7 4 1 2 0 8 8
3 9 1 4 8 6 2 0 1 5 5 2 0 9 3 7
0 2 3 2 7 0 7 7 7 1 8 0 4 7 0 7
8 3 3 6 1 5 9 2 2 4 5 5 5 8 2 7
2 6 2 1 8 9 9 5 0 7 7 6 6 9 4 5
AC output: 119
Last edited by brianfry713 on Tue Jun 11, 2013 3:02 am, edited 1 time in total.
Check input and AC output for thousands of problems on uDebug!

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 929 - Number Maze

Post by mahade hasan » Sun Sep 16, 2012 6:39 pm

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!

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

Re: 929 - Number Maze

Post by brianfry713 » Tue Sep 18, 2012 9:28 pm

Read this thread.
Check input and AC output for thousands of problems on uDebug!

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 929 - Number Maze

Post by mahade hasan » Fri Nov 16, 2012 9:06 am

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;
}

[/color]
we r surrounded by happiness
need eyes to feel it!

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

Re: 929 - Number Maze

Post by brianfry713 » Sat Nov 17, 2012 4:19 am

deleted post
Last edited by brianfry713 on Tue Jun 11, 2013 3:03 am, edited 1 time in total.
Check input and AC output for thousands of problems on uDebug!

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 929 - Number Maze

Post by mahade hasan » Fri Nov 30, 2012 8:54 pm

brianfry713 wrote:
brianfry713 wrote:Input:

Code: Select all

1
33
16
4 6 9 7 6 0 3 4 6 0 8 5 1 2 1 8
9 6 0 3 8 7 1 3 3 4 1 2 9 5 5 3
4 4 3 0 6 6 6 2 9 6 7 2 1 0 1 0
6 1 3 6 0 4 9 5 1 3 7 0 8 2 5 4
8 8 6 4 7 4 6 6 1 5 8 2 5 1 2 3
4 7 0 4 2 1 9 5 4 8 5 5 2 0 9 2
9 8 6 6 2 4 4 5 1 4 9 8 6 3 2 0
1 4 7 5 5 8 0 0 7 5 5 1 7 6 4 8
4 2 6 9 7 0 4 0 5 4 9 3 7 3 3 0
9 2 5 6 1 5 8 0 2 3 1 0 2 5 0 6
8 7 7 7 9 2 9 6 8 0 9 7 3 5 8 4
7 3 1 0 1 9 0 3 5 2 5 7 9 8 5 9
5 3 8 6 7 8 3 5 8 2 2 4 9 2 8 7
6 1 9 9 1 0 2 8 4 0 7 5 8 2 5 5
7 3 1 4 3 4 1 4 9 4 0 8 8 8 7 4
2 7 5 5 9 0 3 3 0 0 8 0 4 5 5 2
1 8 8 6 5 0 0 6 6 0 6 4 1 4 1 3
3 6 8 2 6 3 7 8 3 7 8 7 3 5 1 6
6 0 2 1 2 3 7 8 5 3 4 6 9 5 1 2
4 9 6 2 4 3 1 7 3 1 7 6 9 8 4 5
0 6 8 2 1 7 2 7 2 7 3 2 4 5 6 8
6 5 3 1 8 6 0 1 7 9 9 8 8 3 5 0
2 3 3 3 2 7 0 5 4 6 7 1 3 5 1 1
0 4 4 1 0 5 4 0 4 4 8 4 9 4 7 3
9 2 7 2 9 9 7 6 7 6 7 0 1 8 4 2
3 8 5 3 5 9 5 2 5 4 8 7 0 5 0 1
7 9 3 9 1 2 5 8 8 2 1 2 2 5 6 5
5 1 1 1 0 6 5 6 2 3 3 2 1 5 4 8
5 9 9 6 2 4 4 2 8 7 4 1 2 0 8 8
3 9 1 4 8 6 2 0 1 5 5 2 0 9 3 7
0 2 3 2 7 0 7 7 7 1 8 0 4 7 0 7
8 3 3 6 1 5 9 2 2 4 5 5 5 8 2 7
2 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!

bazocc4
New poster
Posts: 4
Joined: Fri May 31, 2013 5:57 am

Re: 929 - Number Maze

Post by bazocc4 » Fri May 31, 2013 6:03 am

Excuse me, judge.. I just want to ask, is there any problem in judging answer in 929 Number Maze problem?
because all of my submission is always got "Submission Error", each time i submit answer, regardless what kind of answer i submited.

Thanks in advance =D

bazocc4
New poster
Posts: 4
Joined: Fri May 31, 2013 5:57 am

Re: 929 - Number Maze

Post by bazocc4 » Fri May 31, 2013 11:37 am

mahade hasan wrote:
brianfry713 wrote:
brianfry713 wrote:Input:

Code: Select all

1
33
16
4 6 9 7 6 0 3 4 6 0 8 5 1 2 1 8
9 6 0 3 8 7 1 3 3 4 1 2 9 5 5 3
4 4 3 0 6 6 6 2 9 6 7 2 1 0 1 0
6 1 3 6 0 4 9 5 1 3 7 0 8 2 5 4
8 8 6 4 7 4 6 6 1 5 8 2 5 1 2 3
4 7 0 4 2 1 9 5 4 8 5 5 2 0 9 2
9 8 6 6 2 4 4 5 1 4 9 8 6 3 2 0
1 4 7 5 5 8 0 0 7 5 5 1 7 6 4 8
4 2 6 9 7 0 4 0 5 4 9 3 7 3 3 0
9 2 5 6 1 5 8 0 2 3 1 0 2 5 0 6
8 7 7 7 9 2 9 6 8 0 9 7 3 5 8 4
7 3 1 0 1 9 0 3 5 2 5 7 9 8 5 9
5 3 8 6 7 8 3 5 8 2 2 4 9 2 8 7
6 1 9 9 1 0 2 8 4 0 7 5 8 2 5 5
7 3 1 4 3 4 1 4 9 4 0 8 8 8 7 4
2 7 5 5 9 0 3 3 0 0 8 0 4 5 5 2
1 8 8 6 5 0 0 6 6 0 6 4 1 4 1 3
3 6 8 2 6 3 7 8 3 7 8 7 3 5 1 6
6 0 2 1 2 3 7 8 5 3 4 6 9 5 1 2
4 9 6 2 4 3 1 7 3 1 7 6 9 8 4 5
0 6 8 2 1 7 2 7 2 7 3 2 4 5 6 8
6 5 3 1 8 6 0 1 7 9 9 8 8 3 5 0
2 3 3 3 2 7 0 5 4 6 7 1 3 5 1 1
0 4 4 1 0 5 4 0 4 4 8 4 9 4 7 3
9 2 7 2 9 9 7 6 7 6 7 0 1 8 4 2
3 8 5 3 5 9 5 2 5 4 8 7 0 5 0 1
7 9 3 9 1 2 5 8 8 2 1 2 2 5 6 5
5 1 1 1 0 6 5 6 2 3 3 2 1 5 4 8
5 9 9 6 2 4 4 2 8 7 4 1 2 0 8 8
3 9 1 4 8 6 2 0 1 5 5 2 0 9 3 7
0 2 3 2 7 0 7 7 7 1 8 0 4 7 0 7
8 3 3 6 1 5 9 2 2 4 5 5 5 8 2 7
2 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????
>> i think the correct answer is 119, not 123 isn't it ?

Zerch
New poster
Posts: 2
Joined: Sun Jun 09, 2013 8:53 pm

Re: 929 - Number Maze

Post by Zerch » Sun Jun 09, 2013 8:59 pm

is there a problem with this excersice? 929 - Number Maze ... I only get submition error... plz... help me

Zerch
New poster
Posts: 2
Joined: Sun Jun 09, 2013 8:53 pm

Re: 929 - Number Maze

Post by Zerch » Sun Jun 09, 2013 9:03 pm

brianfry713 wrote:
brianfry713 wrote:Input:

Code: Select all

1
33
16
4 6 9 7 6 0 3 4 6 0 8 5 1 2 1 8
9 6 0 3 8 7 1 3 3 4 1 2 9 5 5 3
4 4 3 0 6 6 6 2 9 6 7 2 1 0 1 0
6 1 3 6 0 4 9 5 1 3 7 0 8 2 5 4
8 8 6 4 7 4 6 6 1 5 8 2 5 1 2 3
4 7 0 4 2 1 9 5 4 8 5 5 2 0 9 2
9 8 6 6 2 4 4 5 1 4 9 8 6 3 2 0
1 4 7 5 5 8 0 0 7 5 5 1 7 6 4 8
4 2 6 9 7 0 4 0 5 4 9 3 7 3 3 0
9 2 5 6 1 5 8 0 2 3 1 0 2 5 0 6
8 7 7 7 9 2 9 6 8 0 9 7 3 5 8 4
7 3 1 0 1 9 0 3 5 2 5 7 9 8 5 9
5 3 8 6 7 8 3 5 8 2 2 4 9 2 8 7
6 1 9 9 1 0 2 8 4 0 7 5 8 2 5 5
7 3 1 4 3 4 1 4 9 4 0 8 8 8 7 4
2 7 5 5 9 0 3 3 0 0 8 0 4 5 5 2
1 8 8 6 5 0 0 6 6 0 6 4 1 4 1 3
3 6 8 2 6 3 7 8 3 7 8 7 3 5 1 6
6 0 2 1 2 3 7 8 5 3 4 6 9 5 1 2
4 9 6 2 4 3 1 7 3 1 7 6 9 8 4 5
0 6 8 2 1 7 2 7 2 7 3 2 4 5 6 8
6 5 3 1 8 6 0 1 7 9 9 8 8 3 5 0
2 3 3 3 2 7 0 5 4 6 7 1 3 5 1 1
0 4 4 1 0 5 4 0 4 4 8 4 9 4 7 3
9 2 7 2 9 9 7 6 7 6 7 0 1 8 4 2
3 8 5 3 5 9 5 2 5 4 8 7 0 5 0 1
7 9 3 9 1 2 5 8 8 2 1 2 2 5 6 5
5 1 1 1 0 6 5 6 2 3 3 2 1 5 4 8
5 9 9 6 2 4 4 2 8 7 4 1 2 0 8 8
3 9 1 4 8 6 2 0 1 5 5 2 0 9 3 7
0 2 3 2 7 0 7 7 7 1 8 0 4 7 0 7
8 3 3 6 1 5 9 2 2 4 5 5 5 8 2 7
2 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????
>> i think the correct answer is 119, not 123 isn't it ?
i think that too. isn't 119?

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

Re: 929 - Number Maze

Post by brianfry713 » Tue Jun 11, 2013 3:04 am

You are correct, the output for that input should be 119, I edited my previous posts.

Try a different problem until the submission error issue is resolved.
Check input and AC output for thousands of problems on uDebug!

Faithkeeper_Rangwan
New poster
Posts: 12
Joined: Sun Jul 07, 2013 7:32 pm

Re: 929 - Number Maze

Post by Faithkeeper_Rangwan » Thu Aug 01, 2013 3:47 pm

Zerch wrote:is there a problem with this excersice? 929 - Number Maze ... I only get submition error... plz... help me
Very likely, I saw more than 50 recent submissions (including mine) got (consecutively) SEs.

Post Reply

Return to “Volume 9 (900-999)”