JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
ICPC 2007 results??? | Reply
anybody knows final results??
Re: ICPC 2007 results??? (response to post by naguib) | Reply
Nobody. Current estimates are:
1. Warsaw - 8
2. Tsinghua - 7
3-5. Novosibirsk, MIT, SPb IFMO - 6
6. Saratov SU - 6
7. U of Twente - 6
8. Shanghai JiaoTong U - 6
9. U of Auckland - 6
10. U of Waterloo - 6
11. Moscow SU - 6
12-13. CalTech, Petrozavodsk SU - 6
Re: ICPC 2007 results??? (response to post by Petr) | Reply
Why 8 for warsaw ? I thought the results http://icpc.baylor.edu/icpc/Finals/scoreboard/ here is somewhat final, since the contest should already been finished by now.
Re: ICPC 2007 results??? (response to post by wongiseng) | Reply
It's the result of the first four hours. They freezed the scoreboard. It's common practice in ICPC.
Re: ICPC 2007 results??? (response to post by Aldanur) | Reply
Wow MIT, SPbU IT and Novosibrisk are very close.

Anybody has a detailed result?
Re: ICPC 2007 results??? (response to post by ilham) | Reply
They didn't give us any more results than what was listed. If the results were extended down I think my team would of been close to 14th, but I don't know. We submitted our 5th rigth at the hour.

// We got 3rd place U.S. team for sure and probably top team with a female :)
Re: ICPC 2007 results??? (response to post by cep21) | Reply
I've looked at the picture of the award ceremony. It seems that SPbU IFMO team holds both the fourth place and third place plaques. Anybody willing to share the account of what happened there? Do they actually count to the seconds as well?

It is rather curious that WarsawU receive the trophy and the plaque before TsinghuaU got theirs. Is it common practice in the world finals?
Re: ICPC 2007 results??? (response to post by ilham) | Reply
>> Do they actually count to the seconds as well?

No. Should two teams solve the same number of problems and have the same time penalty, they break the tie by who submitted the most recent accepted solution the earliest.
Re: ICPC 2007 results??? (response to post by Minilek) | Reply
Are you affraid of taking pictures?
I couldn't see you in any of the two GCJLA albuns I saw, nor in the ICPC albuns
Re: ICPC 2007 results??? (response to post by Malkava) | Reply
I was about to go look for his picture in ICPC digital library just before stumbling upon this post, I guess you saved me some time :-)
Re: ICPC 2007 results??? (response to post by Krzysan) | Reply
By the way, that digital library (ICPC) is a nice example of wrong use of AJAX features. A usual library like the previous years is much more fast and easy to handle.
Re: ICPC 2007 results??? (response to post by Aldanur) | Reply
What does the colour code mean..yellow, gray, brown etc..
Re: ICPC 2007 results??? (response to post by KunalKumar) | Reply
I guess it's gold/silver/bronze, for the colors of the medals?
Re: ICPC 2007 results??? (response to post by Petr) | Reply
What were the two problems that Warsaw didn't solve? (if anyone knows)
Re: ICPC 2007 results??? (response to post by NeverMore) | Reply
From the photographs and the summary, it seems that WarsawU solved all but H and J.
Re: ICPC 2007 results??? (response to post by NeverMore) | Reply
No body solved problems H and J. Only one team even submitted H (Tsinghua), and there were *lots* of failed submissions for J...probably by teams who thought it was simply min-cut. None of the top 7 or so teams even tried to submit J.

EDIT: *learns to read through thread before responding to a question*
Re: ICPC 2007 results??? (response to post by Petr) | Reply
I did not know filipek registered in TC long back. He even has a member photo! Looks like he is not interested in TC contests :(
Re: ICPC 2007 results??? (response to post by prunthaban) | Reply
So I submitted a couple problems to the world finals, and both got rejected. At the time, I was a little disappointed. After seeing the problems they chose instead, I almost feel insulted. My gosh - I hate this problem set.

I also heard they had an error in a test input... again. Go ACM.
Re: ICPC 2007 results??? (response to post by dgarthur) | Reply
Why do you hate the problem set?
Re: ICPC 2007 results??? (response to post by NeverMore) | Reply
Well, I do actually quite like A and J. 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.

My main complaints are (a) lack of variety, and (b) lack of problems requiring any kind of original insight. The lack of variety is obvious - FOUR geometry problems, and then B and G. If you replaced geometry with graph theory or DP or something, maybe that would be ok. But 4 problems where your biggest concerns have to do with questions like, "do these lines intersect"? Blech. The lack of insight is more subjective, but I think its perhaps even more obvious.

- The hardest problem should be the one requiring the most insight. Yet for H, all you want to do is understand overlapping triangles. I have seen an algorithm in at least two different courses that solves this problem directly. Its just a pain to implement.

- Problem E is basically shortest path on the plane with a polygon removed. This has been asked on an ACM before.

- Problem D is basically, "Do you know Pick's theorem?"

- Problems F and G? Hello, complete search.

I haven't really looked at problem I yet because I'm not a fan of physics in contests, but of the remaining problems (other than J), its hard to classify a single one of them as requiring serious original insight. For the ACM world finals, that is poor.
Re: ICPC 2007 results??? (response to post by dgarthur) | Reply
I heard SnapDragon wrote problem J. I guess it's no wonder you found it the best of the lot.

I just wish he also wrote an "editorial" for the problem, especially given no-one solved it. ;-)

EDIT: btw, I too heard (thanks Abednego) that the invalid input was on J.
Re: ICPC 2007 results??? (response to post by NeverMore) | Reply
Maybe SnapDragon can come and comment himself. In the meantime, here's the algorithm I came up with.

Initialize X_i = mincut(i, 0) for all i.
while (the graph is non-empty) {
  Let x denote the smallest value of X_i.
  Remove all vertices i with X_i <= x.
  For each remaining vertex, set X_i = min(X_i, x + mincut(i, 0)) 
}
return X_1

I am pretty sure I have a valid proof, but it is messy =P.
Re: ICPC 2007 results??? (response to post by dgarthur) | Reply
Do you think this would work: Remove unreachable nodes and for all nodes i assign mincut(i,0) as the node capacity and run maxflow(1,0)?
Re: ICPC 2007 results??? (response to post by dgarthur) | Reply
Could you please write down at least some sketch of a proof, because it is really interesting. This seems the only problem on this finals which is REALLY difficult algorithmically.
Re: ICPC 2007 results??? (response to post by dgarthur) | Reply
Initialize X_i = mincut(i, 0) for all i.

Was that choice of initialization necessary for correctness? Could you have chosen any upper bound on X_i? (e.g. n?).
Re: ICPC 2007 results??? (response to post by Minilek) | Reply
You cannot use any upper bound. If you set all vertices to have a value of 1000, you'd remove them all in the first iteration of the loop. I believe you could use an initial value being the degree of each vertex, but I haven't thought it through yet.
Re: ICPC 2007 results??? (response to post by Krumble) | Reply
SnapDragon's analysis starts his "d-numbers" at infinity. Won't there be the problem you described? Maybe some d-number needs to start at a non-infinite number; e.g. starting the d-number of the sink as 0.
Re: ICPC 2007 results??? (response to post by Minilek) | Reply
SnapDragon's analysis starts his "d-numbers" at infinity. Won't there be the problem you described? Maybe some d-number needs to start at a non-infinite number; e.g. starting the d-number of the sink as 0.


Our algorithms are ordered differently. Mine keeps relaxing all d-numbers until they stop changing, so it doesn't matter where it starts. dgarthur's starts with known final d-numbers and never changes them again. So it has to have a starting point with a correct final d-number - for instance, the node with the smallest min-cut to the outside, which can't be reduced.
Re: ICPC 2007 results??? (response to post by SnapDragon) | Reply
Thanks, I see your point. Is it also the case that his is more efficient? It seems to be O(n^2 M) where yours (unoptimized) has the most obvious implementation of O(n^4 M). Here M is the cost of computing a max-flow. This is not including your optimization of not recomputing max-flow from scratch in each iteration though.
Re: ICPC 2007 results??? (response to post by dgarthur) | Reply
Why this approach is incorrect?
May be anyone can show me crash test for this solution?

1. Assign X_i = mincut(i,0)
2. Using binary search find minimal x : there is no way from 1 to 0 using nodes with X_i > x.

Thanks!
Re: ICPC 2007 results??? (response to post by dgarthur) | Reply
You missed:
- Problem D, "don't forget to remove unnecessary input"
- Problem G, "don't miss an important single word in the middle of the statement"
Having said that, the difficulty level seemed good - it just seemed there were many 'really-annoying-to-code' questions. I thought C was a good non-geometry geometry question.
Re: ICPC 2007 results??? (response to post by sql_lall) | Reply
I believe the only "geometry" problem is Problem H, while the others seem geometry but do not involve geometry or only some basic geometry :)
Re: ICPC 2007 results??? (response to post by sql_lall) | Reply
When we read problem G, we said: "Easy"; But it took about 2:30 hours to get Accepted for it! We missed many things and we wasted lots of valuable time. We solved only 4, but I think we could solve at least 5 if we didn't do bad at problem G.
Re: ICPC 2007 results??? (response to post by sql_lall) | Reply
I don't really love ACM when the problems are more about paying attention to the smallest detail in the statement than about making an optimized algorithm for an interesting problem.
Re: ICPC 2007 results??? (response to post by sql_lall) | Reply
Discovering that single word in G was fun. Not getting B accepted until I took the time to do a complete rewrite (hey, a rewrite is a rewrite, even if it's just 10 lines...), which was after 4 hours, was not so fun.

At least I managed to get a component review done in the Cybercafe :-)
Re: ICPC 2007 results??? (response to post by cnettel) | Reply
I'm curious, what exactly was the single word?
Re: ICPC 2007 results??? (response to post by NeverMore) | Reply
Yeah, I want to know what the word was too. I solved the problem during the competition, but only after one of my teammates had tried solving it, and then must have 'seen the word'. He explained the problem to me, and I completely rewrote a solution without even reading the problem :) Got it accepted first time, too.
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 dgarthur) | Reply

- Problem E is basically shortest path on the plane with a polygon removed. This has been asked on an ACM before.


Can you give a hint or link of how to solve this? If the no of points are small i can do a dijikstra, but the complexity will be O(E*log(E)). Here generating the right edges is a challenge, i guess.

Also can anyone give hints on how to solve the other problems as well ... (like I) ...

Congrats to the Warsaw team for their win! Please share your approaches for the problems.
Re: ICPC 2007 results??? (response to post by myprasanna) | Reply
For E, you create the visibility graph as follows:

- A vertex for each vertex of the polygon and for the starting point
- 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.
- Weight the edge by the time it would take the person to walk that distance.

Now we binary search on the time (we can do this since we are guaranteed to walk faster than the bag moves). Place the bag where it will end up at a given time and add it to the visibility graph and run Djisktra's to answer yes/no on binary search.

One of my coaches came up with a very cute solution to C using convex hull. The other 4 'easy' problems are pretty straight forward.
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
My only complaint was having a problem that required knowing Pick's Theorem. I dislike programming problems that require knowing an obscure math formula.

I agree with the rest of what you said as well, but maybe not as strongly.
Re: ICPC 2007 results??? (response to post by cep21) | Reply
This particular obscure formula is very famous and appears in programming in math contests all the time.
Re: ICPC 2007 results??? (response to post by cep21) | Reply
I think only knowing that such a formula exists is enough. You can always draw 10-15 triangles and then try to construct a formula.
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 Kawigi) | Reply
Yeah, I meant that per match or per problem the mistakes happen more often at ICPC than here. ICPC might have only 1 chance a year to get it right, but TopCoder also has ~50 chances a year to get it wrong ;).
Re: ICPC 2007 results??? (response to post by aussie) | Reply
If by ICPC you mean ICPC regionals then you are right.

If by ICPC you mean only world finals or DHaka regional or neerc then you are wrong.
Re: ICPC 2007 results??? (response to post by Kawigi) | Reply
And I didn't get +50 points for pointing it out to you :(
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
Really? Or probably such (or even worse) mistakes just go unnoticed because of non-transparency? How can we tell?
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
In other words, your attempt to attack TopCoder is just insulting, because it's TopCoder who discussed its problems in public (and you've in fact provided a link to such discussion) and posts official testcases after all contests. While any means of discussing anything officially with ICPC is reduced to just emailing Bill, him answering in some vague way, and everything staying the same.
Re: ICPC 2007 results??? (response to post by Petr) | Reply
Well I did not attempt to compare ICPC and topcoder in any way it was what aussie's post did. And then I just pointed out a big mistake made by topcoder in 2002 to proof that everyone makes mistake.

I am not related to ICPC in administrative way (You won't find my name in the ICPC page). If you have any complains about DHaka regional problem that is only what I can deal with. I am not liable nor apologize on what Bill does. Even I have made complains about indian regionals to many people and got no feedback.

But I guess the main objective of ICPC is its growth to different countries and so they overlook regional lapses.

I personally do not support the idea of not publishing data. But the idea of not publishing data does not make me or other judges less careful in ensuring the correctness of my problems and that is what I was trying to say. May be I won't be a judge next year any way so I cannot influence on decision making issues.

-Shahriar Manzoor
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
-- Well I did not attempt to compare ICPC and topcoder in any way --

The phrase "But there is no mistake of the scale below in ICPC" made me think you did. Probably I should pay more attention to the smileys :)

Is the situation really that bad? If even the WF judges cannot influence the organizers, then who can? Or are you in minority among judges on this subject?
Re: ICPC 2007 results??? (response to post by Petr) | Reply
No No No! The situation is not that bad.

We never tried that seriously to get the official data out because we are producing unofficial data anyway and maintaining correctness to our best level. But I understand that it is important for coaches and contestants for transperency.

I understand the emotion of gordon or other coaches whose teams suffered for the mistake to write something like "Trying to cover up mistakes". And I don't think he really believes that me or derek are trying to cover up things.

But after making efforts to publish unofficial data (and mentally supporting publishing of data) the "Covering things up" issue is not palatable to me.
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
We never tried that seriously to get the official data out because we are producing unofficial data anyway


Do you?
And where can we get that "unofficial" data?

Well, this really strange thing with "unofficial data", "unofficial standings" insults me.

This year at NEERC (http://neerc.ifmo.ru) we published the official data and let everybody appeal should wrong test cases be found.

Yes, this made us look more thoroughly into the data because we knew that it will be public. But I think it is a better way to go then a situation when the team cannot find out what happened and why their solutions were rejected.

And that is just not talking about such things as
- unpublished time limits for problems (and is there really strict policy on it?),
- human judging (which takes away any availability of objectivity),
- no ability to see who solved which problem at what time after the contest (the desire not to insult teams that have more penalty? Are we in the elementary school and care for psyches of little children? Come on, this is a competition between college students!),
- and other obscure things make me really wonder where does ICPC go from here...
Re: ICPC 2007 results??? (response to post by andrewzta) | Reply
From where do you get the info that world finals do human judging?

The PC^2 compares the two files and shows us the comparision and mismatches. Based on that the judges post their replies.

I am for stricter time limits for ICPC problems rather than current not publishing but very loose time limit.

In the award ceremony this year the scrolling ranklist with anumation showed all the details so they don't hide anything I guess. The reason why penalty of all teams is missing because after 12th place teams are ranked only by number of solved problems not by penalty. That is their policy of ranking not hiding infos.

Well the unoffocial judge data is put at the icpc live archive so that users can submit them and judge correctness. Do the online judges publish their online contest data? no, they do so to keep the judges alive. Similarly for being involved with UVa I prefer publishing them via ICPC live archive to keep it alive and give the contestants a real contest experience. That is why ICPC live archive was extablished. But I know it might not be a popular idea.
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
Well, talking about ICPC live archive I have two arguments.

First, this exactly archive (http://acmicpc-live-archive.uva.es/nuevoportal/) gives no chance for teams that use Java to solve problems because the whole UVA portal unfortunately lacks support of modern Java.

Second, does live archive really give you any contest feeling? When you solve problems and submit them to online judge you have completely different feeling from the real contest. As far as I know it currently has no "virtual contest" feature.

And finally, does publishing test cases really kill online judges? Say, Waterloo publishes everything, does it make their problems at online judges less valuable?

The contestant who really wishes to increase his performance would not look at the test cases. But the coach who would like to host a virtual contest for his team to see how it's result compares to the original results of the contest, cannot do it now.
Re: ICPC 2007 results??? (response to post by andrewzta) | Reply
Just to reiterate what I said at the coaches' briefing, one of several reasons I am advocating the publishing of official data is that it makes my job as a coach much easier.

Right now, I can name a handful of good contests that publish their data in a format that is usable for running a practice competition, with NWERC regionals and the Nordic contest being the best in terms of data format, problem quality and solution quality. NEERC is great, except for the multiple data files (which make it impossible to use PC^2 without major hacking) and the Pascal/Windows combination, but I can live with that.

The list of contests with good data is short, and the problem sets that would be most valuable are the world finals datasets. The ICPC live archive is a great resource, except for the 2 problems andrewzta mentioned - Java support and inability to simulate a contest.
Re: ICPC 2007 results??? (response to post by Abednego) | Reply
Codecraft released judge input and out files and the winning solutions.
Re: ICPC 2007 results??? (response to post by vexorian) | Reply
Boy, there was a lot of discussion (and recrimination) here while I was tooling around Japan. :)

The error on Problem J was very regrettable. We were extremely unlucky that it slipped through undetected. There are multiple eyes on every problem, which catch almost all the errors and ambiguities beforehand. And Petr's theory that we turn on automatic judging and fall asleep while the contest is running is false. ;) I wasn't the primary judge for the problem, but when the first run-time errors occurred I specifically examined the invalid case. However, it was a boundary case with no path from room 1 to the outside, and I assumed that was the cause for the crashes. Unfortunately I didn't look closely at the competitors' code, which tended to consist of large max-flow libraries. I had a lot of chances to catch the bad test case, and missed them all.

So, yes, I screwed up. And any mistake can seriously affect the results of the contest. However, Gordon's post did exaggerate the extent of the error. A small number of teams were affected, and the only symptom was that they were given Run-Time Error instead of Wrong Answer. Waterloo was probably the hardest hit, sadly. Most teams avoided J like the plague. :)

TopCoder is definitely NOT considerably more reliable than recent ICPC Finals. Back when I was a serious TC competitor, the error-per-question ratio was quite high. But as was pointed out, a mistake in the judge data or solution just isn't a big deal in Topcoder. At worst, it causes irregularities in the Challenge Phase. Usually, it just means a delay in System Testing. :)

Shahriar and I are both in favour of publishing official test data, but it's not up to us. Don't expect it to ever happen. It won't silence complaints, of course; people love to complain. I've done it often enough, myself!

Abednego, I see no problem with allowing coaches access to the "unofficial" UVA data set (which I'm assembling now) for practice purposes, even if Miguel Revilla doesn't want it published online. That should be good enough for your purposes. You can't simulate the Finals environment perfectly, anyway (for example, the UVA time limits are tighter).

David, your algorithm for J's a little different than mine, but I think it works. Nice job! My proof of correctness was ugly, too, though the solution makes intuitive sense. Maybe I'll post my proof somewhere.
Re: ICPC 2007 results??? (response to post by SnapDragon) | Reply
Well, I would never compare TopCoder and World Finals. These are different competitions with different rules, different contest organization and different responsibility.

Talking about publishing everything, we hear again (first from Shahriar, now from you):

Shahriar and I are both in favour of publishing official test data


Well, you are for, but somebody must be against, then. How do they motivate that? Maybe we all are missing something?
Re: ICPC 2007 results??? (response to post by SnapDragon) | Reply
--- And Petr's theory that we turn on automatic judging and fall asleep while the contest is running is false --

Hm, when you put it like that, it seems like I was quite over-energetic this morning. This was probably caused by the fact that I wasn't even invited to the coaches briefing (only on-site coaches were, and I'm the second coach for MSU) and didn't have a chance to hear your interpretation of the situation. I apologize for pushing the arguments to the edge.

We all understand that mistakes can, and will, happen. So probably we should now stop discussing the 'what was wrong with J' part. But there's some positive ('why not do this?', as opposed to negative, i.e. 'don't do this') idea in this thread, namely the suggestion to become more transparent by publishing test data, automating judging, etc. And probably you and broken_arrow are the only ones here who can really know why this is not happening, so we're trying to find out what, or who, is stopping that, and why. Sorry if it seems like we're accusing you of something :)

Probably anyone can at least explain that 'intuitive sense'? I don't see much.
Re: ICPC 2007 results??? (response to post by Petr) | Reply
It's no mystery as to who is against it. Dick Reinwalt is the head judge, and he has always refused to publish the data. I'm not sure what Bill Poucher's stance on this is because last year he issued a requirement that all regional contests submit their test data to the ICPC live archive. I don't think he made the distinction between "official" and "unofficial" data clear, and he placed no such requirement on the World Finals data.
Re: ICPC 2007 results??? (response to post by Petr) | Reply
Petr: I was only joking. :) I know you weren't really saying that.

I had no part in the coach briefing, either, so I don't know what was officially said.

My intuitive algorithm for J is to keep track of the current "cut number" of each node (how many edges you currently think are needed to trap the spy). Then you continually improve it by finding ways to corral the spy. Pick a node N and if, after cutting out all nodes with "cut number" <= x, the min-cut to the outside is y, you can improve N's "cut number" to x+y. It's clear that this gives you an upper bound, and ALMOST clear why the spy can defeat any strategy that uses fewer tunnels (he just probes edges to the outside, maintaining the invariant that he's in a node with larger "cut number" than your remaining cuts). There's just one annoying technical detail, which is showing that these min-cuts are disjoint: in other words, the edges you cut to force the spy into nodes with "cut number" x can't help you out later on, allowing you to corral him with fewer cuts.

Abednego: Wow, I didn't know Bill Poucher actually requires regionals to submit their data to the Live Archive. In that case, why NOT require that for the Finals?
Re: ICPC 2007 results??? (response to post by SnapDragon) | Reply
I didn't know Bill Poucher actually requires regionals to submit their data to the Live Archive

I doubt it is "required" - a lot of sets are not available (and I don't think they ever will be).
Re: ICPC 2007 results??? (response to post by darko_aleksic) | Reply
I'm just the Executive Director of an Academic Volunteer Community. So, each year I request that regional contests post their problems and test data which are captured for the ACM-ICPC Live Judge under the direction of Miguel Revilla. We also post the World Finals problems there along with test data.

The test data that is posted there is confidential for the most obvious reasons in the world. If you know the test data, then you can generally write a simple lookup program that returns the answers that have been calculated out in advance. That means those problems can't be used credibly until the test data is redone and secured.

Personally, I would prefer to see all original test data placed in the Live Judge system so others can compete with the champs. But, it is my responsibilty to discern the desire of the volunteers and follow that.

A lot of this will be moot over the next two years. Next year you will be able to watch the 2008 World Finals live coverage for an hour. We will show you what is going on as teams move toward the medals including the progress of runs as they go through judging. In 2009, it will be totally live. Of course the contest floor will be very restricted.

In terms of test data there are a lot of reasons for keeping it secure and a lot of reasons for revealing the results. The same is true about the judges' solutions. Much of our thinking focuses on maintaining the focus on what did happen - a new World Champ and 12 medalists - rather than what might have happened.

My sense is that we will go to a model in which each problem has a pair of roughly equivalent test data. We would commit one set to the OnLine Judge and make the other public. That way on-liners get to compete against the original data (at least a chunk) and those interested in examining data can do that. But, that is a decision for the ICPC EC.

In terms of defects in problem sets in the World Finals, there is an exhaustive process of reviewing and refining the problems and test data. I require that the judges solutions be exercised through a small version of the ICPC contest system to verify that all problems can be correctly judged correct. There are other scaled steps, but we do take the security of the problem set very seriously.

We have a policy of never having the same problem for the same reason. So when we run into a problem we try to improve our processes. In 2000, Problem F has a test data error that resulted in a disconnected graph appearing in the data set. A vertex was double entered. It was at the the end of a line as well as the beginning. Inspections by several missed it. The defect was masked by the fact that several solutions were submitted that did not rely on the graph being connected.

Unfortunately, the equipment had been packed and could not be unpacked to recalculate the results. So, I posted that there was a review in progress, had the equipment shipped to Baylor where we reconstructed the system and judged all of the problems with the corrected data. We then gave each team the highest standing of either interpretation of the outcome of the contest. Fortunately, the World Champion was the same for both.

We then changed our process to keep the necessary equipment in place so that we could rejudge if necessary anytime over the 12 hours that followed the end of the World Finals. We also instituted a number of other changes.

From 2001 to 2006 I am aware of no such defects. The error in 2007 was significant and nothing in our process would have caught the error. Nor would script generation of the test set caught the error since the differing bound would have appeared in the script.

We are going to make a change so that there can be an additional level of review, but I believe the problem is of the sort that occurs when extensive testing builds confidence, but the reality of the defect remains uncovered until discovered.

I will tell you that we have never had a more gifted and committed group of judges. If you want to be a judge, submit a great problem, validating you solution with the finest tools available. Submitted it to Dick Rinewalt or Jo Perry at http://icpc.baylor.edu/icpc/people. Don't give up, they get a LOT of submissions. You will need some character references too.

In terms of covering up problems, we work hard to keep teams focused on performance and the public focused on the team's excellence. Never have I knowingly participated in any coverup. In fact, I know of only one attempted coverup. Once I discovered it and we verified that it happened, we immediately reported and corrected for the defect as best we could. The responsible party no longer has that responsibility. That is the only think in the ICPC Community Culture that is not tolerated.

In terms of the defect in J, it was corrected and the submissions rejudged during the World Finals. That may be like reversing a play in football after your quarterback has been taken out of action, but sometimes it is the best we can do. I will say that the strategy of taking on J that was unsolved when there were other problems to do that had been solved by others was not a strategy I employed when I was coach.

My sense of the matter is this simple. We had extraordinarily talented teams at the 2007 World Finals. Fully 13 teams could have become champs. But the Warsaw University team was unbeatable. They solved 2 problems more than all teams but one. They solved one more problem than that second place team. Frankly, that achievement was given the spotlight that it deserved as were the tremendous accomplishments of all of the champions competing at the World Finals.

The Warsaw Eagles rule the ICPC Community of 1,756 universities in 82 countries for this next year. That is a fact.

After reviewing the statistics, I can see a compelling argument for Novosibirsk getting the Gold, Waterloo the Silver, and Petrozavodk State getting the Bronze. This was the most closely contested World Finals in history.

Novosobirsk 2 min behind Gold.
Waterloo 79 min behind Silver.
Petrozavodsk State -
solved same # of problems as teams in Gold, Silver, Bronze

What do you think? If I approved such changes or a subset of those changes, would that be a good thing or a bad thing? You might want to look at the ICPC P&P that govern our decision making. What should we do given our principles?

http://icpc.baylor.edu/icpc/info/ppgs.pdf


-- Bill
Re: ICPC 2007 results??? (response to post by icpc-bill) | Reply
Thanks for your post. I just wanted to point out that the link http://icpc.baylor.edu/people seems to be broken. What is the proper link?
Re: ICPC 2007 results??? (response to post by Minilek) | Reply
Thanks! I fixed it, jetlag and all!

http://icpc.baylor.edu/icpc/people

-- Bill
Re: ICPC 2007 results??? (response to post by icpc-bill) | Reply
Well, because you asked us - my vote goes to Petrozavodsk getting a medal, I felt really bad for them when their rank was announced.

I am not sure how I feel about increasing the number of gold medals. Maybe it is a good time for it, given the growth of ICPC - from what I understand there used to be three of each medal until relatively recently. And I know how I'd feel if I were 2 minutes short. OTOH you want gold to mean something, so I don't know...
Re: ICPC 2007 results??? (response to post by icpc-bill) | Reply

The test data that is posted there is confidential for the most obvious reasons in the world. If you know the test data, then you can generally write a simple lookup program that returns the answers that have been calculated out in advance.


And what? Does it really hurt anybody? That couple of people that would submit such solutions to live archive would only hurt themselves since they would actually NOT solve the problem and NOT learn anything.

I don't feel that it is better to do a double work thus increasing the probability of a mistake in at least one of the test sets.


In terms of test data there are a lot of reasons for keeping it secure and a lot of reasons for revealing the results. The same is true about the judges' solutions. Much of our thinking focuses on maintaining the focus on what did happen - a new World Champ and 12 medalists - rather than what might have happened.


You cannot run out of speculations. By making everything transparent you just make them pointless, everyone can see his mistakes and learn, community will still see the results and champs.


From 2001 to 2006 I am aware of no such defects. The error in 2007 was significant and nothing in our process would have caught the error. Nor would script generation of the test set caught the error since the differing bound would have appeared in the script.


Well, what we do, as Petr already mentioned, is including in the beginning of each solution, after reading input data, but before actually solving the problem, "a test check" a routine that checks all and every constraint specified in the problem statement, and reports any inconsistency. Yes, there can be a mistake in this check, but it is another measure that helps to avoid problems in test data.

And checking such simple constraints as "1 <= n && n <= 50" is easy and almost always correct.

Doing such checks in a solution rather than separate program gives the opportunity to run these checks by submitting solutions to the system when it is already ready for the contest and finding any errors that could have occurred when integrating test sets into the system, or introduced by last minute changes.
Re: ICPC 2007 results??? (response to post by icpc-bill) | Reply
I don't think that applying any changes to medal distribution is a good idea. Especially, increasing the number of gold medals. Because it would depreciate the value of other medals and establish a dangerous precedent.

Surely, it is a pity to lose gold medal for 2 penalty minutes. But this is sport. Novosibirsk team will have a chance to prove that they deserve gold in the next year. And 79 minutes of Waterloo is a huge amount in our days.

Concerning Petrozavodsk.. you can support them in the other way. For example, every year, in February and in August, they hosted a training camp. Initially, it was intended for Russian teams, but now it becomes international. Many World Champions (SPb IFMO-2004, Saratov-2006, Warsaw-2007) and a great number of medalists of ACM ICPC have participated in this camp. If one day you visit this camp, I think, it will be a great support and honor for Petrozavodsk university.
Re: ICPC 2007 results??? (response to post by Pawa) | Reply
Apologies for deviating from the topic. What is the requirement for attending this camp? Do they charge any fees? Is the medium of instruction in English?
Re: ICPC 2007 results??? (response to post by chamiya) | Reply
Sorry, I have no responsibility to answer such a question - I'm not from Petrozavodsk, but I've participated in this camp 7 times and really love it.

All I can do for you is to ask one of the Petrozavodsk officials to answer your question in this thread.
Re: ICPC 2007 results??? (response to post by icpc-bill) | Reply
Thanks a lot for your response. It does clarify many things.

I agree with andrewzta that not revealing the official data in order to prevent cheating on the Live Archive is an unfounded fear. Most teams use that website to practice and learn, and cheating is counterproductive and time-consuming.

If that is the main reason for creating two similar data sets, then why not publish the official one and submit the other one to the Live Archive? Then both problems would be solved - there will be the openness that many of us are asking for, and cheating on the Live Archive judge will be prevented.
Re: ICPC 2007 results??? (response to post by Abednego) | Reply
I think that problems that are from old contests, including those in the UVA site, should always come with a complete I/O. Specially UVA since statistics there don't really mean much but it is a great place to learn. Having two I/O sets would be really nice since it would prevent cheating but it would take the WA ghost away. I've seen too much problems that you won't really have a clue how to debug the WA, thus it is sometimes more about guessing than about learning.

And to be serious, UVA could even release the judge's I/O sets, if one really wanted to cheat he would just download the source of the solutions... There are plenty of sites with full cpp solutions...
Re: ICPC 2007 results??? (response to post by Abednego) | Reply
There are a number of reasons for not publishing. There are a number of reasons for publishing. Should judges publish their solutions? Is generating a test data set part of the solution?

Historically, the prevailing reason is simply that after all of the hard work going into the World Finals, a number of volunteers want the World Finals to be over once it has ended. It's easier to say no comment and get back to teaching, research, or the job and to get students to get their minds back on their studies.

That way those who would like to continue discussions can, but those who don't want to can avoid them. This is common in judging sports. After the event, the fans talk about it, the coaches talk about it, the athletes talk about it, but the refs and judges disappear.

Regardless, there is no consensus to change practices. But there is a consensus to make the World Finals more fun to watch, so I expect the practice to change over the next two years.

But that is just my opinion.

Bill
Re: ICPC 2007 results??? (response to post by icpc-bill) | Reply
It's great to see that Mr. Bill Poucher checks these forums. I guess, you must be aware to an extent about the poor quality of the indian regional contests.

Complaints against the 2005 Coimbatore contest and how to appeal:
http://acm.uva.es/board/viewtopic.php?p=41545&sid=a0f49767babe7e403b33fbe465aa137a

All problems stolen in 2006:
http://acm.uva.es/board/viewtopic.php?t=13315&highlight=coimbatore&sid=02af999f9e4c0378fad2824663e773ab

World-finals judges already *have* complained about the indian contests:
http://forums.topcoder.com/?module=Thread&threadID=568887&start=60&mc=70#774734

Even about the Kanpur regional contests, it is of relatively low quality than the regionals else where. By poor quality, i don't just mean that the problems are too simple to solve. A problem set is poor when:

1) The constraints are very badly described (or) Insufficient constraints.
1.1) Judge solutions rely on harder restrictions on the input than the one that is currently mentioned or a restriction is not mentioned at all. Eg, If a constraint is missing for a variable, we tend to only assume that it fits into a 32-bit integer. Not anything more strict. But unfortunately more stricter assumptions are let to pass.

eg: Problem #D IIT Kanpur region 2007.
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3767
Since no constraints are stated in this problem, the assumption is that the numbers can be as large as the limit on 32-bit integers, and their product is no way going to fit a 64-bit integer. Making this assumption, i had written a backtrack based on factoring the numbers into prime factors and maintaining the count of power of each prime. It took me 50 minutes to complete while i saw teams getting it accepted in 20 mins with the usual multiplication check. I know that even my implementation shouldn't have passed, i assumed all prime-factors were less than 10^5 which was incorrect (or not mentioned in the problem).

1.2) Test data is too poor. Now when a tricky statement is made, in a problem, by seeing the world-finals problems etc, we learn to believe that, assume only what it means - Nothing more, nothing less. Again, expecting us to assume more out of a statement as 'probably' is a bit too much.

eg: Problem #F IIT Kanpur region 2007.
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3769
This problem clearly calls the input numbers as 'roll numbers'; It is disappointing to note that the problem allowed assumptions of the form "roll numbers will be numbered between 1 and max(roll_no)"; I know it's not very hard to translate the input numbers from 1 to n, which i did, but why would someone have to do that, if only the problem had mentioned it.
Also my program which passed on this problem, i late found out that it had made another assumption:
"The input 3 numbers in the second line will be given in sorted order"
I know these assumptions are hard to kill during the design of the problem, but seeing the test-data of people like Derek Kisman (i am not being sarcastic here, i really mean it, check out the last year's world-finals at the live-archive), it seems kicking out such solutions might not be impossible.

eg2: Problem #C IIT Kanpur region 2007.
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3766
This problem "xtc++" (ranked 2 at the regionals) found that their solution was timing out for the worst-case inputs in their local comp, but got it accepted by the judge.
Please note that N and K can be only between 1 and 10. Which makes the no of distinct possible valid inputs to be approximately 50. And you also know that the worst-case will occur only for N = 10, and K is around mid(N). And if you fail to provide that case, I feel, then it's really an error.

Also why does indian contests, not provide the test-data to the online archive consistently? Maybe they being aware of the above are one of the few reasons.

Yes, i did raise complaints about 3 problems on the Kanpur regionals 2007, which contained a total of 6 problems! I won the regionals this time, but i think, that it involved too much of hit n miss, trial n error, make assumptions, rush in your solution, Passed? Just be happy move to the next one :)

I'd finish this post very pessimistically if i did not mention that everything except the problem set at Amrita Coimbatore wonderful, and i'm pretty sure everyone will agree with me here. In terms of organization, the amount of care they take, the value they give to feedback, and finally the food! [:)]

I'm not sure what you can do about this 'problems and test-cases part'. IMO, IIT Bombay have been doing well in the past, IIT Madras is interested in taking it up, and they seem to be promising that they can do well if given a chance. I know anything cant change suddenly, i'm hoping to see a gradual change. The best thing to happen is that a problem-setters like derek kisman who is writing the Bangladesh region, (though he is an European), must be allowed to write contest for our region. People in academic institutions don't seem to understand complaints of the form, your constraints are not fully specified. "So?" is the natural response.

Thank you bill anyway! The organization of the world-finals were better than great! :)

To topcoders: I could not find how to solve this ... Can anyone give me an approach on this problem?
Problem #B IIT Kanpur 07:
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3765
I think a back-track written well, to generate the edges and memoize on the current number must work, but i'm not sure why it should in worst-case. But i'm almost sure it'd have worked for the regional contest had i sent one in ;)
Re: ICPC 2007 results??? (response to post by myprasanna) | Reply
I think when I complain about indian regional I am just an ordinary contest related person. there should not be any extra weight or reference that I am a "World Finals Judge". That just puts that post in dispute.

If the coaches file official complains that is more important. Actually I was not supposed to do the complains any how if the coaches did their duty.

The main reason for my posts in this thread is to save the judges from dispute not to bring them into dispute.
Re: ICPC 2007 results??? (response to post by myprasanna) | Reply
The regionals are done by the universities in the region. We are as regionally autonomous as we can possibly be.

Universities in India are relatively new to the contest. The best way to make these contests better is to volunteer. Go to http://icpc.baylor.edu/icpc/people and contact the Asia site directors and offer your services.

You do have to be careful. I did that in 1983. It can really grow on you.

-- Bill
Re: ICPC 2007 results??? (response to post by icpc-bill) | Reply
IIT Kanpur (Contest Director Prof. Phalguni Gupta) has been doing it since 1999. So it is not new.

Finding good problem setters in India should not be difficult. If some one searches at topcoder he will find that there are 47 yellow coders and one red from india and I am sure not all of them are now eligible to participate in ICPC and also some of them live in India. So if some of them are asked for help it will be a great problemset. Whenever I run out of problems in Bangladesh I do just that ask the retired contestants (whom I know very well) and they do a fine job.

Conventional approach like asking only computer science faculty members without experience of contest will not work at least in the sub continent. But as long as someone is not asking for advice it is hard for me to give the advice.

Edit: It was a pleasant surprise to see prof. Poucher in this forum though :).
Re: ICPC 2007 results??? (response to post by myprasanna) | Reply
...derek kisman who is writing the Bangladesh region, (though he is an European)
I've always thought that SnapDragon is Canadian.
Re: ICPC 2007 results??? (response to post by ilham) | Reply
Isn't that next to France?
Re: ICPC 2007 results??? (response to post by slex) | Reply
Linguistically speaking, maybe, though geographically speaking UK is slightly closer to Canada ;)
Re: ICPC 2007 results??? (response to post by slex) | Reply
Nope, Denmark.
Re: ICPC 2007 results??? (response to post by icpc-bill) | Reply
So, each year I request that regional contests post their problems and test data which are captured for the ACM-ICPC Live Judge under the direction of Miguel Revilla. We also post the World Finals problems there along with test data.


That is probably great for the C/C++ teams out there, but the Java support on the judge is way too horrible to really practice on. You spend way more time fighting the compiler and restrictions than actually solving the problem.

If the judge would fix it's Java support (it's been promised for as long as I can remember), I wouldn't mind not having access to the test data nearly as much. The way it is now however, really limits the amount of good problems to practice on.
Re: ICPC 2007 results??? (response to post by Im2Good) | Reply
I will look into this. The On-line judge should support the latest version of Java.
Re: ICPC 2007 results??? (response to post by icpc-bill) | Reply

The error in 2007 was significant and nothing in our process would have caught the error. Nor would script generation of the test set caught the error since the differing bound would have appeared in the script.

What we do in the Polish Olympiad is for each problem to have a separate test format checker. The checker will check all constraints, including the number of spaces in the input and ranges for each number. This has worked very well in the past.

Writing such a checker is a very quick and easy process, especially given a small library with functions such as "read a space", "read an input in range [a,b]", etc. For most problems it's no more work than specifying the number ranges and input layout.

It would be close to impossible for the error in J (number out of specified range) to go past such a checker, since the author of the checker would consult the problem statement for the range of each number.

I would be willing to help create some such framework, if necessary.
Re: ICPC 2007 results??? (response to post by tomek) | Reply
I didn't "write" the Dhaka regionals; Shahriar just sends me the problems to test-solve. I'd be willing to do that for other regionals, as well, if they ask. However, from the sounds of it the Indian regionals were beyond the help of a simple test-solve. Especially a humble Canadian European French Danish test-solver like myself. :P

tomek, andrewzta: yes, an automatic input checker is a good idea. If I'm a judge again next year, my intention is to write one for all the problems. It would definitely have prevented this particular error...

Thanks, Prof. Poucher, for the informative post! One important note: the Live Archive does NOT get the official judge data, which is one of our primary complaints. Prior to 2006, the data at the Live Archive was produced by random good samaritans. For the 2006 Finals (and 2007), Shahriar and I produced our best attempt at a data set based on our knowledge of the problems, but it's not perfect. I would love it if the Live Archive did get the official data!
Re: ICPC 2007 results??? (response to post by SnapDragon) | Reply
You bet. You are right. The actual data is archived. We have discussed having an on-line contest with the previous year's problem set using the actual data as a warmup, but have never implemented it.

That is possible at some future time, but what makes these problems accessible are great volunteers like you and Shariar. I was just expressing a personal sentiment when I said:

"Personally, I would prefer to see all original test data placed in the Live Judge system so others can compete with the champs. But, it is my responsibilty to discern the desire of the volunteers and follow that."

I have to be very careful not to "dumb down" the ICPC by imposing on the ICPC Community volunteers. My view of my role is to make sure that the ICPC is valuable and fun for all.

By the way, I started thinking about strategy. Gordon's teams shoot for the World Championship. Since the championship is often settled by a problem that only one a small number of teams solved so it's probably really good strategy to go after a straggler. He is one of the best coaches in the world as are Waterloo teams, certainly better than me.

I've got to get back to focusing on my classes so thanks for all you have done as well as so many who have fun on this forum.

-- Bill
Re: ICPC 2007 results??? (response to post by SnapDragon) | Reply
Just to adjust some credits:
In 2006 and 2007 derek has done 80% data preparation and me rest 20% (Yet to be done).

I was one of the random good samaritans in 2003 and 2004 but who was in 2005?
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
Bill,

I think that having on-line coverage would be great. Such coverage should include expert analysis by somebody familiar with the problems and their solutions.

But I still think that a presentation of the problems and solutions would be interesting and educational for the participants. I don't see why on-line coverage would obviate it.

By the way, I have corresponded with Sean Silcoff who reported on the 2000 contest and he has several suggestions for how to make the contest a better spectator event, taking the lead from such current phenomena as TV and internet poker. I will send it to you if you like. (Silcoff's article: http://www.canadianbusiness.com/article.jsp?content=10326 )

G
Re: ICPC 2007 results??? (response to post by Hurd) | Reply
If you think on-line coverage would be a good idea, you might be interested to know that we had a proof of concept for live coverage at NWERC 2006. You can download a wmv-file with the webcast from www.csc.kth.se/contest/nwerc if you are curious. It is interesting that you mention TV poker, as that, along with the TV station Eurosport, inspired Fredrik Niemelä and the other people working on the live coverage at NWERC. The scoreboard that we used inspired the new scoreboard at the WF in Tokyo, particularly we showed pending runs and resolved the runs from the last hour during the awards.

How successful on-line coverage will be depends a lot on the amount of information from the judge room that can safely be leaked during the contest. During NWERC the commentator had on-line contact with the judge room, and also there were interviews with judges during the contest.

What you see if you watch it can be improved in a number of ways, and adapting the idea to covering the World Finals in a way that is fair, secure, and entertaining will no doubt be a challange. But given that equipment and crew were gathered less than a week before the event and that most of the work was done in the last 48 hours preceding the contest, I think the people who conceived the idea and worked on it did a tremendous job!

There are some lulls during the broadcast, but one of the entertaining parts with a judge interview occurs about 2 hours and 39 minutes into the broadcast, so fast forward to that. Watching the entire thing after the fact is a bit mind numbing.

/Mikael Goldmann
Re: ICPC 2007 results??? (response to post by MikaelG) | Reply
Yes. That is the proof of concept and KTH is taking the lead in developing this component. It may well be that an "after" contest analysis of the problem set would be a good extension.

--Bill
Re: ICPC 2007 results??? (response to post by tomek) | Reply
If you made the error of checking bounds in the the checking script the defect would have gone as undetected as the double "the" I placed in my remark about the 2000 data set error. The checker is no better than the checker code.

Anyway, best wishes all!

Bill
Re: ICPC 2007 results??? (response to post by icpc-bill) | Reply
But if the person writing the checker is different from the person writing the test data aren't the chances of this happening slimmer?
Re: ICPC 2007 results??? (response to post by Minilek) | Reply
Even if it is the same person, my experience suggests that a checker will catch virtually all cases violating the specification, unless the specification is changed after the checker is written. Obviously a seperate person is even better.

For example, in the case of n out of bounds, it is quite possible to generate a test case that is too large, forgetting the bound, but it would take really bad luck to put 100 in the checker while seeing 50 in the statement, and even more bad luck to make both mistakes at the same time.

More often, I have found automatically many other own mistakes such as putting too many lines or an extra space at the end of a line, made either by hand or by an incorrect script. Actually I find that writing a checker makes generating test cases easier and more efficient, because I make such mistakes quite often and the checker gives me confidence about what I have generated.

A review process by another person is necessary for finding problem statement misunderstandings or ambiguities. Optimally, a reviewer would write another checker to test data independently (and this is what I have done many times too).

Edit: Errors in the output may be even more likely - thus the more independent solutions, the better - even some very slow, brute-force solutions. This is probably much more important for the reviewier than the input checking, but also much more difficult.
Re: ICPC 2007 results??? (response to post by tomek) | Reply
Also, I would say that a very likely cause of input (or output) violating the specification are the changes made in the process of refining the problemset. It is easy to forget to always change both the specification and the data, especially when you are in a hurry. So a input checker is very valuable.
Re: ICPC 2007 results??? (response to post by icpc-bill) | Reply
Bill,

Thank-you for responding.

I must take exception to your statement that nothing in your process would have caught the error. The error was very simple: the size of the test data exceeded the bounds stated in the problem.

If your standards of review included writing a program that checked the validity of the input data neither the 2000 nor the 2007 error would have escaped detection. Tom Verhoeff's well-known guidelines, and the guidelines in my region, mandate this level of checking.

Why does the World Final not?

regards,

Gordon
Re: ICPC 2007 results??? (response to post by Hurd) | Reply
Gordon,

I don't recall saying that. These are not my processes. They are the judges' processes. The ICPC relies on informed experts to do their portion of the business. There is an annual review at which problems were identified and processes are improved.

In terms of validity checkers, personally I prefer them. But, still an error can creep up in a validity checker that leads you to believe that it is doing its duty when it is not. A desk check by an expert is still the best source of detecting defects.

The validity checker can be a useful tool. I built test data set generators with bounds checkers for the problems that I submitted at the World Finals when I was a judge. In particular some scanned the source to build a test set to stress critical aspects of their code. The statement required that data be managed dynamically. So, I wanted to find out what happened at the extremes of their dynamic allocation policy. Building a validity checker for my test generator would have been a chore since it was dependent on the code that it checked.

Still, I believe that validity checkers would have reduced the risk of errors in 2000 and 2007, had they been valid themselves. But I have seen validity checkers mask errors. An example was a system that had been modified, but the validity checker had not. Since the statement was changed to have lower limits, the validity checker accepted invalid data. This is a variant on as old a problem in database as there is, consistency.

I publish Tom's guidelines and recommend them, but I do not require them. That violates the responsibility space of the expert team putting together the problems. I don't do that as practice.

I suspect that Derek and Shariar will advocate validity checkers within that group for those who doen't write them (if there are any - I don't know) and offer to do so.

Organizations get very stupid when one person tells others how to conduct their business. It also undermines the volunteerism that makes the ICPC so unique. All I ask is that we don't make the same mistake for the same reason twice. I would expect that the next defect will manifest itself differently.

-- Bill

-- Bill
Re: ICPC 2007 results??? (response to post by icpc-bill) | Reply
Bill,

I think he was referring to this post where you said "The error in 2007 was significant and nothing in our process would have caught the error.".
Re: ICPC 2007 results??? (response to post by icpc-bill) | Reply
Bill,

Thanks again for your response. I appreciate your efforts and, as you said in the original text of your message, the judging processes are not yours.

Indeed they are the judges' process and as such Dick Rinewalt and Jo Perry bear the responsibility for the lack of quality control and opacity of the judging and problem selection process. The guest judges suffer from lack of guidance and oversight, and the result is apparent.

As for checking programs, there's a utility called "Make" that handles the problem of inconsistencies between problem statements and checkers, as well as other version control issues. If these things were checked in to a repositority and appropriate builds were done, I daresay the chance of error would be reduced by orders of magnitude. Even a manual checklist -- of the sort used at ICPC registration -- would be better than nothing.

I would say that the same problem *has* occurred twice. Judge data has been used twice -- in 2000 and 2007 -- that did not meet the specification in the problem statement.

I think we are using a different definition of the word "protest." I don't think anybody who was at the coaches' briefing would say that I did not protest. I did not file any sort of formal appeal, assuming that's what you mean by protest, becasue there is no such process and because I believe strongly that the judges' decisions -- flawed or not -- should remain final.

Gordon

P.S. The judges' shyness notwithstanding, I believe they should be recognized in writing for the record. If a judge specifically asks to remain anonymous, OK, but that should not be the default.

P.P.S. I wish also to add my voice to those asking for an overview presentation of the problems and solutions. Participants would find this interesting and educational. It is done in several regions. The IOI prepares a booklet discussing the problems.
Re: ICPC 2007 results??? (response to post by Hurd) | Reply
G,
I would personally like to thank you for being associated with some initiatives after being an elected member of IOI scientefic committee, like (a) Working with IOI statistics (b) Intiative to hold a workshop at Germany (Will there be a second one in future?) (c) Publishing IOI syllabus.

However is there any guideline about good IOI problems and bad ones? I mean rather than mere guidelines some examples like "These are the problems that were rated very highly by us" or "These problems are not suitable for us" would be more preferable. For the local IOI problemsetters (who sets problems in national contests) this will also be useful.

-Shahriar
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
Shahriar,

We could, and perhaps should, start a whole new thread about IOI. The structure there is a bit different as it is a travelling road show, with every country having a great deal of autonomy in how they put together the contest.

The International Scientific Committee, of which Misof and I are members, attempts to put together some guidelines and standards for the makeup of problems, test sets, judging environment, and so on. But how closely these are followed -- indeed whether or not they are followed at all -- is up to the host country, with the effect that quality varies a lot from year to year. For example, in the first two years that I was a member of ISC, the host country has declined to show the ISC the final data or problem statements for review.

Many of the documents produced by the ISC over the years may be found here: http://olympiads.win.tue.nl/ioi/sc/index.html

Gordon

P.S. The conference to which Shahriar refers is http://www.bwinf.de/competition-workshop/ I don't know of any plans to repeat it, but I think it'd be a good idea.
Re: ICPC 2007 results??? (response to post by Hurd) | Reply
A new IOI discussion thread openned at. ICPC discussion continues here though.

http://forums.topcoder.com/?module=Thread&threadID=570284&start=0&mc=1#778518

I am quite ignorant about IOI though (Compared to ICPC). So I may ask some stupid questions in that thread.
Re: ICPC 2007 results??? (response to post by Hurd) | Reply
Gordon,

If all goes well, next year we are rolling out a portion of the play by play presentation module. It will require more security on the floor, but it will reveal a lot about the problems as they are being solved. I doubt that there will be a need for further problem review.

I agree that it is a good idea for problem submitters to provide verification checkers along with test data for their problems. Still, as long as a bound exists in three places (problem statement, judges' solutions, and bounds checker) there is a chance of inconsistency in any of them. It is the talent and commitment of all of the judges that gives us excellence.

In terms of the ICPC Judges, Jo and Dick continue to do an outstanding job of recruiting excellent judges and crafting near flawless problem sets for many years. It is healthy to give people their due.

I do agree with you that the judges' decisions should remain final. Still judges should have every opportunity to correct oversights. In 2000, it was the judges who made the final call on places.

Problem count was used to award medals before 2005. The restriction to 3 groups of 4 was to have a predictable number of plaques and ribbons. The matter of medals is a matter of honoring high performance. We decided to award one more Bronze Medal because it was deserved and a good thing to do.

-- Bill
Re: ICPC 2007 results??? (response to post by SnapDragon) | Reply
These are the lines that are used in latest new rcd guidelines (NewRCDNotebook2007.pdf emailed to all rcd, page 84 or fourth page from the last). So I think it is upto the regional contests and coaches to press their RCDs next year.

"Reporting requirements are described in the RCD Web Site. A report, the standings, and the problems are represented on web pages with the URLs stored at the RCD Web Site. Those pages are harvested into the ICPC archive by April 1 following the World Finals. The problem set includes both the problem statements and test data. The test data may vary in nature, but not in coverage from the data used at the contest."
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
Here are my original problem notes for J, including the technical proof of correctness of my algorithm. The Lemma is the hard part; it SEEMS obvious (especially if you tinker with the problem a bit), but is tricky to prove. Everything else is straightforward.

http://www.geocities.com/snapdragon64/tunnel-notes.txt
Re: ICPC 2007 results??? (response to post by Petr) | Reply
This was probably caused by the fact that I wasn't even invited to the coaches briefing (only on-site coaches were, and I'm the second coach for MSU) and didn't have a chance to hear your interpretation of the situation.

I went to the coaches briefing despite not being the coach for the KTH team, and there were no problems with that. 2005 and 2006 I went to the briefing as the "Assistant coach", and there were no problems with that. So next year, you could probably try to go. :)
Kudos to Derek and Shahriar (response to post by SnapDragon) | Reply
Derek,

You and Shahriar (and whoever the other anonymous judges are) get scant credit. You should get much more, and you should not apologize for the judging screwup. I believe that ICPC could easily redirect some of the time it spends recognizing the old boys in favour of recognizing you. And I find it shocking that there isn't even an acknowledgement of the guest judges by name, either at ICPC or for the permanent record.

In this case I know it was not your data that was wrong. What was wrong was the lack of oversight by the permanent judging committee. So I don't even blame whoever made the errant test case. Leaving judges to do "the best they can," to paraphrase Shahriar, is simply not good enough. An institution with 30 years history should have standards and safeguards that work properly without heroic efforts such as you apologize for not doing.

I want to make it clear that I have been the first person to speak at many post-contest coaches meetings. I have lauded the problem sets and judging as often as I have criticized. I was particularly upset this year as I thought that better oversight -- including the use of input checkers as discussed in 2000 -- had been put in place. Apparently not.

I am not -- and have never been -- in favour of revising standings after the fact. Bad calls happen and must be allowed to stand. However the NFL, NHL, NBA, etc. do not systematically destroy the instant replays of their bad calls. They are there for the world to see, and argue about. If these organizations are embarrassed, so be it.

In this particular case Waterloo erred by attempting J with the wrong algorithm. However, had they received "wrong answer" they might've realized their error and either moved on or come up with a correct solution. We'll never know. That's what happens with a bad call. You never know what the outcome might have been. My only aim in this protest is to encourage the organizers to put in place better QA procedures, and to be much more transparent, so as to improve the contest in future years.

I do not buy Bill's argument that the judges just want closure. Imposing closure by limiting information is the worst way to convince people to accept the outcome.

Gordon
Re: Kudos to Derek and Shahriar (response to post by Hurd) | Reply
The ICPC has a number of very gifted World Finals Judges. Gordon, you can read their names in the brochure. Once I get the smaller version back from the author, it will be posted in past. We have listed all of the volunteers in the brochure for three years.

It is the case that this year at opening ceremony, I shortened acknowledgments because the program had run long. I had planned to call out the names of the judges as they escorted the teams to the dais, but did not do that either. My attention was drawn toward integrating a new scoreboard into the ceremony.

Still, I don't think that any of them felt belittled in any way. They have their letter of appointment and the opportunity for us to corroborate their contributions. Furthermore, I plan to give them even more exposure in Queue Magazine this year.

I am for revising standings when there is substantial evidence to do so. We used to give the teams solving the most problems Gold, the teams solving the second most problems Silver, and the teams solving the third most problems Bronze. We changed to the current method so we could have a predictable number of medals on hand. I prefer to look for the natural breaks, a process well accepted in academia. So I polled a few groups about their thoughts on this matter. The result is that the medals stand as granted and Petovavodsk will receive a Bronze.

In terms of your protest, I actually never received a single email about this problem. Not one. I have no memory of ever not taking or requesting that corrective action be taken to remedy or improve the ICPC. We rolled out a play-by-play system at KTH this past fall that permits code inspection of close submissions and examines impacted test data. It is informative and permits catching defects that slipped through the problem and testing formulation process. That will be pretty transparent. You will watch it in HD. I am sure that the ICPC QA will be improved as it has every year. But at the end of the day, its the experts that make it happen.

Also, I have tried to give a number of views on how to end the contest with a focus on what was accomplished rather than shortcomings. My guess is that next year, spectators will see more, but that judges will not comment about the problems after the Coaches Briefing.

-- Bill
Re: Kudos to Derek and Shahriar (response to post by icpc-bill) | Reply
-- Petovavodsk will receive a Bronze. --

That's great!

EDIT. Yes, I'm biased.
Re: Kudos to Derek and Shahriar (response to post by Petr) | Reply
I really love Petrozavodsk team too, and I was really sorry that they did not receive a medal.

But it seems to me that if you put the rules, you must follow them.
Re: Kudos to Derek and Shahriar (response to post by icpc-bill) | Reply

I am for revising standings when there is substantial evidence to do so. We used to give the teams solving the most problems Gold, the teams solving the second most problems Silver, and the teams solving the third most problems Bronze.


Technically, I wouldn't say that you "used to" do it, it was only done twice - in 2000 and 2001. In 2002 the medals were awarded following 3,3,4 rule, and were awarded following 4,4,4 rule ever since then.
Re: Kudos to Derek and Shahriar (response to post by andrewzta) | Reply
Actually, it wasn't a 3-3-4 rule. It was a number-of-problems-solved rule. Teams tied with the winner for number solved were given gold; the next tier silver; the next tier bronze.

The issue isn't of burning importance to me, but I'd prefer *one* gold, *one* silver, and *one* bronze. I don't bother displaying Waterloo's medal certificates or plaques. I'm a bit tired of explaining how we came away with a bronze for tenth, or a silver for 5th, or a gold for 2nd. I consider gold, silver, and bronze as synonyms for first, second and third place, as does, I think, most of the world.

And I'd like to see non-podium finishers ranked. The artifical ties obscure many really good efforts. I recall, for example, that Michigan Techological University had a very strong start in Shanghai, leading all US teams with 3 problems solved. But they solved no more and ended up with the also-rans. A report of their problems solved and time would've recognized their achievement.
Re: Kudos to Derek and Shahriar (response to post by Hurd) | Reply
I would also prefer one gold, one silver and one bronze. The current sitation depreciates the value of medal.
Re: Kudos to Derek and Shahriar (response to post by marek.cygan) | Reply
I don't think that something can depreciate the value of your medal, Marek.

But I agree that the number of medals is too high. For example, our team (Moscow U) didn't done well at the recent finals (especially compared with our perfomance in NEERC) but we still recieve a bronze medal.

I think that one gold, two silver and 3 bronze medals will be enough.
Re: Kudos to Derek and Shahriar (response to post by marek.cygan) | Reply
Hey, saying that after dominating the contest is not fair! (jk)
edit) Anyway, congratulations on the great performance.. it was really jaw-dropping!
Re: Kudos to Derek and Shahriar (response to post by JongMan) | Reply
I'm sorry, but now I have the same opinion as before the contest, it is my opinion as a contestant. Most championship events of every sport discipline have one gold, one silver and one bronze medal. People connect silver medal with second place, which is not the case in ACM ICPC.
Re: Kudos to Derek and Shahriar (response to post by marek.cygan) | Reply
I think that the extra bronze medal, in violation of the rules, a purely subjective judgement "because they were so close", diminishes the value of those prizes. It says: we, the jury, have decided that the 2-minute victory is not really enough for us to recognize as a good enough victory.

Why not add to the rules "unless the difference is smaller than 10 minutes"? But then if it's 12 minutes next time it will probably not be convincing enough.

The reason I say it diminishes the value of the prizes is that the perception of the medals, instead of something the best teams fight for among each other, becomes something that the jury has the power to give out at their discretion.
Re: Kudos to Derek and Shahriar (response to post by marek.cygan) | Reply
Yeah, I understand your point and I was just joking. :)
Actually I agree with you - because I couldn't get near any medals in my previous finals and I want mooore teams to share this sentiment. (Evil grin)

(Do not [-] me! I'm still joking.)
ICPC Medals (response to post by JongMan) | Reply
Today, to win any ICPC medal you are in the 99.8 percentile of 6,099 teams representing 1,756 universities in 82 countries. Gold medals are at the 99.9 percentile level. That is an extraordinary accomplishment.

Currently we guarantee Gold to the top 4, Silver to the next four, and Bronze to the next four. Read the rules carefully and find where it says that we will not award additional Bronze medals.

The ICPC is governed by principles including putting people first and following the Golden Rule (good-will reciprocity). So, while we do all that we can to follow our rules, we will address a need after the fact if the circumstances warrant it within our ability to do so. I'm enabled to rule on such unforeseen circumstances.

In terms of medals, the most popular medal application was Gold for solving the most, Silver for solving the next most, and Bronze for solving the next most. This disregards variability, native language differences and provides clear granularity.

The problem was that the number of medals varied from a min of 1 to 1 for all. So, we took our Top Ten and assigned medals 3-3-4. As the ICPC grew from 24 teams at the World Finals to 88, and the regionals increased by a factor of 8, we felt like we were under recognizing excellence, a trait common in IT. So we expanded to 12 teams receiving medals in a 4-4-4 distribution.

Winning an ICPC medal puts you in the upper 99.8 percentile of 5,099 teams representing 1,756 universities in 82 countries competitng at 205 sites. Where as winning the World Championship in 1982 when Baylor won put you in the upper 99.25 percentile.

A number of us prefer the model of medal based on problems-solved only. So, given that 10 of the top 12 medal winners solved 6 problems and that only team 13 had solved 6 problems, the situation begged to be addressed by a microapplication of the favored method of applying medals by problem count.

I polled 40 volunteers with several hundreds of years of contest experience. The consensus was to acknowledge the accomplishment of team #13 with a bronze medal. A few preferred not to make the change. But, the chief judges supported it, the DRC supported it, several super regional directors supported it, and so forth. So, I made the award.

Personally, I believe that we will move toward giving certificates and medals while preserving the World Champion as being the 1 and only 1 of years competitors.

What I would like to do is assign teams performing at the same level of the team at the 99.8 percentile receive bronzes. Above that, teams would receive silver and gold in accordance with a natural break.

Teams in the block immediately below bronze would receive certificates "With High Honor". The next block would receive "With Honor". The remainder would receive "Honorable Mention."

We would publish the statistics as well as the standings. The statistics would show the scoring problem by problem for each team. In fact, we would provide a digital score board that could be run back and foward to see the teams performance at any point of the event.

What would be the result? Teams receiving 'Honorable Mention' would be in the top 2% of ICPC teams. Teams receiving "With Honor" would be in the top 1% of ICPC teams. Teams receiving "With High Honor" woudld be in the top 0.5% of ICPC teams. Bronze teams would be at 0.3%. Silver at 0.2% and Gold would be 0.1%. The World Champions would be #1 of all.

That is different than the Regionals because the regionals need to score to get into the World Finals. Rather it is a blend of the World Championship, the Medals of Championships, and the honors earned in academic diplomas.

-- Bill

P.S. One Gold, One Silver, One Bronze? We could do that. But if we are convinced that the arithmetic is accurate but the math is not accuate, then we would not be true to our love for understanding.
Re: ICPC Medals (response to post by icpc-bill) | Reply
P.S. One Gold, One Silver, One Bronze? We could do that. But if we are convinced that the arithmetic is accurate but the math is not accuate, then we would not be true to our love for understanding.


I do not understand why increasing number of teams has influence on the number of medals. I am not against giving additional certificates or "Honorable Mention".
Re: ICPC Medals (response to post by marek.cygan) | Reply
Well, talking about the medals, the current system with gold/silver/bronze is quite confusing. I read now and then in news about teams "winning ICPC" when they get gold medal, and "coming first and second" when they get gold and silver.

On the other side I can agree with Bill and others that say that there must be some reward for high-ranked teams at ICPC. Should all competition go for the top three places, the current growth rate would never be achieved.

The introduction of the medals system coincided with the huge expansion of ICPC coverage throughout the world, and I think that it gave additional motivation to such expansion.

But there are some controversial things implemented together with it, such as blurring the bottom of the standings table. Here I agree with Gordon that some (small, but who judges that?) achievements might be covered.
Re: ICPC Medals (response to post by icpc-bill) | Reply
I am really feeling happy for Petrozavodsk State Univ.! Congratulations to them!
Re: ICPC Medals (response to post by icpc-bill) | Reply
Just one comment on the "math" part:
With the current system of advancement from regionals the claims like 'Teams receiving "With Honor" would be in the top 1% of ICPC teams.' are in my opinion quite imprecise. No offense intended, but I would look for many of the real top 1% teams at places 3 to 10 in tough regions (think NEERC and CERC).

I understand that there are other reasons for having the current advancement rules -- as I see it, popularization of computer science in the weaker regions plays an important role here. I understand some of the motivation behind the advancement rules and I don't want to argue against them here. However, once you have such rules, claims like the one I highlighted above lose any scientific validity.
Re: ICPC Medals (response to post by misof) | Reply
Not quite 3 to 10 for NEERC, more of 13 to 20 :)
Re: ICPC Medals (response to post by misof) | Reply
I think we should be wary of the claim that any sporting event -- of which this is one -- measures much other than who happened to win. Of course, better teams have a higher chance of winning, but that's it.

ICPC and IOI do not have in their mission statements anything about trying to rank the prowess of competitors, or even about identifying the "best." Only TopCoder claims to do that.

The idea is, I think, to encourage and reward accomplishment at all levels. So I think it is way more important to give mid-ranked teams something to strive for than to worry about who gets what trinkets.

I wrote (with Munro, Vasiga and Kemkes) a paper about this, and about some organizational changes that both IOI and ICPC might consider. Unfortunately the journal version -- http://www.vtex.lt/informatics_in_education/htm/INFE071.htm -- seems no longer freely available. The conference version -- http://www.bwinf.de/competition-workshop/RevisedPapers/11_Cormack+_rev.pdf -- is essentially similar.
Re: ICPC Medals (response to post by misof) | Reply
More than this, some universities have more then one strong team, and only one of them advance to the World Finals. So, all talks about percentiles, in my opinion, are unjustified.

For example, to advance to the World Finals in Tokyo we have to beat another Moscow U team, NEERC-2005 champions and Bronze medalists of San Antonio-2006. We won NEERC-2006, and they finished 3rd. Don't they also deserved to be in 1% of the best ICPC teams?
Re: Kudos to Derek and Shahriar (response to post by marek.cygan) | Reply
Right - but it's still better than IOI.
Re: Kudos to Derek and Shahriar (response to post by Krzysan) | Reply
What's wrong with the IOI? IMHO, the medals at the IOI have a different purpose than the medals at the ACM finals. At the IOI the main purpose of the entire event is to encourage the participants, and to motivate them to pursue a career in computer science. And giving lots of kids awards is a good thing. (Plus there is still the "absolute winner" status at the top.) Maybe it's just the word "medal" that makes this seem inappropriate. Imagine giving out golden, silver and bronze certificates, with e.g. the silver one saying "this kid is among the top 75 young programmers in the entire world". Does it still seem wrong to you?
Re: Kudos to Derek and Shahriar (response to post by misof) | Reply
I don't like the idea that 50% or so (don't remember the exact number) of participants get "medals". Your suggestion to use the word "certificate" is fine.

I like ICPC's scheme better. While it's not olympic gold/silver/bronze, current thresholds make sense. Unlike IOI, a medal from ICPC does have value (a lot!), and that's what I pointed out in my previous post.
Re: Kudos to Derek and Shahriar (response to post by Krzysan) | Reply
Unlike IOI, a medal from ICPC does have value (a lot!), and that's what I pointed out in my previous post.


Any other achievements that you think don't have any value?
Re: Kudos to Derek and Shahriar (response to post by rusolis) | Reply
We're getting off-topic here, and I see little point in reiterating, so I'm going to stop with this post. To sum up my position, IOI, as misof pointed out, has different goals and I do appreciate it. However, any "competition" where half of participants get "medals" so that they wouldn't feel sorry is, IMHO, funny.
Detailed results! (response to post by andrewzta) | Reply
Thanks to ICPC organizers for posting the detailed results. They tell a much better story.
Re: Detailed results! (response to post by Hurd) | Reply
Wow! Yes, thank you very much.
Re: Kudos to Derek and Shahriar (response to post by andrewzta) | Reply
Thank you very much for this great step on making ICPC more clear.
Re: Kudos to Derek and Shahriar (response to post by andrewzta) | Reply
Oh no!, now everyone knows we didn't solve a problem at all, :).


Although as far as i remeber this is not the first time they publish the final results, in Shanghai they gave a sheet at the end of the prizing ceremony detailing the final results.
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
Now about human judging.


The PC^2 compares the two files and shows us the comparision and mismatches. Based on that the judges post their replies.


What if the answer is not unique (World Finals 2007 problemset featured such problems)? Isn't it where the human judging comes in? And if the judge must make a decision based on output from "diff" of his answer file and the contestant's output, I don't really think that there can be no place for a mistake.

But if the situation changed, I really appreciate it (but feel discouraged again that this is not public).
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
Well the unoffocial judge data is put at the icpc live archive so that users can submit them and judge correctness. Do the online judges publish their online contest data? no, they do so to keep the judges alive.


Yes, they don't publish for the same reason you mentioned. But ACM-ICPC is a different category. It's a "one time" contest, just like Bitwise07 and CodeCraft which were held a while ago. Usually, "one time" contest publish their test data and open some Judge solutions or Best solutions.

ACM-ICPC World Finals, IMHO, belong to this "one time" contest type. The "one time" contest doesn't suffer for "alive" problems you mentioned above when the judge data/solutions are published and the benefits of this openness are already posted in this thread.

Similarly for being involved with UVa I prefer publishing them via ICPC live archive to keep it alive and give the contestants a real contest experience. That is why ICPC live archive was extablished. But I know it might not be a popular idea.


You intend to convert "one time" type contest to "online judge" type contest, and hence you hesitate to release the Judge Data.

Since you are very eager to create "unofficial data", especially for great contest such as ACM-ICPC, why don't you use your "unofficial data" for the the Live Archive online judge, and publish the World Final Judge data instead?

This way, you can publish the Judge Data of the World Final without suffering the "alive" problems of the Live Archive online judge :)
Re: ICPC 2007 results??? (response to post by felix_halim) | Reply
Well I cannot decide to publish the official data because I don't have many of them and also don't have the authority. I can just create some unofficial ones that fits for UVa. and ofcourse cannot create all, has to ask Kisman for the rest of the data.
Re: ICPC 2007 results??? (response to post by Petr) | Reply
duplicate - deleted.
Re: ICPC 2007 results??? (response to post by Petr) | Reply
Well I did not attempt to compare ICPC and topcoder in any way it was what aussie's post did. And then I just pointed out a big mistake made by topcoder in 2002 to prove that everyone makes mistake.

I am not related to ICPC in administrative way (You won't find my name in the ICPC page). If you have any complains about DHaka regional problem that is only what I can deal with. I am not liable nor apologize on what Bill does. Even I have made complains about indian regionals to many people and got no feedback.

But I guess the main objective of ICPC is its growth to different countries and so they overlook regional lapses. And really during regionals 300 problems are produced within two months. The world on average don't have the quality to do this that is why it is hard o maintain the quality of regionals.

I personally do not support the idea of not publishing data. But the idea of not publishing data does not make me or other judges less careful in ensuring the correctness of the problems and that is what I was trying to say. May be I won't be a judge next year any way so I cannot influence on decision making issues.

-Shahriar Manzoor
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
You're right, I haven't had anything to do with the world finals personally, so I'm judging them partially on my experience with the ICPC South Pacific regional (though I would certainly expect the world finals to be run to a higher standard).
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
That's funny, I was nearly going to use that as an example of how TopCoder handles mistakes that they do make better than ICPC does :). While ICPC often seems to just pretend that there was no mistake at all, TopCoder admitted there was a problem and re-ran the match.
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 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 darko_aleksic) | Reply
It is business-oriented, why do you think IBM keeps pumping money into it?


With an interview you get a short amount of time to both test and impress candidates to come to your company. At an event like the ICPC IBM has several days of interaction with the competitors to try to convince them to work for them. They haven't been making any money off of the world finals problems, test data, or solutions thus far, and I'd be surprised if they even owned the rights to these items. (EDIT: And to add-on, just being able to say that you're the sponsor of the premier university-level programming competition in the world is good PR)

Sure, the sponsors come into the deal from a business-minded perspective, but ACM and the other ICPC volunteers have purely academic interest. So my question still stands: why aren't solutions released? I see solutions being released only helping the community.
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 Petr) | Reply
We also go through the same process that you talked about NEERC to ensure correctness or do even more (The author do not only make the judge data someone else also makes it and then they are cimpared). I don't want to go into explanation still how that mistake in J remained, in a public forum because I am not a official representative to talk in a public forum.
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
I didn't talk about problem preparation, I was talking about the actual contest duration. So I don't quite get why you say 'even more'.

If you really do the same, didn't the Runtime Errors and Time Limits raise suspicion during the first hour of the contest? If you just looked at the wrong testcase you'd see immediately it violates the constraints, wouldn't you?
Re: ICPC 2007 results??? (response to post by Petr) | Reply
Sorry I misread your post and thought you draw all the test cases before the contest. In world finals we never go to automatic mode. Always judge manually.

I think there is no point in saying that you run your regional contest without any mistake. We (Me, Kisman and some other local persons) run the dhaka regional without mistake from 2003-2006. Only in 2003 there were some minor ambiguities. But that record did not save us from being associated with mistakes in the world finals. Although we both runs error free regionals our process of maintining correctness is different.

Strange run time errors occur in World finals any way because there are many weak teams. And we don't get to see who the submitting team is and be cautious when a very good team is getting RE.

May be next year we will be more careful. Because no mistakes have occured in recent times in World Finals and this may be the first since I had been a judge in 2003.
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
I was not directly comparing WF with NEERC, nor was I saying that NEERC is perfect. I was just saying that at NEERC we try not to be too sure in our solutions and testcases, and explained what we do for that.

From your replies it seems like WF judges are themselves trapped in that 'traditions' thing. Can you tell your personal opinion - should the testcases and solutions be made public after the contest? And why yes/no? (EDIT. didn't see the other reply)

-- May be next year we will be more careful. --
That's exactly what's so bad about ICPC's refusal of public discussion. You can never tell what exactly is being done to make things better. Some judge (and many thanks to you for doing that) will discuss something but will never make any official statement. And that can easily be transformed into thinking that nothing is changing at all.
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
Strange run time errors occur in World finals any way because there are many weak teams.
I don't think 'many' seems to be the right word here :p
Anyway, one thing with ACM-ish contests is their real-time judging, which means any small problems suddenly become very large ones the longer it takes to fix them - it's a definite problem with the structure rather than organisers, unfortunately there doesn't seem any good way to fix it, so most ICPC/regionals are doomed to the occasional(?) bad problem.
Re: ICPC 2007 results??? (response to post by sql_lall) | Reply
I feel that realtime response is good because giving only one chance to get your solution accepted is a bit harsh. But as you said then creates more problem when the judge data is wrong.

And if only one chance is given then partial marking like IOI is required (That is my opinion :).
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
don't want to go into explanation still how that mistake in J remained, in a public forum because I am not a official representative to talk in a public forum.


Why not? You aren't getting any official recognition. Surely you aren't bound to a nondisclosure agreement. We are all dying to know how such a screw-up could have occurred. I know one data point. The problem was a "left-over" from last year, so managed to bypass the normal scrutiny. Wouldn't a thorough airing of what went wrong be the best way to prevent re-occurrence?
Re: ICPC 2007 results??? (response to post by Hurd) | Reply
World Finals judges have a certificate which can be counted as an official recognition. So offocial recognition is there.

Personally, I would prefer prof Dick Rinewalt or Jo Perry to say something about the problemset/judging in the prize giving ceremony because contestants and other judges are not present in the coaches briefing.

Bill:
Most of the judges hate the job of showing path for the contestants at the prize giving ceremony, they just don't dare to tell you :).
Re: ICPC 2007 results??? (response to post by Petr) | Reply
Maybe they cannot publish the test data because it contains bad language (for text problems) and pornography (for geometry problems).
Re: ICPC 2007 results??? (response to post by Eryx) | Reply
No, it's because many problem statements infringe on the ACM trademark by providing alternative meanings for the acronym.
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
It may be mentioned that there were no mistake in the problemset within the year 2001-2006.

Prove it.

After Gordon stormed out of the post-contest coaches' briefing, several coaches (mainly Fredrik Niemela, Jorge Hernandez and I) asked the head judge many of the questions that appear in this thread. His responses were pretty much the same to every question - "We apologize for the mistake on J and will try to be more careful in the future." I don't think that's good enough.

In my opinion, when there is a mistake in a problem, the responsibility lies with the writers of the alternate solutions as much as the original author, and in the case of the ICPC Finals, with the head judge, too, for setting the policies for handling these mistakes.

It is extremely difficult to make a bug-free contest. Every contest I have ever organized had at least one broken problem. Once, I had a mistake in a problem that had 2 alternate solutions. People think in similar ways and make the same mistakes, so mistakes will continue to happen. That's unavoidable.

What would help immensely is openness. I do not see a single reason why keeping the judge data secret is a good idea. I think Shahriar's "it's tradition" argument is silly, and the only real reason I see is that Dick Rinewalt (the head judge) wants to avoid arguments and discussion about the test data. Clearly, that strategy is not working.

At the same coaches' briefing, Dick mentioned that there is only a handful of test cases for each problem, and the outputs are checked by hand. To quote Fredrik, I believe that "computers are better at comparing strings". Perhaps another reason for the secrecy is that the judges are ashamed to admit they are still comparing outputs by eye? Well, that's not a secret anymore, so let's publish the official data.

Finally, huge thanks to SnapDragon and any other judges who have released their "unofficial" test data. To all of them I say, wouldn't it be nice if you didn't have to spend time making those unofficial test cases? I'm sure they would much rather release the official data.

I'm not even talking about the great value the data would have for the coaches who run practices, and the recognition that the judges deserve for making great problems.
Re: ICPC 2007 results??? (response to post by Abednego) | Reply
[offtopic]You look totally different in this new member photo! We are used to the old one :-([/offtopic].
Re: ICPC 2007 results??? (response to post by prunthaban) | Reply
I like his new member photo.</offtopic>
Re: ICPC 2007 results??? (response to post by mishastassen) | Reply
The new photo is necessary. Otherwise he is hard to recognize at finals. Sometimes I have behaved so rudely with him (I mean just ignore) because I simply did not recognize him :).
Re: ICPC 2007 results??? (response to post by Abednego) | Reply
My arguments are silly because they are not my arguments. Just whst I have heard over the years.

I have no idea about the coaches briefing because I wasn't present there so I cannot comment.

I cannot prove that all previous world finals were correct. But I can say that from 2004 almost all problems had three independent solutions by virtue of Derek. Also by publishing the official data we cannot proof that we are correct. Because then coaches may argue that we have altered the data before publishing.

This argument will continue but my point was that this mistake would have happened even if we published the data.

By this time you have understood that I am quite stubborn :). That's why I am associated with problemsetting for so long otherwise I would have quitted by a long distance by now.
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
...then coaches may argue that we have altered the data before publishing.

That would be a whole new level of nasty. I'm willing to trust the judges that the data files they post are official if they claim that to be so. Pardon me for using the word "silly" again, but it just seems to me that saying "We won't post the official data because we could just lie and alter it" is... well... silly. Besides, the whole point of releasing the official data is not so that we can find mistakes in it, but because openness and honesty are, as a general principle, a good thing.

This argument will continue but my point was that this mistake would have happened even if we published the data.

That's fine. Arguments are a good thing. They cause the truth to come out. Once again, I'm not saying that releasing the data will eliminate all mistakes. But it will greatly raise everyone's confidence and respect for this competition.

I've heard both Bill Poucher and Dick Rinewalt refer to the ICPC Finals judges as "scourges" of the competition. I know they are trying to be funny, but this is the wrong image to be proud of. I see them as a closed organization, unresponsive to criticism and resistant to change. That's probably not true, and a great way to change that image would be to become more open. Judges should be the servants of the competition [Fredrik's words], not scourges.

For example, to echo dgarthur's complaint, why not publish the guidelines for selecting the world finals problems? I have not submitted any problems for the world finals because it is a mystery to me how they get selected, and I'm not too eager to get entangled in what looks from the outside like a shady bureaucracy.
Re: ICPC 2007 results??? (response to post by Abednego) | Reply
So how far can you believe me :)

When I say this data is official you say you believe me but when I say problemset was correct for the last six years you need a proof....

I believe the publishing of judge data is more necessary for educational purposes rather than proving correctness. Because if you don't believe judges then there is no mean in participating in contests.

It is hard for me to believe that bureaucracy is involved in World Finals problem selection. Because when submitted problems for the first time and my problems were selected I did not know anyone of ICPC personally. When the evaluation of problemset is done then the author names are kept hidden from the evaluators. In most cases people give up after failing once. I also almost decided to stop submitting when my problems were not selected in 2006. But then suddenly in a reverse mood submitted almost a dozen this year.

I don't think there is any specific guideline about accepting problems in IOI or topcoder as well. I know many great problemsetters who have failed to get his problem accepted at IOI. It is very hard to define a good problem. So why blame ICPC only?
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
-- I believe the publishing of judge data is more necessary for educational purposes rather than proving correctness. Because if you don't believe judges then there is no mean in participating in contests. --

Test data having no errors is not an issue of believing, it's just an issue of facts. The only thing I can believe (and do believe) is that judges' put a lot of effort into removing those errors, but the only way to see that there's actually no error (or at least no error influencing my result) is checking it by myself against my solution.
Re: ICPC 2007 results??? (response to post by Abednego) | Reply
For example, to echo dgarthur's complaint, why not publish the guidelines for selecting the world finals problems? I have not submitted any problems for the world finals because it is a mystery to me how they get selected, and I'm not too eager to get entangled in what looks from the outside like a shady bureaucracy.

Just to clarify, I don't think there is anything shady or dishonest going on. I just don't agree with their tastes =)
Re: ICPC 2007 results??? (response to post by broken_arrow) | Reply
Even though aussie has already said it better than I could, for the record, I was *not* blaming Snap for any mistakes whatsoever.
Re: ICPC 2007 results??? (response to post by NeverMore) | Reply
Two years ago there was a similar discussion at the UVa board, you may be interested in reading it:
http://online-judge.uva.es/board/viewtopic.php?t=7934
Re: ICPC 2007 results??? (response to post by misof) | Reply
The link you provided to your IOI task analysis is broken. Is the document still available anywhere?

FYI, this was the link:

http://people.ksp.sk/~misof/ioi/tasks.html
Re: ICPC 2007 results??? (response to post by naguib) | Reply
I notice the contestant list here. There's a lot of familiar TopCoder names (eg. I have some suspicion who "Marek Cygan" is) - although it would be much more convenient if they'd include their handles on these things.
Re: ICPC 2007 results??? (response to post by jmzero) | Reply
There are a lot of topcoders there. One can notice ACRush and ardiankp then there are also a lot of names I could recognize from gcjla...

Some are also there as couches.

In fact, last SRM was a great chance to get some money since the usual winners were not in the town... :)

And yes, it would be really helpful if they did.
Re: ICPC 2007 results??? (response to post by vexorian) | Reply
Some are also there as couches.

I don't think anybody deserves that insult ;-)
Re: ICPC 2007 results??? (response to post by jmzero) | Reply
Check this
Re: ICPC 2007 results??? (response to post by jmzero) | Reply
Am I the only one who didn't know lars2520 coached a team?
Re: ICPC 2007 results??? (response to post by dskloet) | Reply
He didn't tell me either :)
RSS