Problem 5 Oct. 2008

[divad12]

DWITE Problem 5 Oct. 2008: http://dwite.org/questions/moving_stuff_in_boxes.html

I am disappointed with the quality of this problem. It was a question that put too much focus on properly parsing data (for example the dimensions of each item could have been given) and not enough on the formulation of an algorithm to solve it (it was obvious that it was multiple-knapsack and recursive descent should be used).

Another major concern is that this problem rewarded those who did not make an attempt to solve the problem the way it was intended but simply approximating a solution (e.g. ceil(num_hashes/25.0)). Look at the codes of those who received 5/5 and some of those who received 1/5. It is unfair to punish those who made a valid attempt to solve the problem (e.g. teams "Hanson" and "Beat Hanson" from Woburn) and reward those who made made no effort in programming a correct solution. I think that future test cases should aim to minimize the ease of "bullshitting" or simply outputting random numbers (for example, have 5 sets of 5 test cases and require that all 5 test cases from one set be correct to be awarded 20 points, (similar to the CCC)).

I think that future problems should have focus on the algorithms required to solve them, instead of taking input and tedious string processing. Problems that require abstraction and modeling (such as to graphs) or mathematical problems are much more satisfying and enjoyable to work out and solve, and are more similar to problems offered from larger programming contests such as the IOI, TopCoder, USACO, and CCC.

I enjoyed problems like http://dwite.org/questions/bridges_in_a_graph.html and http://dwite.org/questions/portals.html that I thought were interesting and elegant but nevertheless challenging. I think we should be given more problems like the above and less like this one.

I think DWITE should also pose some problems that require dynamic programming.

What do you guys think?

[S_Grimm]

not everyone knows how to use dynamic programming. most is just oop

[thenewme91]

As one of the students on a team who submitted an "approximate" solution and received 5/5, I sympathize with your frustration with the test cases. I myself was surprised that my approximate solution got 5/5 -- when I submitted the code, I was actually expecting a score more along the lines of 3/5.

Because there are already larger programming contests (IOI, TopCoder, USACO, CCC) out there, I'm not really sure it would make sense for DWITE to strive to mimic these contests more. My school currently encourages our students to participate in DWITE so that they can get a feel for what a contest environment is like, without having to deal with the more challenging problems posed by the other contests. I can only imagine that without this sort of "stepping stone", many students (my younger self included) would be too discouraged to even try the other contests. That, however, is my opinion, and perhaps DWITE was not meant for this purpose.

Either way, it is only October, and many students (at least from my school) are quite rusty from a lack of programming over the summer. As a result, it seems logical to me that the questions would be slightly easier in October than in other contests. At least, that is what my experience has been with past DWITEs.

[Dan]

We do aim to start the season easy and get harder with each round. We also have to balance the contest for both students new to programming and more expercented students. I have received a few complaints about it being to hard this round as well.

And yes DWITE is meant to be partice for other contests witch is why it is done muptial times per year.

I am working on a method of detecting hard coding however it is hard to do well keeping the judge fast.

When we first started doing dwite with the new system it did have 5 sets of test cases witch where each run individual however it slowed the judge down significantly causing there to be a back log of unmarked submissions. One goal of dwite is close to live marking witch means the judge needs to be fast as possible.

With that side we will take your suggestion in to consideration with all the other feedback to try and make each round better then the last.

[klopyrev]

I think problem 5 is a really bad problem to put on a contest like this. First of all, by not making the test cases hard, you are encouraging students to submit incorrect solutions. Secondly, I don't actually see a solution to that problem that will run in time. Perhaps someone can come up with a good algorithm with reasonable worst case complexity. You can make test cases with 29 items that will only have one unique solution. I'd love to see a solution to this.

[Insectoid]

When is the next DWITE? I'd like to give it a go with some friends, and I didn't get registered this time.

[riveryu]

Are there official solutions to DWITE problems?
How come no programming contest have official solutions..

I have only seen CCC, DWITE though, so I don't know, but CCC and DWITE don't seem to have official solutions publicized.

I would love to see the solution for this one (and learn it).

[McKenzie]

I'd just like to take a moment to thank Dan and Tony for all their hard work. It's a lot of hard work that you guys do just to give back to the community. You guys have made great improvements in the contest and I know my kids love writing it.

I encourage other posters to put their concerns about problems with questions in a proper context. The reality is some of the questions will have errors and odd test cases, that's just life, for the most part the contest is great.

[saltpro15]

I dont know man, I thought it was a pretty challenging question although it definitely bugs me that people got 5/5 when it didnt even work right i got a mere 2/5 for my attempt and if someone could p.m. me a correct code I would be very grateful (to figure out what i did wrong).

[thenewme91]

Dan @ Thu Oct 23, 2008 10:46 pm wrote:

When we first started doing dwite with the new system it did have 5 sets of test cases witch where each run individual however it slowed the judge down significantly causing there to be a back log of unmarked submissions. One goal of dwite is close to live marking witch means the judge needs to be fast as possible.

Perhaps the judge could run one set case for each program as soon as it is submitted, and use it provide early ("close to live") feedback, and then queue the program for more testing to be run during "idle" periods? This would allow particpants to catch certain "obvious" errors earlier, while at the same time providing more through feedback.

That said, doing something like this would involve a few UI changes... for example, a program would have three states while being marked -- Unmarked (no test cases run), Marking In Progress (one set run), Marking Complete (all sets run). The results page would need to be modified to show the results of both partial and full results (or more than one results page would need to be created). Someone would need to come up with more test cases, and it does increase the complexity of the judge somewhat. (And there's still the risk of a delay between the end of the contest and the final results being available.)

But if it worked, it'd mean "the best of both worlds" (or the worst, depending on how you look at it).

A judge that did this could look something like this:

code:

while (there are still programs left to be marked)     while (the contest is still running and there are new submissions)         take next new submission         run "preliminary" test set and create early feedback page         add program to bottom of the queue for more thorough testing     end while     if (there are any programs in the queue)         remove program from top of the queue         run one test set on the next program         update or create final feedback page     end if end while

But DWITE is pretty good the way it is, so. *shrugs*

Just my two cents.