11119 - Chemical Attraction

luishhh · Post by **luishhh** » Tue Oct 17, 2006 6:31 pm

Hi all!
I saw this problem was one of the most difficult in the last contest... but actually I do not know why, because I've just sent my code for problem 11121 to the problem 11119 by mistake, and it was AC!!
It seems there is not only attraction between cations and anions but between any output and the judge's output

david · Post by **david** » Tue Oct 17, 2006 6:35 pm

Intention is what matters, as we all know...
Anyway this explains why nobody got WA during the contest, only AC, TLE and RE.

sclo · Post by **sclo** » Tue Oct 17, 2006 11:56 pm

Could someone please fix the correction program so that only CORRECT solutions will get AC. (There are some people solving it in 0.000 sec, which is nonsense). Anyway, this is a very nice problem.

I made some mistake in the implementation that caused some cycle which would TLE, I've fixed them now and can guarantee that the matching that I output is stable.

little joey · Post by **little joey** » Wed Oct 18, 2006 12:31 am

Yes, I just submitted a program that outputs nothing at all, and got Accepted

Since I wrote the problem, and the special judge, I mailed Carlos to look into this problem. The error will get corrected and the submissions rejudged. Be patient.

sclo · Post by **sclo** » Sun Oct 22, 2006 8:29 am

Finally, this problem has been rejudged. I wonder how come only 3 solutions (including mine) were correct.

little joey · Post by **little joey** » Sun Oct 22, 2006 11:39 am

I think you have to realise that Carlos is a busy person and has to find spare time to manage UVA, so 4 days is not something I would call 'finally'.
The fault is all mine: I had a misunderstanding of how a special judge works, so it was judging my (correct) sample solution instead of the output from the user's program

Currently, you are the only one who got accepted besides me (the problemsetter) and Derek (who wrote the alternative solution). That's probably because it is not an 'off the shelf' problem (although the algorithm is quite well known), and also I think most people don't like reading relatively long descriptions (too bad for them). I don't think it is because the judge contains a logical error: as you remarked yourself, once you have a candidate solution it is relatively easy to test the stabillity of the mixture.

fpmc · Post by **fpmc** » Sun Oct 22, 2006 11:24 pm

Hi Little Joey,

Nice problem. I tried many times yesterday to solve this problem. I used a standard algorithm that I have code for, but got wrong answer. Before I output the answer, I also check for validity of the solution by making sure that the mixture is stable before outputting it (otherwise do an assert(false)). I still got wrong answer after that...

I looked very carefully at my code, and I don't think my checker is wrong. I take whatever I am going to answer, check that the answer contains exactly N pairs, and exactly one of each type in the input, and then check that between each pair the compound is stable by your definition in the problem statement. Still... wrong answer.

Are you willing to check the judge again to see if there can be anything else wrong?

Thanks,
Frank

Abednego · Post by **Abednego** » Sun Oct 22, 2006 11:34 pm

I agree with Frank. I, too, have an assert() checking the stability at the end. Unless there is an evil boundary case that I'm not seeing, there is probably a mistake in the judge.

little joey · Post by **little joey** » Mon Oct 23, 2006 12:29 am

Could one of you, or both, PM me your code so I can run it agains the judge?

little joey · Post by **little joey** » Mon Oct 23, 2006 10:08 am

Thanks for your code guys.
Well, it looks like I messed it up again: the judge input contains duplicates because my generator is faulty

I'll fix it ASAP.

This problem is turning into a nightmare, and I should probably never try to set one again... Big apologies to everyone who wasted time over it here and during the contest.

Abednego · Post by **Abednego** » Mon Oct 23, 2006 2:39 pm

Oh no, don't say that! Just make sure you send me a copy before you add it to a contest. I'll write a sample solution. The square of the probabiliy of a mistake is fairly small.

shahriar_manzoor · Post by **shahriar_manzoor** » Mon Oct 23, 2006 3:07 pm

[to joey]
Problem setters have to be kind of shameless, you will make mistakes, feel sorry and start over again and I have done it 10/12 times. Actually I have a little fault of mine to share. Derek did not complain for this problem but he complained in some earlier problem of yours about your special judge being non-standard. I just fixed it myself without informing you. But this time no one complained. And not that all your special judges were wrong. At initial stages I also made mistakes writing special judges.

Actually while writing alternate solutions we rarely look at special judges correction but that is not to be done I see.

Abednego · Post by **Abednego** » Mon Oct 23, 2006 6:28 pm

UVa's special judge format is very nice, compared to the alternatives. PC^2 has the most idiotic special judge format imaginable. They define a "standard API" that they claim has been agreed to by multiple "teams" who implemented "similar contest systems". So they claim that it is an international standard. And then they add an extension to that "standard" that makes it incompatible with the original standard. The idea is that the extension should make the special judge more secure. In reality, it does absolutely nothing to prevent cheating.

After figuring out how their crazy XML-based judge format works (why XML!??!!?), I swore that I would never again do this. So I wrote my own judge API in C++. It is very simple because there are 3 functions: init(), Yes() and No(). First, you call init() and pass in your argc and argv. Then, if the team's answer is wrong, you call No(). If everything is correct, you call Yes(). There are 3 methods of compiling your judge: HUMAN, UVA and PC2. So I will never again have to deal with PC^2's "standard". (Until, of course, they release a new version. They like changing network protocols every time a minor version release comes out, so there is no guarantee they will not add another "security extension" to their judge API.)

Whew! That's my angry PC^2 rant. I can talk a lot about PC^2.

Anyway. If you want, here is my API and a simple example of using it to write a special judge:
http://shygypsy.com/acm/judge-api.cpp

shahriar_manzoor · Post by **shahriar_manzoor** » Mon Oct 23, 2006 6:55 pm

I am not an PC^2 expert, in Bangladesh someone else does that. Before Dhaka regional I asked one of them to mail me a sample PC^2 judge so that I can have some idea. I was so afraid to see that sample that I removed all special judge option in problems of Dhaka regional because there was not enough time to look for other options.

Yes UVa special judge is nice no doubt. But initially I made the mistake that programs that produced no output were also accepted which is a very easy mistake to make

. Also important thing to remember is that

a) judge must not print any output just return value

b) argv[1] is judge input file name and argv[2] is judge output file name and the contestant output comes into from standard input. Even if the special judge does not require input file still argv[1] is for judge input file name.

Just wanted to clear things up for anyone else interested.

About XML, yes we had long discussions in CII meeting about how to create XML standard for problemset sharing, and I don't understand why XML???

Also some regionals are very idle or afraid to publish data or put it in online judge so what is the point in creating new standards if no one follows the basic things. ICPC should make it must to publish data in some form then the mistakes in problemset will go away. This year I even saw a message in some regional not to disturb them asking for data, which I found amusing

.

Abednego · Post by **Abednego** » Mon Oct 23, 2006 7:05 pm

I remember that last year during the coaches' meeting at the World Finals, Bill Poucher announced that from now on, all regional contests must publish their data. I agree that this is a good thing. The funny thing is that he is refusing to publish the World Finals data, so we have to rely on Derek Kisman. (Big thanks to him.)

OJ Board

11119 - Chemical Attraction

11119 - Chemical Attraction

hmm

hmm