JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
<< PREV    [ 1 2 3 4 5 6 7 8 ]    NEXT >
Re: ICPC 2007 results??? (response to post by NeverMore) | Reply
My guess is "consecutively". It seems to me to be the word that can most easily change the problem by being left out, and the example case works the same whether that word is there or not.

Solving the problem without that word seems too easy for a world finals set though. (Edit: Actually, it seems too easy for a world finals problem even with "consecutively", but I haven't tried to code it yet so I might be missing something).
Re: ICPC 2007 results??? (response to post by Krumble) | Reply

- Add an edge between every two points if they only intersect segments
of the polygon at end points and the midpoint is outside the polygon.


I am not sure how i can manage this in time. There seems to be 10K points, adding only relevant edges, asks for an angular sweep?
Re: ICPC 2007 results??? (response to post by myprasanna) | Reply
My problem set says there are 100 points. The absolute value of all the coordinates is <= 10000.

So you have 101 vertices => 101 choose 2 edges to check against 100 segments each then possibly run point in polygon (which is linear). So this step is O(n^3).

Every time you check the position of the bag you have to add a vertex (=> 101 edges to check requiring n work each). Then run Djikstra / Bellman Ford / some SSSP. O(n^2) dominates this step and you do this step log(C) times for some upper bound C that you can compute lazily (say the time it takes for the bag to meet you at the closest point on the polygon to you).
Re: ICPC 2007 results??? (response to post by dgarthur) | Reply
Cormack's comments: http://it.slashdot.org/comments.pl?sid=227161&cid=18400387
Re: ICPC 2007 results??? (response to post by NeverMore) | Reply
From this forum the information I get is that there was a mistake in the input of problem J and it was a problem set by SnapDragon.

While I am not in a position to admit about the mistakes officially I think it would be harsh to put the blame on the problem setter about the mistake (if there was one). Because many other judges are involved with a problem and all mistakes should be blamed collectively to the judges.

Let me put it in another way: probably SnapDragon is the person who contributes most for the programming contest community through out the year voluntarily through different ICPC regionals, UVa and of course world finals. Over the years he has found countless mistakes in thousands of problems. Unfortunately the one mistake he was associated with (According to this forum) happens to be a problem in World Finals. Even he has pointed out many ambiguities in World Finals problemset in different years and it is a pity that we (the other judges) failed to find the mistake in problem J if there was one. By not publishing the judge data we don't try to cover things up. It may be mentioned that there were no mistake in the problemset within the year 2001-2006. But some posts here give the impression that mistake in ICPC World FInals is a regular event.
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
I think it would be harsh to put the blame on the problem setter about the mistake
I'm not sure what you mean about people blaming SnapDragon, I only see people saying that they liked the problem he wrote and saying it's a pity that the invalid input was on his problem:

dgarthur
I heard the invalid input was on J, which is a bummer, because I think that was by far the best problem on the set.
NeverMore
I heard SnapDragon wrote problem J. I guess it's no wonder you found it the best of the lot.


I don't think you'll get any arguments here at TopCoder about how much SnapDragon contributes to the programming contest community. :)

It may be mentioned that there were no mistake in the problemset within the year 2001-2006. But some posts here give the impression that mistake in ICPC World Finals is a regular event.
That's probably just because compared to mistakes at TopCoder, mistakes at the ICPC world finals are a regular event.
Re: ICPC 2007 results??? (response to post by aussie) | Reply
That's probably just because compared to mistakes at TopCoder, mistakes at the ICPC world finals are a regular event.


I don't think that's true in a literal sense, even though as a percentage of contests hosted, it might be true. The ICPC World Finals isn't a regular event, and they only have one chance a year to get it right. They probably also don't have as much capacity to adjust things during the competition if they find an error (and TopCoder's format makes it so that adjusting input data can be done without any real effects on the contest while it's happening).

Mistakes certainly happen on TopCoder. I'll volunteer that in the last match, I wrote something that said "see example 8", when in fact it should have been example 6. That's a fairly minor error, and didn't interrupt the flow of the contest, but bigger problems do occur occasionally. I'll bet that approximately once a year, problems with either the set or the competition environment cause a match to go wrong enough that they decide not to rate it. If that happened to the ICPC World Finals once a year, they wouldn't exist :-)
Re: ICPC 2007 results??? (response to post by aussie) | Reply
I think you have frustration towards ICPC because your regionals (SP) are very badly organized (4 wrong problems).

May be topcoder make less mistakes. But there is no mistake of the scale below in ICPC :)

http://forums.topcoder.com/?module=Thread&threadID=160720&start=0&mc=61
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
-- By not publishing the judge data we don't try to cover things up. --

Really? Then what are you trying to achieve by that?
Re: ICPC 2007 results??? (response to post by Petr) | Reply
When we go for a world finals we don't have any doubt about the correctness of the solutions.

Probably the reason for not publishing data is because it has not been done in the past (Some sort of tradition). But some judges care to make a second set of data and publish it via UVa. I have always cared to make a second test data for the problems that I had been associated with and put it to UVa.
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
Why aren't solutions also released? I'd imagine many people would be interested in reading them for educational value. This is an academic and not business-oriented event after all, so it seems strange that such a source of knowledge would be kept secret. I understand the problem setters already volunteer much time (and we're all grateful) and may be too busy to donate extra time for writing an editorial, but surely coded solutions already exist and simply releasing those I feel would be appreciated by many people and unwanted by no one.
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
I don't think it has anything to do with tradition - there is no real reason to keep data secret, but they like to cover their behinds. I think it is paranoid, but maybe they had some bad experience, I don't know... I agree with Prof. Cormack - making it public could only improve the quality of the contest.

Mr. Manzoor, I know you try your best to make some unofficial data public (or at least available on UVa) and I think everyone appreciates it.
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
-- When we go for a world finals we don't have any doubt about the correctness of the solutions.

Probably the reason for not publishing data is because it has not been done in the past (Some sort of tradition).
--

Sorry for being harsh, but both these sentences just don't sound right.

First, you should always be ready that judges' data or whatever is wrong. For example, at the NEERC we have automated testing, but for every problem several first runs are re-checked by hand (by re-checking I mean not just comparing the output, but drawing the testcase on a sheet of paper, rereading the statement, etc) to ensure everything is OK, and only after several accepted runs we turn automatic-only mode on.
(EDIT. To the best of my knowledge that never led to any change in judges' data during the contest, but we still do it)

Second, even the fact that such non-transparency leads to such accusations by Gordon should be enough to overcome tradition. If something stupid is supported only by tradition, why not break it?
Re: ICPC 2007 results??? (response to post by Minilek) | Reply
It is business-oriented, why do you think IBM keeps pumping money into it?

I do agree that they should publish both data and solutions.
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
Really? Or probably such (or even worse) mistakes just go unnoticed because of non-transparency? How can we tell?
<< PREV    [ 1 2 3 4 5 6 7 8 ]    NEXT >

RSS