Programming Forums > Application Development > Software Design and Algorithms

Jimbo · Jun 8th, 2008, 1:21 PM

Quote:

Originally Posted by Sane

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

Right. To draw out that segment of the graph, so people can see, here's what it looks like:

(Toggle Plain Text)

10<---9
|     ^
|     |
----->4
      ^
      |
      3
----------
rest of the graph

Changing the 10 to go to the 3 eliminates the loop which is otherwise cut off from the rest of the graph.

Sane · Jun 8th, 2008, 1:27 PM

Good stuff.

You guys might kick yourself when you see the solution. I have a feeling you guys might be over-complicating it now. lol. Have you figured it out Jimbo?

Jimbo · Jun 8th, 2008, 1:29 PM

Quote:

Originally Posted by Sane

You guys might kick yourself when you see the solution. lol. Have you figured it out Jimbo?

I'll admit, I cheated. The problem sounded so familiar I poked open my algorithms book. I think I'll pass on submitting that problem now

Sane · Jun 8th, 2008, 1:34 PM

Awe, dang. I'm actually kind of surprised it was in there... It's a generic problem, but I've never seen this version of it before.

Since I didn't cover all my bases, I don't consider it cheating if you've found the same problem elsewhere. It's my fault that it's been done before. Nothing in the rules against looking at textbooks.

I'm also wondering if their solution is the same as mine, since it's again not something I've learned from a textbook, but had to think up. So as long as you didn't copy their code, you should go ahead and submit it.

titaniumdecoy · Jun 8th, 2008, 2:36 PM

I didn't realize that loops caused problems in the senior (escalator) problem, so it turns out my current solution is $O(E*V)$ . I can't see any way to do it in $O(E)$ ... hint?

Sane · Jun 8th, 2008, 2:43 PM

So worst case it's 100^3 operations? Then don't worry about it. That's the expected solution. The best possible solution is |E|+|V| (I was writing it as just |E| earlier), but that's needlessly quick (and will be explained in the solution thread).

titaniumdecoy · Jun 8th, 2008, 7:10 PM

I just thought I would point out that the submission deadline is June 31, but June has only 30 days.

Also I found the advanced problem much, much easier than the senior problem. Assuming I got it right, that is.

Sane · Jun 8th, 2008, 8:05 PM

Quote:

Originally Posted by titaniumdecoy

I just thought I would point out that the submission deadline is June 31, but June has only 30 days.

Okay. I've scored titanium's submissions, and he's got a zero.

Anyone else notice any incredibly stupid mistakes?

Sane · Jun 25th, 2008, 1:07 PM

Just a small reminder: 5 days left!

Jabo · Jun 25th, 2008, 6:59 PM

Quote:

Originally Posted by Sane

Anyone else notice any incredibly stupid mistakes?

Sane has the makings of an IT Director...

Jun 8th, 2008, 1:27 PM	#32
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,840 Rep Power: 5	Re: Sane's Monthly Algorithms Challenge #2 [06-08] Good stuff. You guys might kick yourself when you see the solution. I have a feeling you guys might be over-complicating it now. lol. Have you figured it out Jimbo? __________________ Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Jun 8th, 2008, 1:34 PM	#34
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,840 Rep Power: 5	Re: Sane's Monthly Algorithms Challenge #2 [06-08] Awe, dang. I'm actually kind of surprised it was in there... It's a generic problem, but I've never seen this version of it before. Since I didn't cover all my bases, I don't consider it cheating if you've found the same problem elsewhere. It's my fault that it's been done before. Nothing in the rules against looking at textbooks. I'm also wondering if their solution is the same as mine, since it's again not something I've learned from a textbook, but had to think up. So as long as you didn't copy their code, you should go ahead and submit it. __________________ Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Jun 8th, 2008, 2:36 PM	#35
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 843 Rep Power: 3	Re: Sane's Monthly Algorithms Challenge #2 [06-08] I didn't realize that loops caused problems in the senior (escalator) problem, so it turns out my current solution is $O(E*V)$ . I can't see any way to do it in $O(E)$ ... hint?

Jun 8th, 2008, 2:43 PM	#36
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,840 Rep Power: 5	Re: Sane's Monthly Algorithms Challenge #2 [06-08] So worst case it's 100^3 operations? Then don't worry about it. That's the expected solution. The best possible solution is \|E\|+\|V\| (I was writing it as just \|E\| earlier), but that's needlessly quick (and will be explained in the solution thread). __________________ Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Jun 8th, 2008, 7:10 PM	#37
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 843 Rep Power: 3	Re: Sane's Monthly Algorithms Challenge #2 [06-08] I just thought I would point out that the submission deadline is June 31, but June has only 30 days. Also I found the advanced problem much, much easier than the senior problem. Assuming I got it right, that is.

Jun 25th, 2008, 1:07 PM	#39
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,840 Rep Power: 5	Re: Sane's Monthly Algorithms Challenge #2 [06-08] Just a small reminder: 5 days left! __________________ 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]