1 / 8
Oct 2004

Hi SPOJ DASM-Contest Team!

Looking at the incredibly impressive time at the "Relevant Phrases of Annihilation"-problem by top coder Tomek using a bash program after a ridiculous number of 24 submissions (most of them ACC with suspiciously varying run-times) we propose that different inputs should be used for final judgement in the contest.

ACM Student Chapter,
University Ulm

  • created

    Oct '04
  • last reply

    Oct '04
  • 7

    replies

  • 473

    views

  • 5

    users

I guess the input consists of only a few test cases, and tomek found out the answers for each input with "binary search" and different timing depending on if the guess was too low or too high.
Since there is nothing said that this is cheating, the method is ok. But in my opinion, there shouldn't be more points awarded to people at first position in the time ranklist for classical problems. Normally, I guess the algorithm used by the first one is not different than that of the following coders, only it is heavily optimized.

Tomek's method is in accordance with the rules. The only way of preventing such action is multiple testing on single test-cases, and this won't be available in SPOJ for another couple of weeks. Until then, introducing lots of test cases for new DASM problems becomes a necessity.

The only question that remains is: what should be done about the existing problemset for PHRASES (SOPARADE is not really a problem, since Pascal Zimmer's solution seems perfectly ok). Oh well, its my fault, so I guess I will have to think of a way out. I won't increase or change the test data, unless everybody who has solved the problem agree to this...

Doubling the score was used in previous editions of the league. This year, it doean't seem to be such a good idea. I guess the bonus will be removed or decreased starting from the second problemset onwards.

BTW. In the future, we are planning to use a slightly simplified version of the formula from the league to generate the main spoj ranking. The score will most certainly not be doubled there.

You don't have to change the testdata. A random permutation of the testcases of your judge input is enough to solve the problem of the problem.

This solves the problem only temporarily.
And increased testdata also won't help much if someone has great patience and/or uses automated binary search checking.
Everyone else could have used this method, only Tomek was the first to do it, so he deserves the first place on this problem (but as I said before, this shouldn't give more points).

I am glad to hear that smile

But a special judge which permutes the testcases and checks the permuted result is a solution for the dilemma of binary search input reconstruction.

To raise a point of order: Tomek was not the first to try this in the league, but the first to try it in the fight for first place wink.

Oh well: less of a fight for first place in the future will probably mean tougher problems. You asked for it smiling_imp.

Jokes aside, I will try to clarify/modify the rules and let everyone know ASAP.

I am sorry to hear that you feel that sending 24 submissions is "ridiculous" and that varying run-times are "suspiocious", and that my solution is cheating.

I thought it would be perfectly valid to send 24 submission and a bash program. The rules specifically say:

Also, I propose a slight addition to the rules - limit the number of submissions for a contest problem to, say, 128 submissions, in order to forbid flooding the server with thousands of submissions, which I may have inspired some people to do by my solution.