OJ Board

Preventing cheating

Background
Most of the ranking lists are filled with entries such as:
1 0:00.000 64 A. Ellertsen C 2004/07/24-04:00:30.664 2703157 (H0)

If this had been done without cheating, it would have been impressive!
Unfortunately, as most of you know, getting such results are not done by actually solving the problem. The cheater has the correct answers in advance, and is just printing them without doing any computation. The cheater may have gotten the answer in various ways, e.g. output from contests, or trial and error.

The problem
Devise an algorithm such that this strategy always will fail, while ensuring no legitimate program is ever marked as a cheating one.

Input
1. A program which prints the correct answers for all the questions.
2. A program which prints the correct answers for all the questions, but is using the cheating strategy.

Output
1. Return "Accepted Answer"
2. Return "Wrong Answer". Mark the person using the strategy as a cheater.

Hints
To ensure the solution can be implemented with minimal cost, it must not require the judges to be provided with more sets of answers.


[Problemsetter's note] I suggest the ranking lists should be reset if a suitable solution is chosen.
As they are now, they are not good for anything anyway! (except showing off cheaters' names)

You have no idea what you are talking about. Just because you do everything in some forsaken interpreted language like Java, copy your algorithms straight out of a textbook without understanding them, and are jealous of people who really know how to program getting much faster times, does not mean they are cheaters. It means they are better programmers than you.

Look at the source code for your library; scanf() is 1200+ lines. Compare that to someone using fread() and a two line input routine accessing an array, and you have at least a 6000x (code is 600x shorter, and removing function call overhead is at least 10x faster) speed increase, and that is just on the I/O.

If someone is better them you, that does not make them wrong.

Andrew Neitsch wrote:You have no idea what you are talking about. Just because you do everything in some forsaken interpreted language like Java, copy your algorithms straight out of a textbook without understanding them, and are jealous of people who really know how to program getting much faster times, does not mean they are cheaters. It means they are better programmers than you.

Look at the source code for your library; scanf() is 1200+ lines. Compare that to someone using fread() and a two line input routine accessing an array, and you have at least a 6000x (code is 600x shorter, and removing function call overhead is at least 10x faster) speed increase, and that is just on the I/O.

If someone is better them you, that does not make them wrong.

Eh, _some_ people do cheat. Whether this is a big set or a small set of users is unknown (at least by me).

But I'm not too bothered by it, because I solve (most of) my problems, and if people want to cheat, then let them cheat.. they're only cheating themselves..

The reason why I care is that I think the ranking lists would be a cool thing to measure how fast you were able to solve a particular problem, and that's why I posted the post above.

There has been a question in the past whether precalculation is cheating or not. I believe precalculation is not cheating, but a valid way of solving a particular problem quickly. However, it's not usable in all cases, for example problem 10657. In that case, the problem space is virtually infinite, but the answer space is relatively small. To be exact, the answer space is 2^12.

Here's a simple C program that proves the judge expects 12 solutions.
[c]int main()
{
int x;
scanf("%i",&x);
if(x==12) while(1);
}
[/c]

2^12 is of course much larger than what's possible for a brute-force approach, but given that you know the correct algorithm to solve the problem, you may easily test each of the 12 answers whether it's a "Yes" or a "No". This can be done in the same manner as the above program, testing each answer, and going into an infinite loop or crashing the program depending on the result.

When you know all the answers, you can write a simple program which outputs each of the expected answers, without any calculation at all. To me, this is cheating.

My solution to the problem suggested above:
Run the accepted program again on the same data, only in a different order. If the program just outputs the exact same output as last time, it's an attempt to cheat. No legitimate program would ever do this. Neither would a program using a precalculation strategy. This can be implemented for many problem sets without the need of creating more solutions. Assuming most of the load on the servers are from programs that are not accepted, running an accepted program twice should not be a problem.


To Andrew Neitsch: You should think twice before flaming people. Your post don't need to be answered, as I believe everyone can see how stupid it is.

>To Andrew Neitsch: You should think twice before flaming people. Your
>post don't need to be answered, as I believe everyone can see how >stupid it is.

I said that if you don't know how to write fast programs, that does not make peope who do cheaters; and I didn't call you stupid. Jerk.

To Korken:

Wa, I am cheater!!!

If it's so easy, prove it. You do it what you say.

Der-Johng Sun

Let us cool ourselves every one.

The situation here is clear misunderstanding. What Korken said is true and Andrew Neitsch's claims are also valid.

There is enough evidence that some do cheat, however there are some good programmers who can reduce the runtime to great extent. The cheaters are "clouding" the efforts of the good programmers.

I'm sorry that this topic started out this way. I shouldn't have added the comment to Andrew in the end of my second post, it should have been taken to private messages right away, as I have done now. I apologize for that. I had the belief that it was common knowledge that cheating was possible, or else I would have been more explicit in my first post.

shamim wrote:The cheaters are "clouding" the efforts of the good programmers.

This is exactly what I'm getting at. It is very interesting to see how you really compare.

I consider many people here much better problemsolvers than myself, and I hope they will add their thoughts as how the problem may be solved.

Your 'solution' does not even solve the make-believe problem; if I know all the inputs and ouputs for a problem, and the judge permutes them, I just need my code to check which input it read, and print the solution.

The appropriate definition of cheating is "to violate rules deliberately." There are no rules on this site saying that brute force, or precomputed tables, or sending the released judge's solution from a local contest, or anything like that, is not allowed; so it is completely impossible for anyone to cheat.

Der-Johng Sun wrote:Wa, I am cheater!!!
If it's so easy, prove it. You do it what you say.

I can't prove that you are a cheater, and I doubt that you are. However, I can prove that I am a cheater!

Using this very simple program, I am able to climb to the top of the ranking list.

[c]int main()
{
printf("Case 1: X\n"
"Case 2: X\n"
"Case 3: X\n"
"Case 4: X\n"
"Case 5: X\n"
"Case 6: X\n"
"Case 7: X\n"
"Case 8: X\n"
"Case 9: X\n"
"Case 10: X\n"
"Case 11: X\n"
"Case 12: X\n");
}
[/c]

It is possible to argue that it's not possible to cheat when there are no rules, but as I said before, the ranking lists can be a useful tool to see how you compare. When it is very easy to cheat, they become useless.

I'm not saying the solution I gave above fits all problems, but it's an easy solution for this particular case (impossible to find test cases & easy to find solution given correct algorithm). If all the inputs and outputs are known, a way of removing the printf solution is to create some new inputs and outputs. Just one may even be sufficient. My point is that for many cases, it is very easy to make it difficult or impossible to cheat.

There are other ways to cheat as well, for example sharing the solution with your mates, but that won't make the algorithm any faster or more memory efficient, which is what I'm getting at here.