Programming Forums > Application Development > Software Design and Algorithms

Sane · Jun 5th, 2008, 6:10 AM

Will it still work even if I give it a crazy room like:

XXXXXXXXXX
X........X
X.X..XXX.X
X.X.X.X..X
XXXXX.XX.X
X...X....X
X.X.XX.XXX
X.X..X...X
X.X....X.X
XXXXXXXXXX

Where that all counts as one room?

Ancient Dragon · Jun 5th, 2008, 6:54 AM

If that's all one room then my program needs more work.

mbd · Jun 5th, 2008, 2:44 PM

i am wondering who else is attempting the senior and advanced level problems. i just finished my solution to cards (my first attempt was way off proven by some new inputs i came up with). it might be useful to get some sample input from other people in case i am missing some boundary cases. anyone wanna trade inputs?

mbd · Jun 5th, 2008, 3:14 PM

(Toggle Plain Text)

1
1

(Toggle Plain Text)

2
12
23

(Toggle Plain Text)

2
1
2

(Toggle Plain Text)

2
12
21

i also have one that tests the maximum size

(Toggle Plain Text)

Jimbo · Jun 6th, 2008, 12:16 AM

Bleh, why can't you accept C# as a language? Now I need to install a Java IDE. Oh, what will my co-workers say when they find out...

Sane · Jun 6th, 2008, 6:10 AM

Well, like I said in the general information, you can use C#, I don't mind. The only difference is I won't be able to rank it. The reason is simple: I don't have C#.

You will have to rank your own solution according to the test files I send you. You will still be in the results and your source may still potentially appear in the analysis for others to learn from.

titaniumdecoy · Jun 7th, 2008, 12:09 AM

I have spent days trying to figure out how to solve the senior (escalator) problem to no avail. Is there an algorithm that you have to know to solve it, or is it something that can be reasoned out? The problem reminds me of Euler cycles but I don't recall those involving one-way paths between nodes.

anrchydrgn · Jun 7th, 2008, 1:11 AM

Sane, under what circumstances are you checking to see if the program runs in under 10 seconds (processor type, how you are timing) and are there any algorithm books you can recommend

Sane · Jun 7th, 2008, 9:44 AM

@titaniumdecoy:

You fell into my trap! You're right to think of Eulerian curcuits, but that will lead you to an overcomplicated (or incorrect) solution. A Eulerian curcuit would guarantee connectivity to and from every vertex, but that's overcomplicated. And a Eulerian curcuit must use every edge, yet some escalators may cause a curcuit to be impossible to construct, so that's incorrect.

There is a fancy algorithm that can solve senior in 3 lines that takes $O(|V|^3)$ time, but it's not necessary to know. I've thought of two other solutions, one that takes $O(|V||E|)$ time and one that takes $O(|E|)$ time. The last two are quite logical and don't require any special algorithms (they can be reasoned out).

The problem becomes simpler if you try to draw out the graph and solve it by hand. Don't think of the problem as trying to construct a set of edges. We only need to know if anything is not reachable. If you need a push, let me know.

There's also a $O(|V|^2|E|)$ solution, but it's silly and will probably time out on most of the last files.

@anrchydrgn:

I'm running on a 2 Ghz processor. I'm just timing by feel. So far working submissions either work in <2 seconds, or they work in 50 seconds. So as soon as I see it's not going to finish, I just stop it. If I see your submission is "correct", but it's just taking longer because you're using Java or something, then I'll let it slide. But if it's obviously incorrect in terms of time complexity, then it gets a time-limit exceeded.

The only book I can recommend is the one I've read. It is free online: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani.

@Clarification for everyone:

Just so everyone knows, escalators don't always necessarily only go up one floor. For example, an escalator can go from the 1st floor to the 5th floor. Otherwise the problem would be too easy. ;D

mbd · Jun 7th, 2008, 11:33 AM

Sane, my escalator solution is o(n^4) in floors and o(n^2) in escalators. It ran in way less than 10 seconds on my computer with a worst case set of data. Did you find it to take longer than that?

Jun 5th, 2008, 6:10 AM	#11
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,886 Rep Power: 5	Re: Sane's Monthly Algorithms Challenge #2 [06-08] Will it still work even if I give it a crazy room like: (Toggle Plain Text) XXXXXXXXXX X........X X.X..XXX.X X.X.X.X..X XXXXX.XX.X X...X....X X.X.XX.XXX X.X..X...X X.X....X.X XXXXXXXXXX XXXXXXXXXX X........X X.X..XXX.X X.X.X.X..X XXXXX.XX.X X...X....X X.X.XX.XXX X.X..X...X X.X....X.X XXXXXXXXXX Where that all counts as one room? __________________ Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Jun 5th, 2008, 6:54 AM	#12
Ancient Dragon PFO God In Training Join Date: Jun 2005 Location: near St Louis, MO. (USA) Posts: 549 Rep Power: 4	Re: Sane's Monthly Algorithms Challenge #2 [06-08] If that's all one room then my program needs more work. __________________ True Terror is to wake up one morning and discover that your high school class is running the country - Kurt Vonnegut Jr.

Jun 5th, 2008, 2:44 PM	#13
mbd Programmer Join Date: Nov 2007 Posts: 86 Rep Power: 1	Re: Sane's Monthly Algorithms Challenge #2 [06-08] i am wondering who else is attempting the senior and advanced level problems. i just finished my solution to cards (my first attempt was way off proven by some new inputs i came up with). it might be useful to get some sample input from other people in case i am missing some boundary cases. anyone wanna trade inputs?

Jun 5th, 2008, 3:14 PM	#14
mbd Programmer Join Date: Nov 2007 Posts: 86 Rep Power: 1	Re: Sane's Monthly Algorithms Challenge #2 [06-08] (Toggle Plain Text) 1 1 1 1 (Toggle Plain Text) 2 12 23 2 12 23 (Toggle Plain Text) 2 1 2 2 1 2 (Toggle Plain Text) 2 12 21 2 12 21 i also have one that tests the maximum size (Toggle Plain Text) 1000000 1 2 3 4 5 6 7 8 9 10 11 ... 999999 1000000 1000000 1 2 3 4 5 6 7 8 9 10 11 ... 999999 1000000

Jun 6th, 2008, 12:16 AM	#15
Jimbo Battle Programmer Join Date: Feb 2006 Location: Bellevue, WA, USA Posts: 763 Rep Power: 3	Re: Sane's Monthly Algorithms Challenge #2 [06-08] Bleh, why can't you accept C# as a language? Now I need to install a Java IDE. Oh, what will my co-workers say when they find out... __________________ <insert disclaimer here> <insert shameless plug for Visual Studio here>

Jun 6th, 2008, 6:10 AM	#16
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,886 Rep Power: 5	Re: Sane's Monthly Algorithms Challenge #2 [06-08] Well, like I said in the general information, you can use C#, I don't mind. The only difference is I won't be able to rank it. The reason is simple: I don't have C#. You will have to rank your own solution according to the test files I send you. You will still be in the results and your source may still potentially appear in the analysis for others to learn from. __________________ Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Jun 7th, 2008, 12:09 AM	#17
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 856 Rep Power: 3	Re: Sane's Monthly Algorithms Challenge #2 [06-08] I have spent days trying to figure out how to solve the senior (escalator) problem to no avail. Is there an algorithm that you have to know to solve it, or is it something that can be reasoned out? The problem reminds me of Euler cycles but I don't recall those involving one-way paths between nodes. Last edited by titaniumdecoy; Jun 7th, 2008 at 12:32 AM.

Jun 7th, 2008, 1:11 AM	#18
anrchydrgn Newbie Join Date: May 2008 Posts: 2 Rep Power: 0	Re: Sane's Monthly Algorithms Challenge #2 [06-08] Sane, under what circumstances are you checking to see if the program runs in under 10 seconds (processor type, how you are timing) and are there any algorithm books you can recommend

Jun 7th, 2008, 9:44 AM	#19
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,886 Rep Power: 5	Re: Sane's Monthly Algorithms Challenge #2 [06-08] @titaniumdecoy: You fell into my trap! You're right to think of Eulerian curcuits, but that will lead you to an overcomplicated (or incorrect) solution. A Eulerian curcuit would guarantee connectivity to and from every vertex, but that's overcomplicated. And a Eulerian curcuit must use every edge, yet some escalators may cause a curcuit to be impossible to construct, so that's incorrect. There is a fancy algorithm that can solve senior in 3 lines that takes $O(\|V\|^3)$ time, but it's not necessary to know. I've thought of two other solutions, one that takes $O(\|V\|\|E\|)$ time and one that takes $O(\|E\|)$ time. The last two are quite logical and don't require any special algorithms (they can be reasoned out). The problem becomes simpler if you try to draw out the graph and solve it by hand. Don't think of the problem as trying to construct a set of edges. We only need to know if anything is not reachable. If you need a push, let me know. There's also a $O(\|V\|^2\|E\|)$ solution, but it's silly and will probably time out on most of the last files. @anrchydrgn: I'm running on a 2 Ghz processor. I'm just timing by feel. So far working submissions either work in <2 seconds, or they work in 50 seconds. So as soon as I see it's not going to finish, I just stop it. If I see your submission is "correct", but it's just taking longer because you're using Java or something, then I'll let it slide. But if it's obviously incorrect in terms of time complexity, then it gets a time-limit exceeded. The only book I can recommend is the one I've read. It is free online: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. @Clarification for everyone: Just so everyone knows, escalators don't always necessarily only go up one floor. For example, an escalator can go from the 1st floor to the 5th floor. Otherwise the problem would be too easy. ;D __________________ Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data Last edited by Sane; Jun 7th, 2008 at 10:00 AM.

Jun 7th, 2008, 11:33 AM	#20
mbd Programmer Join Date: Nov 2007 Posts: 86 Rep Power: 1	Re: Sane's Monthly Algorithms Challenge #2 [06-08] Sane, my escalator solution is o(n^4) in floors and o(n^2) in escalators. It ran in way less than 10 seconds on my computer with a worst case set of data. Did you find it to take longer than that?

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Uman's WEEKEND CHALLENGE	uman	Coder's Corner Lounge	34	Aug 5th, 2008 9:25 PM
Sane's Monthly Algorithms Challenge #1 [05-08]	Sane	Software Design and Algorithms	31	May 21st, 2008 10:11 PM
Good reference/tutorial for game tree algorithms	Jessehk	Software Design and Algorithms	10	Apr 10th, 2007 11:32 AM
Challenge: How to make daily life better with programming?	tempest	Coder's Corner Lounge	53	Jun 17th, 2005 2:37 AM
Weekend Challenge	theduck	Community Announcements and Feedback	43	Jun 3rd, 2005 4:58 PM

Programming Forums > Application Development > Software Design and Algorithms

Sane's Monthly Algorithms Challenge #2 [06-08]