Programming Forums > Application Development > Software Design and Algorithms

Sane · Jun 7th, 2008, 12:18 PM

If I recall correctly, the solution you sent me was a double for loop. So it was $O(|V|^2)$ or $O(|E|)$ . Which is the best possible solution. The reason I kept |V| small, is because I wanted to keep the question open-ended to more solutions. Or are you talking about a new submission that I haven't seen yet?

By the way, here's a hint for your #3: Try feeding your solution a graph with two disjoint sets.

Jimbo · Jun 7th, 2008, 3:08 PM

Quote:

Originally Posted by Sane

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).

For the "fancy" $O(|V|^3)$ solution, does the fancy just apply to code elegance? Since there's at most $V^2$ edges, it seems like the $O(|E|)$ would win hands down.

I'm curious about the $O(|E|)$ one, since you need to at least verify that you've hit every vertex, wouldn't it at least be $O(|E|+|V|)$ ?

Sane · Jun 7th, 2008, 3:28 PM

Fancy in terms of elegance. Yes. Since it's literally 3 lines long.

I've been ignoring the +|V| part in the notation.

mbd's solution is truly $O(|V|^2)$ , but it's also not correct.

Jimbo · Jun 7th, 2008, 10:17 PM

So, just to fire up more controversy in this thread, here's my approximation of my solutions' time efficiency (note: I wasn't doing a whole lot of optimizing for space):

Beginner: $O(n + q)$
Junior: $O(w*h)$ (I think... I'm a little fuzzy on if I calculated it right)
Senior: $O(e + n)$
Advanced: $O(n)$

I will note that I didn't do very extensive testing (ironic, for being a tester), but I'm pretty sure I've covered almost all of the cases (assuming my implementation is bug-free, haha!

).

titaniumdecoy · Jun 7th, 2008, 11:24 PM

I have come up with what I believe is a working solution to the senior (escalator) problem. It is recursive and, as far as I can tell, runs in $O(E)$ time.

If you have solved the senior (escalator) problem, is your solution recursive?

EDIT: Thanks Jimbo, got here in time to change "junior" to "senior".
EDIT: Changed running time from O(E+V) to O(E)

Jimbo · Jun 7th, 2008, 11:29 PM

Quote:

Originally Posted by titaniumdecoy

I have come up with what I believe is a working solution to the junior (escalator) problem.

Escalator was senior; Junior was the room size

I solved everything with loops, for comparison, but really they can probably be written both ways. $O(|E|)$ plus an iteration over the vertices to verify is what I ended up with as well.

titaniumdecoy · Jun 7th, 2008, 11:41 PM

Does anyone have (a) large test case(s) for the senior (escalator) problem? It's a hassle to draw one out on paper and then figure out if it passes.

Jimbo · Jun 8th, 2008, 12:00 AM

Crap, I drew one out and found a case I'd forgot to cover. Back to the hacking board...

(Toggle Plain Text)

[edit:] expected: Bob's getting the pink slip. Explanation: if you draw it out, 3 goes to 4, which is part of a loop with 9 and 10

titaniumdecoy · Jun 8th, 2008, 12:02 AM

Mrh. Looks like my solution doesn't work... or does it? This is going to take time...

Sane · Jun 8th, 2008, 11:29 AM

Don't worry about being super-duper efficient if you're not completely sure that the logic is correct. The number of floors is quite small, so keep it simple! It's better to be a bit slower and have it perfect, than trying to nail the fastest possible solution and getting it wrong.

I'm happy to hear people talking out the harder problems this month. Instead of what happened last month. lol.

P.S. For the sake of those testing Senior, with the test file Jimbo posted, my solution says that Bob gets fired. But that changes as soon as I change the last line from (10 4) to (10 3).

Jun 7th, 2008, 12:18 PM	#21
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,888 Rep Power: 5	Re: Sane's Monthly Algorithms Challenge #2 [06-08] If I recall correctly, the solution you sent me was a double for loop. So it was $O(\|V\|^2)$ or $O(\|E\|)$ . Which is the best possible solution. The reason I kept \|V\| small, is because I wanted to keep the question open-ended to more solutions. Or are you talking about a new submission that I haven't seen yet? By the way, here's a hint for your #3: Try feeding your solution a graph with two disjoint sets. __________________ Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Jun 7th, 2008, 3:28 PM	#23
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,888 Rep Power: 5	Re: Sane's Monthly Algorithms Challenge #2 [06-08] Fancy in terms of elegance. Yes. Since it's literally 3 lines long. I've been ignoring the +\|V\| part in the notation. mbd's solution is truly $O(\|V\|^2)$ , but it's also not correct. __________________ Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data Last edited by Sane; Jun 7th, 2008 at 3:45 PM.

Jun 7th, 2008, 10:17 PM	#24
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] So, just to fire up more controversy in this thread, here's my approximation of my solutions' time efficiency (note: I wasn't doing a whole lot of optimizing for space): Beginner: $O(n + q)$ Junior: $O(w*h)$ (I think... I'm a little fuzzy on if I calculated it right) Senior: $O(e + n)$ Advanced: $O(n)$ I will note that I didn't do very extensive testing (ironic, for being a tester), but I'm pretty sure I've covered almost all of the cases (assuming my implementation is bug-free, haha! ). __________________ <insert disclaimer here> <insert shameless plug for Visual Studio here>

Jun 7th, 2008, 11:24 PM	#25
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 856 Rep Power: 3	Re: Sane's Monthly Algorithms Challenge #2 [06-08] I have come up with what I believe is a working solution to the senior (escalator) problem. It is recursive and, as far as I can tell, runs in $O(E)$ time. If you have solved the senior (escalator) problem, is your solution recursive? EDIT: Thanks Jimbo, got here in time to change "junior" to "senior". EDIT: Changed running time from O(E+V) to O(E) Last edited by titaniumdecoy; Jun 7th, 2008 at 11:51 PM.

Jun 7th, 2008, 11:41 PM	#27
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 856 Rep Power: 3	Re: Sane's Monthly Algorithms Challenge #2 [06-08] Does anyone have (a) large test case(s) for the senior (escalator) problem? It's a hassle to draw one out on paper and then figure out if it passes.

Jun 8th, 2008, 12:00 AM	#28
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] Crap, I drew one out and found a case I'd forgot to cover. Back to the hacking board... (Toggle Plain Text) 10 14 1 3 1 7 1 8 2 3 3 5 3 4 4 9 5 7 5 6 6 1 7 2 8 2 9 10 10 4 10 14 1 3 1 7 1 8 2 3 3 5 3 4 4 9 5 7 5 6 6 1 7 2 8 2 9 10 10 4 [edit:] expected: Bob's getting the pink slip. Explanation: if you draw it out, 3 goes to 4, which is part of a loop with 9 and 10 __________________ <insert disclaimer here> <insert shameless plug for Visual Studio here>

Jun 8th, 2008, 12:02 AM	#29
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 856 Rep Power: 3	Re: Sane's Monthly Algorithms Challenge #2 [06-08] Mrh. Looks like my solution doesn't work... or does it? This is going to take time... Last edited by titaniumdecoy; Jun 8th, 2008 at 12:27 AM.

Jun 8th, 2008, 11:29 AM	#30
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,888 Rep Power: 5	Re: Sane's Monthly Algorithms Challenge #2 [06-08] Don't worry about being super-duper efficient if you're not completely sure that the logic is correct. The number of floors is quite small, so keep it simple! It's better to be a bit slower and have it perfect, than trying to nail the fastest possible solution and getting it wrong. I'm happy to hear people talking out the harder problems this month. Instead of what happened last month. lol. P.S. For the sake of those testing Senior, with the test file Jimbo posted, my solution says that Bob gets fired. But that changes as soon as I change the last line from (10 4) to (10 3). __________________ Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

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]