168 - Theseus and the Minotaur

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

Moderator: Board moderators

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

168 Now ACed,ignore it

Post by pineapple »

I have read many threads about this problem.But I still can't get Accepted.
Who can help me?Please give me some cases I can't handle or point out my mistake.Thanks very much.

The following is my code:

Code: Select all

Accepted!
Last edited by pineapple on Wed May 02, 2007 2:57 am, edited 2 times in total.
rickyliu
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

Post by rickyliu »

Try this:

Code: Select all

A:DBC. A B 20
#
Your answer is:

Code: Select all

/C
The correct answer should be:

Code: Select all

/D
pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

Post by pineapple »

Thank you very much!
Your test case is very helpful to me.
I changed my code a little and get AC!
then I will delete my code above.
Thanks again.
shamsacm
New poster
Posts: 6
Joined: Sat May 07, 2011 12:45 pm

Re: 168 Now ACed,ignore it

Post by shamsacm »

Try This
Input

Code: Select all

A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 3
A:BCD;B:ACD;C:ABD;D:ABCG;G:DEFH;E:GFH;F:GEH;H:EFG. A C 1
A:BCD;B:ACD;C:ABD;D:ABCG;G:DEFH;E:GFH;F:GEH;H:EFG. A C 6
A:BCD;B:ACD;C:ABD;D:ABCG;G:DEFH;E:GFH;F:GEH;H:EFG. A C 7
A:B;B:A. B A 3
A:B;B:C;C:A. B A 6
C:A;A:B. A C 999999999
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 3
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1
A:DBC. A B 20
A:DBC. A B 1
A:BC:A A B 1
#
Output:

Code: Select all

D F G /E
A B C D G E F /H
C D /B
A B D /C
/B
A /C
/B
D F G /E
A B D G E F /H
/D
A /D
/A
vo_minhdat2007
New poster
Posts: 5
Joined: Mon Apr 09, 2012 7:11 am

Re:

Post by vo_minhdat2007 »

rickyliu wrote:Try this:

Code: Select all

A:DBC. A B 20
#
Your answer is:

Code: Select all

/C
The correct answer should be:

Code: Select all

/D
Hello, please explains why the answer is /D? If I understand the problem correctly, the graph should be like this:

Image

And
where in this case the Minotaur checks the exits from a cavern in alphabetical order
So Minotaur should go to C (because C < D) and be trapped there immediately?
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 168 Now ACed,ignore it

Post by brianfry713 »

Read the problem description again. It was alphabetical just for the sample case. "The description of a labyrinth will identify each cavern by an upper case character and will list the caverns reachable from that cavern in the order that the Minotaur will attempt them"

In the input

Code: Select all

A:DBC. A B 20
#
The Minotaur will attempt to go from A first to D, then B, then C.
Check input and AC output for thousands of problems on uDebug!
vo_minhdat2007
New poster
Posts: 5
Joined: Mon Apr 09, 2012 7:11 am

Re: 168 Now ACed,ignore it

Post by vo_minhdat2007 »

brianfry713 wrote:Read the problem description again. It was alphabetical just for the sample case. "The description of a labyrinth will identify each cavern by an upper case character and will list the caverns reachable from that cavern in the order that the Minotaur will attempt them"

In the input

Code: Select all

A:DBC. A B 20
#
The Minotaur will attempt to go from A first to D, then B, then C.
Thank you, I got it!
vo_minhdat2007
New poster
Posts: 5
Joined: Mon Apr 09, 2012 7:11 am

168 - Theseus and the Minotaur TLE

Post by vo_minhdat2007 »

I wonder which test case that cause the TLE. Here is my code, please give me some big case and I will try to improve it.

(My program return results correctly for problems at this topic: http://online-judge.uva.es/board/viewto ... =1&t=14236)

Code: Select all

import java.util.ArrayList;
import java.util.Scanner;


public class Main {

	//===============================================//
	// Inner Classes
	//===============================================//
	
	public class ArrayListInteger {
		public ArrayList<Integer> value = new ArrayList<Integer>();
	}
	
	//===============================================//
	// Variables
	//===============================================//
	
	private static ArrayListInteger[] mAdjacentVertexes;
	private static boolean[] mVertexDisabled;
	private static int mFinalVertex = 0;
	private static int mThesusVertex = 0;
	private static int mMinotaurVertex = 0;
	private static int mK = 0;
	
	//===============================================//
	// Public Methods
	//===============================================//
	
	public static void parseInput(String pRawData) {
		String[] periodDelimiter = pRawData.split("\\.");
		
		String[] passages = periodDelimiter[0].split(";");
		for (int i = 0; i < passages.length; i++) {
			int startVertex = passages[i].charAt(0) - 'A';
			if (startVertex > mFinalVertex) mFinalVertex = startVertex;
			
			for (int j = 2; j < passages[i].length(); j++) {
				int endVertex = passages[i].charAt(j) - 'A';
				if (endVertex > mFinalVertex) mFinalVertex = endVertex;
				
				mAdjacentVertexes[startVertex].value.add(endVertex);
			}
		}
		mFinalVertex++;
		
		String initData[] = periodDelimiter[1].trim().split(" ");
		mMinotaurVertex = initData[0].charAt(0) - 'A';
		mThesusVertex = initData[1].charAt(0) - 'A';
		mK = Integer.parseInt(initData[2]);
	}

	public static String traverse() {
		String result = "";
		
		int mTravelCount = 0;
		int nextVertex = -1;
		do {
			nextVertex = -1;
			
			for (int i = 0; i < mAdjacentVertexes[mMinotaurVertex].value.size(); i++) {
				int currentVertex = mAdjacentVertexes[mMinotaurVertex].value.get(i);
				if (mVertexDisabled[currentVertex] || currentVertex == mThesusVertex) continue;
				nextVertex = currentVertex;
				break;
			}
			
			if (nextVertex != -1) {
				mTravelCount++;
				if (mAdjacentVertexes[mThesusVertex].value.indexOf(mMinotaurVertex) != -1)
					mThesusVertex = mMinotaurVertex;
				mMinotaurVertex = nextVertex;
				
				if (mTravelCount == mK) {
					// Print result
					result += (char)(mThesusVertex + 'A') + " ";
					
					// Clear this vertex
					mVertexDisabled[mThesusVertex] = true;
					
					mTravelCount = 0;
				}
			}
		} while (nextVertex != -1);
		result += "/" + (char)(mMinotaurVertex + 'A');
		
		return result;
	}
	
	public static void main(String[] args) {
		String result = "";
		Scanner scanner = new Scanner(System.in);
		
		// Initialize
		mAdjacentVertexes = new ArrayListInteger[26];
		Main obj = new Main();
		for (int i = 0; i < 26; i++) {
			mAdjacentVertexes[i] = obj.new ArrayListInteger();
		}
		mVertexDisabled = new boolean[26];
		
		String currentInput = scanner.nextLine();
		while (!currentInput.equals("#")) {
			
			// Reset value
			for (int i = 0; i < 26; i++) {
				mAdjacentVertexes[i].value.clear();
				mVertexDisabled[i] = false;
			}
			mFinalVertex = 0;
			
			// Input
			parseInput(currentInput);
			
			// Traverse
			result += traverse() + "\n";
			
			// Next line
			currentInput = scanner.nextLine();
		}
		
		System.out.print(result);
	}
	
}
Thank you.
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 168 - Theseus and the Minotaur TLE

Post by brianfry713 »

Input:

Code: Select all

B:A;A:B. A C 999999999
#
AC output:

Code: Select all

/B
Check input and AC output for thousands of problems on uDebug!
vo_minhdat2007
New poster
Posts: 5
Joined: Mon Apr 09, 2012 7:11 am

Re: 168 - Theseus and the Minotaur TLE

Post by vo_minhdat2007 »

Thank you brianfry713,

Maybe I'm having too much misunderstanding about this problem. In that test case,
If a cavern has no exit it may or may not be in the input.
So C doesn't have any connection with A and B, so Theseus cannot chase the Minotaur? Then if I try comment out this line:

Code: Select all

if (mAdjacentVertexes[mThesusVertex].value.indexOf(mMinotaurVertex) != -1)
So Theseus can freely chase after Minotaur, the program works well with that test case, but I still get another TLE.
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 168 - Theseus and the Minotaur TLE

Post by brianfry713 »

Yeah that test case I posted is probably invalid but the line you commented out is not needed to get AC and will slow down your code.
I optimized your code and got AC in 1.392 sec. JAVA is always going to be slow, so make sure you are coding efficiently and sometimes you should try C/C++ instead. Use BufferedReader and BufferedWriter for I/O. mFinalVertex is not needed so get rid of it. Building the entire output into a string is slower than printing it immediately onto a BufferedWriter.
Check input and AC output for thousands of problems on uDebug!
Sawon90
New poster
Posts: 11
Joined: Wed Nov 23, 2011 1:28 am

Re: 168 Now ACed,ignore it

Post by Sawon90 »

For every case above, my code gives correct output. But why I am getting wrong answer???? :( Please someone help me. Thanks in advance. Here is my code....

Code: Select all

#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
char st[250];
long i,n,ts,mt,k,vis[35],c,sz;
vector<long>vc[35],op;
bool fg;
int main()
{
	while(gets(st) && strcmp(st,"#"))
	{
		for(i=0;i<30;i++)
		{
			vc[i].clear();
			vis[i]=0;
		}
		for(i=0;st[i];i++)
		{
			if(st[i]>='A' && st[i]<='Z')
			{
				n=st[i]-65;
				i+=2;
				while(st[i]>='A' && st[i]<='Z')
				{
					vc[n].push_back(st[i]-65);
					i++;
				}
			}
			if(st[i]=='.')
			{
				mt=st[i+2]-65;
				ts=st[i+4]-65;
				k=st[i+6]-'0';
				break;
			}
		}
		c=0;
		while(1)
		{
			fg=0;
			sz=vc[mt].size();
			for(i=0;i<sz;i++)
			{
				n=vc[mt][i];
				if(vis[n] || n==ts)
					continue;
				else
				{
					c++;
					fg=1;
					ts=mt;
					mt=n;
					if(c==k)
					{
						op.push_back(ts);
						vis[ts]=1;
						c=0;
					}
					break;
				}
			}
			if(fg==0)
				break;
		}
		sz=op.size();
		for(i=0;i<sz;i++)
			printf("%c ",op[i]+65);
		printf("%c%c\n",47,mt+65);
		op.clear();
	}
	return 0;
}
Sawon90
New poster
Posts: 11
Joined: Wed Nov 23, 2011 1:28 am

Re: 168 Now ACed,ignore it

Post by Sawon90 »

Oh God, Please someone help me, Please someone tell me what will be the output of the following cases...

Code: Select all

A:BCD;B:AD;C:AD;D:B. A C 3
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG. A C 3
Please someone help me.
Sawon90
New poster
Posts: 11
Joined: Wed Nov 23, 2011 1:28 am

Re: 168 - Theseus and the Minotaur TLE

Post by Sawon90 »

Please help me to find why I am getting wrong answer in this problem. Here is my code....

Code: Select all

#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
char st[250];
long i,n,ts,mt,k,vis[35],c,sz;
vector<long>vc[35],op;
bool fg;
int main()
{
	while(gets(st) && strcmp(st,"#"))
	{
		for(i=0;i<30;i++)
		{
			vc[i].clear();
			vis[i]=0;
		}
		for(i=0;st[i];i++)
		{
			if(st[i]>='A' && st[i]<='Z')
			{
				n=st[i]-65;
				i+=2;
				while(st[i]>='A' && st[i]<='Z')
				{
					vc[n].push_back(st[i]-65);
					i++;
				}
			}
			if(st[i]=='.')
			{
				mt=st[i+2]-65;
				ts=st[i+4]-65;
				k=st[i+6]-'0';
				break;
			}
		}
		c=0;
		while(1)
		{
			fg=0;
			sz=vc[mt].size();
			for(i=0;i<sz;i++)
			{
				n=vc[mt][i];
				if(vis[n] || n==ts)
					continue;
				else
				{
					c++;
					fg=1;
					ts=mt;
					mt=n;
					if(c==k)
					{
						op.push_back(ts);
						vis[ts]=1;
						c=0;
					}
					break;
				}
			}
			if(fg==0)
				break;
		}
		sz=op.size();
		for(i=0;i<sz;i++)
			printf("%c ",op[i]+65);
		printf("%c%c\n",47,mt+65);
		op.clear();
	}
	return 0;
}
Please help me.. What will be the output for these case.....

Code: Select all

A:BCD;B:AD;C:AD;D:B. A C 3
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG. A C 3
Thanks in advance....
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 168 - Theseus and the Minotaur TLE

Post by brianfry713 »

Check input and AC output for thousands of problems on uDebug!
Post Reply

Return to “Volume 1 (100-199)”