Computer Science Canada My sincere apologies |
| Author: | bbi5291 [ Thu Dec 16, 2010 4:15 pm ] |
| Post subject: | My sincere apologies |
I would like to apologize to the DWITE community for my astounding lapse of judgement. I was the one who suggested the wildcard matching problem for the DWITE contest that just passed. My intention was that this problem would be a difficult exercise in dynamic programming. I did not realize that in some languages (*cough* Java *cough*), there are built-in libraries that make a problem of this nature trivial. I am ideologically opposed to the appearance of such problems on algorithmic competitions, and I was myself rather incensed when a problem appeared on ECOO last year that was trivial with the use of "eval" or a similar function in some languages, but forced me to code a recursive-descent parser in C++. Sadly, it appears I have failed to myself take the necessary precautions against such situations. |
|
| Author: | Dan [ Thu Dec 16, 2010 4:53 pm ] |
| Post subject: | RE:My sincere apologies |
Time to learn about regex? Many languages have support for it in their default libraries. In any case i don't necessarily think it is a bad thing. We had discussed the possibility of the use of regex to solve this problem and deiced to use it any way. DWITE is about practice if teams want to use an easier solution then they are free too. Well such problem solving methods might not help them learn algorithms, it does teach them real world solutions to seemingly complicated problems. |
|
| Author: | DemonWasp [ Thu Dec 16, 2010 6:45 pm ] |
| Post subject: | RE:My sincere apologies |
"You know, in certain older civilized cultures, when men failed as entirely as you have, they would throw themselves on their swords." - The Operative, Serenity I'm joking, of course. While in general I agree that for the purpose of a contest the problem should be equally hard in all languages, that isn't the case in the Real World (tm). The lesson to learn here is to use the right tool for the right job; if your problem is hard in your language / library of choice, try another language / library. |
|
| Author: | Tony [ Thu Dec 16, 2010 7:40 pm ] |
| Post subject: | RE:My sincere apologies |
In fact, one could use a different language for each of the 5 problems. |
|
| Author: | bbi5291 [ Thu Dec 16, 2010 8:08 pm ] |
| Post subject: | Re: RE:My sincere apologies |
DemonWasp @ Thu Dec 16, 2010 6:45 pm wrote: "You know, in certain older civilized cultures, when men failed as entirely as you have, they would throw themselves on their swords."
I'm not saying that problems have to be equally hard in all languages. In fact, this is not even true with contests as prestigious as USACO --- there are lots of USACO problems that are a bit harder in Pascal because it lacks a built-in sort function, and there was even at least one problem that nobody solved correctly in Pascal because of the lack of an efficient built-in symbol table (i.e., std::set in C++).
- The Operative, Serenity I'm joking, of course. While in general I agree that for the purpose of a contest the problem should be equally hard in all languages, that isn't the case in the Real World (tm). The lesson to learn here is to use the right tool for the right job; if your problem is hard in your language / library of choice, try another language / library. On the other hand, you'll never see a problem on USACO that just asks you to sort numbers, or just asks you to efficiently maintain a dynamic set. Instead, these are the easy parts, mere building blocks of more complex algorithms. The real challenge is to solve the hard part, which probably requires you to invent an algorithm you've never seen before. (Or, for easy contests, at least, an algorithm that doesn't exist in the built-in libraries.) That's why I kicked myself after AJ told me that nobody correctly solved this problem in C++ --- the issue isn't that it's easier in Java, but rather that there is no "hard part" to solve after the library call. |
|
| Author: | A.J [ Thu Dec 16, 2010 8:11 pm ] |
| Post subject: | RE:My sincere apologies |
Albeit it being hard to create questions of equal difficulty in most of the programming languages, I believe #5 was a bit too easy for certain languages. Like Brian had mentioned, the intended solution was meant to be a lot more challenging. Still, only a few teams solved the problem completely, and since Brian and I will be posting analyses to the solutions later on, no harm done. And we did decide to use this problem regardless of 'regex', as it wasn't something that trivialized the problem completely for most people (as only a few users had it solved completely using regex). In the future, though, we'll try avoiding something like this (or keeping it to a minimum). |
|
| Author: | bbi5291 [ Thu Dec 16, 2010 8:16 pm ] |
| Post subject: | Re: RE:My sincere apologies |
A.J @ Thu Dec 16, 2010 8:11 pm wrote: Still, only a few teams solved the problem completely, and since Brian and I will be posting analyses to the solutions later on, no harm done. Personally, my contention is "Cyril still won (and he deserved to), so no harm done."  |
|
| Author: | chunnn_li [ Mon Jan 17, 2011 8:22 pm ] |
| Post subject: | RE:My sincere apologies |
bbi5291, Although the round for this problem finished a while ago, I would just like to ask about a problem me and my team had on it. My friend had solved this problem with regex in java. It ran perfectly fine, and seemed to run pretty well under the time limit asked. However, when we submitted the solution, the dwite computer said our program timed out. Do you know a possible reason this could have happened? If it helps, my friend coded the program in eclipse. |
|
| Author: | Tony [ Mon Jan 17, 2011 10:22 pm ] |
| Post subject: | RE:My sincere apologies |
Possible reasons are different hardware, not accounting for JVM startup time, and benchmarking for just one testcase at a time, instead of all five. What's your team's name? |
|
| Author: | chunnn_li [ Tue Jan 18, 2011 7:25 pm ] |
| Post subject: | RE:My sincere apologies |
Calcoolus The person that wrote the code was tummychow EDIT: Sorry, he says that he wrote a package statement at the top that probably screwed up the code. : S |
|