DWITE Issues
Author |
Message |
Tony
|
Posted: Sun Mar 01, 2009 4:17 pm Post subject: RE:DWITE Issues |
|
|
Every team gets two submissions for each problem. You'd be surprised how often someone reads or writes to a file with a wrong name. |
Tony's programming blog. DWITE - a programming contest. |
|
|
|
|
Sponsor Sponsor
|
|
|
saltpro15
|
Posted: Sun Mar 01, 2009 4:20 pm Post subject: RE:DWITE Issues |
|
|
or submits the wrong question 2 times by accident... well, lesson learned I suppose |
|
|
|
|
|
A.J
|
Posted: Sun Mar 01, 2009 5:03 pm Post subject: Re: DWITE Issues |
|
|
McKenzie wrote:
First, let me say that Tony and Dan have done a fantastic job with DWITE. It was good when Mr. Sentjens started it, but it is GREAT now.
As far as cheating goes (and I think AJ's common sense definition is on the money) I understand why a team would want to ('hacking' Hacker Dan...cool) but I think a score of zero is the correct response. I know you see DWITE as "just a fun contest" to help prepare for CCC and ECOO but a lot of kids give their blood sweat and tears to DWITE and having a fake team in spot 4 means everyone else appears one rank lower. Don't kid yourselves, kids go home and say "hey, we got 11th place in DWITE"
I agree. Our school did put a lot of effort into this contest and we were kind of disappointed to see that we all got a place lower than we would have because of this team.
I also agree that DWITE is a GREAT contest, and I am looking forward to whether they have a spring and summer contests. |
|
|
|
|
|
saltpro15
|
Posted: Sun Mar 01, 2009 5:06 pm Post subject: RE:DWITE Issues |
|
|
spring DWITE would be great, summer, not so much. well I wouldn't be in it at any rate |
|
|
|
|
|
saltpro15
|
Posted: Wed Mar 18, 2009 7:39 am Post subject: RE:DWITE Issues |
|
|
... sooooo did anyone ever find an optimal way to solve Q4? |
|
|
|
|
|
DemonWasp
|
Posted: Wed Mar 18, 2009 9:33 am Post subject: RE:DWITE Issues |
|
|
Wasn't problem 4 just a restatement of the Traveling Salesman Problem? In that case, the best you can do is a brute-force solution: compute the distance for each permutation, choose the smallest, output. There's no known faster way. For more information, see: Traveling Salesman Problem. |
|
|
|
|
|
saltpro15
|
Posted: Wed Mar 18, 2009 11:07 am Post subject: RE:DWITE Issues |
|
|
ah thanks DemonWasp
so Dan and Tony please,
NO MORE OF THESE UNSOLVABLE PROBLEMS
(hope that tag worked) |
|
|
|
|
|
DemonWasp
|
Posted: Wed Mar 18, 2009 12:22 pm Post subject: RE:DWITE Issues |
|
|
It's not technically unsolvable. The only difficult bit is determining the permutations without duplications, which minimises the number of cases you need to compute. After that, just optimise to do as well as possible - I think someone mentioned a while ago that it was fairly easy up to 19 nodes, it was only 20 that would take an unreasonable amount of time. |
|
|
|
|
|
Sponsor Sponsor
|
|
|
saltpro15
|
Posted: Wed Mar 18, 2009 12:24 pm Post subject: RE:DWITE Issues |
|
|
So brute forcing would solve this in O(n!) time correct? I do not think there is any way a high school student could code a 5/5 solution in less than 3 hours |
|
|
|
|
|
Analysis Mode
|
Posted: Wed Mar 18, 2009 1:30 pm Post subject: Re: DWITE Issues |
|
|
well, I guess we'll never know, as HAnson didn't participate in the last contest. |
|
|
|
|
|
saltpro15
|
Posted: Wed Mar 18, 2009 2:40 pm Post subject: RE:DWITE Issues |
|
|
haha true, this definitely would have been challenging for him though, it's challenging for anyone
EDIT:
I have an idea as to how to solve this 5/5! To Bluefish I go, let's hope I remember enough C++ to do this... |
|
|
|
|
|
Foundation
|
Posted: Wed Mar 18, 2009 8:27 pm Post subject: Re: DWITE Issues |
|
|
I would be very interested to know how one would optimize going through permutations as that would be O(N!).
Another solution to P4 would be a standard application of the optimized TSP DP solution. Letting each state be represented as an integer representing all the nodes visited and an integer representing the current node.
Then the time complexity would become O(2^N*N) which is around 40 million and will work within the 3 second time limit. |
|
|
|
|
|
saltpro15
|
Posted: Wed Mar 18, 2009 8:35 pm Post subject: RE:DWITE Issues |
|
|
never mind, my idea has died |
|
|
|
|
|
|
|