DWITE Issues

[Tony]

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.

[saltpro15]

or submits the wrong question 2 times by accident... well, lesson learned I suppose

[A.J]

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]

spring DWITE would be great, summer, not so much. well I wouldn't be in it at any rate

[saltpro15]

... sooooo did anyone ever find an optimal way to solve Q4?

[DemonWasp]

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]

ah thanks DemonWasp

so Dan and Tony please,

NO MORE OF THESE UNSOLVABLE PROBLEMS

(hope that tag worked)

[DemonWasp]

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.

[saltpro15]

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]

well, I guess we'll never know, as HAnson didn't participate in the last contest.

[saltpro15]

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]

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]

never mind, my idea has died