OJ Board

For a given input file, e.g. a file with a single byte 'a', there may be multiple shortest compressions. It seems like there should be a special judge. In the actual contest, no one solved this problem in 109 submissions, according to http://acm.up.pt/local/Historial/2003/stats-miup03.html
I suspect the local contest probably didn't have a special judge either.

No, that's not true. A single character can be outputted in only one way, and in general the shortest compression for any possible input is unique.

I fear something else went wrong while implemening this problem on the judge:
There can only be one inputfile. If the original dataset had multiple inputs, meant to be fed to the user program in separate runs of the judge, then concatenating them into one inpufile, will still result in just one case, because the user's program should treat the input as binary file, not as text file.
The output file should be treated as binary file by the judge, not as text file. Also the input file should not be converted from DOS to Unix, and no additional spaces and newlines should be added to it, unless the output is generated again.

There can be several possible minimal compressions.
Think of 129 times 'a'.
Then, we can encode it as:
[255]a[0]a
[254]a[129]a
...
[0]a[255]a

Yes, you're right. I was to hasty with my second conclusion.

So what did this mean?
Does every program with multiple answes need a special judge?

Will such a judge come or must we guess how the solution output is generated.

I am quite tiered of getting WA now.

I'd suggest not to waste more time on this problem until it's fixed. And I don't know if it is fixable at all, because I don't know if the judge can handle binary (non-text) files.

I forgot to say that I'm on the way.....I started it last sunday, but I couldn't finish it. Then I didn't have enough time during the week....I'll finish it as soon as I can.

By the way, little joey, can you mail me your solution? Judge handles binary files ok, but I'm afraid that ftp was made in ascii mode.....so judge's answer is not valid now

MaVa wrote:So what did this mean?
Does every program with multiple answes need a special judge?

Will such a judge come or must we guess how the solution output is generated.

Actually, it means that a special judge should be made for every problem that allows multiple answer. That special judge is usually made by the problemsetter, but, for problem 909, as we don't have it we have to make it. It was our gault that we didn't realize it was a multiple answer program before we put it online.

I've just finished it, I hope everything is ok now.