868 - Numerical Maze

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Phocasia
New poster
Posts: 4
Joined: Fri May 11, 2007 3:50 pm

Help!

Post by Phocasia » Sat Apr 19, 2008 7:55 am

Code: Select all

1

4 3
1 1 2
1 2 1
2 1 2
1 2 3
What should be print for this test case?

I think it should be

Code: Select all

1 1
4 3
because it follow the rule 1,1,2,1,2,3.

Am I correct?

Phocasia
New poster
Posts: 4
Joined: Fri May 11, 2007 3:50 pm

Re: 868 - Numerical Maze

Post by Phocasia » Sat Apr 19, 2008 10:54 am

I try to solve this problem many times and now I got AC.

First, I print output by this code.

Code: Select all

printf("1 %d\n%d %d\n\n" ,start ,row ,end);
I got WA.

I got AC when I change code to

Code: Select all

printf("1 %d\n%d %d\n" ,start ,row ,end);
if(set--)
        printf("\n");
I think that the last output don't have two newline.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 868 - Numerical Maze

Post by DD » Sun Nov 09, 2008 6:15 pm

Phocasia wrote:

Code: Select all

1

4 3
1 1 2
1 2 1
2 1 2
1 2 3
What should be print for this test case?

I think it should be

Code: Select all

1 1
4 3
because it follow the rule 1,1,2,1,2,3.

Am I correct?
My A.C code generates the following output:

Code: Select all

1 1
4 1
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

yokola95
New poster
Posts: 1
Joined: Sat Dec 01, 2012 10:30 pm

Re: 868 - Numerical Maze

Post by yokola95 » Sat Dec 01, 2012 10:37 pm

I've made a code that solves the sample input (and the inputs written in this topic). Still I'm getting WA. Since the description of the problem is very bad, I can't understand where the problem is.

1. Can i turn back to the cell that I've already visited (I supposed NO).
2. Once i reach the last row, the cell must contain the end of a subsquence (I supposed NO, but tried even considering this).
3. Once i reach the last row, can I move more to the left (or generally still move) if possible (to get a minor end or to complete a subsequence), or I must stop immediately?

I've tried all but still WA.
Thank you

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

Re: 868 - Numerical Maze

Post by brianfry713 » Sat Dec 08, 2012 5:33 pm

My AC code assumes:
A path can not revisit a cell.
I only consider complete subsequences.
I continue the DFS after I reach the last row, and store the minimum column on the last row that is the end of a subsequence.
Check input and AC output for thousands of problems on uDebug!

tiendaotd
New poster
Posts: 12
Joined: Mon Jan 14, 2013 12:21 pm

Re: 868 - Numerical Maze

Post by tiendaotd » Tue Feb 19, 2013 12:26 pm

I got AC in first submission and I don't even consider if a cell can be visited more than once or not, I just check only for the complete path. The path must be :

Code: Select all

1,
1, 2,
1,2,...,k
1,2,...k+1
For the case :

Code: Select all

6 6
1 1 2 1 2 3
2 1 4 3 2 1
3 4 5 1 2 3
3 2 1 6 5 4
4 5 6 7 1 2
9 9 9 9 9 3
I printed "NOT FOUND" as the last sequence is not completed.

I also suppose n,m <= 100 . Hope it helps.

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 868 - Numerical Maze

Post by metaphysis » Tue Nov 14, 2017 4:58 pm

It seems that the judge data is weak, there allways(may be) only one way to arrive last row with completed sequence.

Post Reply

Return to “Volume 8 (800-899)”