New wait time system.

[euler]

* minor-tweak *

I think that should fix the problem. Let me know if you encounter any more.

[rlindley]

I have devised a solution validation system for PE which addresses the problem of cheaters using a solutions list. I don't think this system is too complicated nor too expensive in terms of time/space to be implemented on the PE website. The system would require designing all future problems with a built-in validation parameter. Existing problems (especially the more difficult ones) could also be retro-fitted with a validation parameter if desired, but it is not necessary to do so.

To demonstrate the system I will do a walk-through using Problem 1 as an example:

Currently Euler must maintain a solution data base which contains the answer to each problem and a user data base which contains the problems each user has solved. Among other things, the user data base is used to determine access rights to the problem threads in the forum.

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Problem 1 (original statement)

05 October 2001

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and
9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

Euler posts the problem and updates the solution data base to indicate that the answer to problem 1 is 233168.

A user solves the problem and enters the solution (233168).

Euler looks it up in the solution data base and verifies it is correct then updates the user data base to reflect that this user has solved problem 1, which also gives the user access to problem 1's thread in the forum.

Euler responds with a congratulatory message and offers a link to the problem thread.

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Problem 1 (with validation parameter)

05 October 2001

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and
9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below V for V = 1000.
(Be sure to parameterize your algorithm so that the value of V can be easily changed.)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

Euler posts the problem and updates the solution data base to indicate that the answer to problem 1 is 233168. But now, instead of a single entry in the solution data base, Euler enters a small table:

V : solution
-------------------------------
1000 : 233168
849 : 167594
943 : 207900
878 : 179669
777 : 140793 (I hope these are correct!)

The number of rows in the table need not be very large. (Five or six should be sufficient. For the sake of discussion I will use 5.) The values of V other than 1000 are chosen by Euler and are unknown to the user. (These challenge values of V should in general not make the problem more difficult than the original given value of V.)

A user solves the problem and enters the solution (233168).

Euler looks it up in the solution data base and verifies it is correct then updates the user data base to reflect that this user has solved problem 1 using the first value of V in the table (by setting an index = 1). This marks it as solved but not validated. Solved but not validated does NOT grant the user access to the problem thread.

Euler responds with a congratulatory message that the answer is correct, then Euler randomly picks one of the other values of V in the table and challenges the user to solve the problem again using the value of V selected by Euler. (At this time it should be stressed to the user that he needs to print the page or otherwise record his challenge value of V as he will not ever be given another challenge value.)

Then Euler updates the user data base to indicate which challenge value was selected for this user. (Just changing an index from 1 to n, where n is the row containing the challenge value should do the job.)

The user plugs the new value of V into his algorithm and responds with the correct answer. (This need not be immediate. In fact the user should be able to come back at any later time and enter his challenge answer.)

Euler looks at the user data base and sees that this user has solved this problem and is validating ( since 1 < index < 6). Euler looks up the proper row in the solution data base and verifies the challenge answer is correct. Then Euler sets this user's index for this problem to some large number (index = 100, say). This marks it as solved and validated, which also gives the user access to the problem thread.

Euler responds with a congratulatory message and offers a link to the problem thread.

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

Now let's see what this does:

It makes it very difficult for a single person to create a complete solutions list. Since he is only ever given one challenge value, he would have to have at least 4 different accounts or have at least 4 accomplices in order to get all the challenge values.

A user using a solutions list would become suspect since he would have many solved problems, but few validated problems.

It would discourage brute force solutions which take many hours or days since the user would know ahead of time that he is going to need to run it again with a different value of V to get full credit for the solution.

If the user is given his challenge value as an image (capthca), then it would stop automated attacks.


I realize there are going to be some inherent problems with this system. One problem would be that the forum threads would need to be policed to stop sharing of challenge values and challenge answers. I'm sure Euler and others will see many more problems with such a system. It is just an idea.

[ouid]

2 - Make everybody submit their solutions along with the answer? Do you have enough resources to do that? People could simply be forced to provide a solution (either code or explanation for the pen&paper fanatics) and solutions could be parsed randomly. You submit a fake solution? You're banned.

I'll try to translate this idea roughly:
"Did you use sort/uniq/vim for preprocessing input.txt data before feeding it to your program? Did forgot about it? You are banned"
"Did you solve this task with pen&paper and you don't have camera/scanner and you submit 'I DONT HAVE DAMNED CAMERA'? You are banned. No, we will not buy camera for you. Really."
"Did you solve this task with pen&paper, then entered explanation with some BIG typos so explanation became incorrect? You are banned "
"Did you solve this task with pen&paper, but I was stupid to understand explanation, and in bad mood, so I decided that you used scigen? You are banned"
"Did you provide program that use special features of your compiler, while our compiler doesn't have them? You are banned "
"Did you solve this problem by using excel, which contained a lot data from other problems(when you are lazy enough to clear list, it happens)? BANNED."
"Did you used your own library, which you forget to include in your submission? BANNED."
"Did you used a lot of tools to solve this task and forget to include some intermediate programs? Banned. "

Summary: Euler is not intended to be peer-reviewed scientific journal. Therefore requesting full solutions will destroy fun for lot of non-cheaters.

tl;dr: BAD, BAD idea.

[quilan]

<randomization of the inputs of PE problems>

While they could work for many problems, there are also a large number of PE problems that depend on a very strict input set. For example, consider Problem 236 (View Problem).

[rlindley]

quilan wrote:
While they could work for many problems, there are also a large number of PE problems that depend on a very strict input set. For example, consider Problem 236 (View Problem).

First of all, I said:

The system would require designing all future problems with a built-in validation parameter. Existing problems (especially the more difficult ones) could also be retro-fitted with a validation parameter if desired, but it is not necessary to do so.

I have not solved 236, nor have I even given it much thought since it is not the type of problem that appeals to me. However, without really knowing what is involved, I understand it to mean: find the 35 m's and give the largest as the answer. If this is the case, then the question could be rephrased from:

There are thirty-five m>1 for which this surprising result could have occurred, the smallest of which is 1476/1475.

What's the largest possible value of m?
Give your answer as a fraction reduced to its lowest terms, in the form u/v.

to:

There are thirty-five m>1 for which this surprising result could have occurred, the smallest of which is 1476/1475.

If these 35 m's are listed in increasing order, what is the V^th one in the list for V = 35.
(Be sure to parameterize your algorithm so that the value of V can be easily changed.)
Give your answer as a fraction reduced to its lowest terms, in the form u/v.

I'm sure the "team" can come up with very clever ways of parameterizing problems. I'm sure there are better ways to parameterize 236 than the above. In fact, the way I did it may not even make sense if I am not understanding the question correctly.

[hk]

@ rlindley:
We are happy with all suggestions made. They might help in the future if further adjustments to the website might become necessary.
However, currently the database reserves only one bit per problem per user to indicate if (s)he has solved the problem.
So the system you are suggesting would mean quite a change to the underlying database.
For the time being we would like to keep the current database without too much change.
But be sure that your suggestion will not be forgotten. At least not by me.

[rlindley]

@quilan:

I finally partially solved 236, but it was a struggle as usual. It turns out that my suggested validation system would work very well for this problem in my particular situation: I had a probable answer early on but my program was only finding 25 of the 35 m's. So I was not sure. I kept working but still have not been able to find all 35 with my program. The best I have been able to do so far is 33. So I finally tried my probable answer and it was correct. Under the validation system, knowing the correct answer would have told me I was on the right track, but would not have granted me access to the problem thread. Then, if the challenge value did not happen to be among my 33, I would have to completly solve the problem to find it before I would get credit for solving and validating.

From the problem thread, the two I am missing are the 5^th and 33^rd and I still don't know why my program is not finding these. The program is such a cobbled up mess right now that I probably won't try to find the bug since I already have credit for solving the problem.

So I got credit for solving the problem without having a complete solution, just as someone with a solutions list would.

[Rinick]

Why we need a score page where users are sorted by the number of problems they solved?

They will have no reason to cheat if we remove that page

[drsparky]

Yes, I think that the wait system is also not ideal. I've got an idea that will not only solve this problem, but another as well...

Unlock the threads on the problems again... BUT, only keep the most recent 100 posts. The old posts will be discarded. Then, we also introduce an "accept" and a "reject" button for each problem and define a number of trustworthy "checkers" (could be admins). The process will then be as follows:

1. Solve the problem writing code.
2. Enter your result and see whether you are "correct". If you are, you receive half a tick. You are now required to post your solution in the thread. All members will be able to see your solution and an "accept" and "reject" button will appear for the members with "checker" status that have already solved the problem.
3. A checker will look at the solution (maybe even run it) and click "accept", if the solution is okay (or "reject" it, if it is not). If the problem was accepted, the member will now receive full credit.

Using this technique we can get rid of the waiting system altogether, encourage dialogue between members on problems, get rid of cheaters and allow users to "brag" about their nifty solutions in the thread.

Comments?

[hk]

Comments?
Yes, we have been keeping track of the number of correct solutions that are submitted every day.
That number is between 1500 and 2000 every day.
Suppose you look 1 minute at a solution it means about 1800 minutes=30 hours to check all solutions entered per day.
That is a full time job for 3.5 men 7 days a week.

[drsparky]

Point taken... My idea does not scale well

(However, what about unlocking the problem threads and keeping the most recent 100 posts?)

[hk]

For what purpose?

[genious999]

(However, what about unlocking the problem threads and keeping the most recent 100 posts?)

That would allow everyone to post their solutions. However, I have definitely noticed that the best explanations for most of the problems are in the first few posts, so if they were deleted to let anyone post, it is highly unlikely that the new posts would explain the solution with the same quality as the first posts, which would defeat the purpose of having the threads in the first place.

[dan19]

Hi there.

It's been less than 4 hours since I registered on projecteuler.net, and I've already made myself acquainted with the wait time system. The news article from July, 21st, says:

It is our hope that this restriction more naturally reflects the increasing difficulty of the problems remaining and no genuine problem solver should ever experience the restriction.

I guess this isn't entirely true. It only takes me several minutes per problem right now, and I reached problem 25 after a couple of hours of work. It's a little bit frustrating to have to take a 25-hour break so soon. And my guess is, the next day I might experience this restriction again ((

[tharkun860]

Hi -

Could someone clue me in as to the time I need to wait between submitting answers? I've been trying to answer #36, and it's still telling me the answer is wrong. Also, is someone time-penalized for submitting a wrong answer?

tharkun860

[hk]

The time between successive guesses is 30 sec.
If the site says the answer is wrong then it is wrong. Otherwise you get some other response.

[zwuupeape]

Force everyone to post their submit their solution. All answers will be accepted, anyway; but if someone is suspect of cheating, you can have a look at his submissions and see if they're consistently "suspicious".

With that said, would you count looking at Sloane after spotting a pattern as cheating?

[elendiastarman]

About the only problem with that idea is that it would take far too much time for the staff here to look through all of the solutions, and they might be in alien languages, so to speak. I think these objections have already been made earlier anyway...

EDIT: Here are 3 posts related to this:

viewtopic.php?f=5&t=1599&st=0&sk=t&sd=a#p15689
The argument here is made against a whitelist, but it could be applied to your question.

viewtopic.php?f=5&t=1599&st=0&sk=t&sd=a&start=15#p15728
Your idea has already been proposed.

viewtopic.php?f=5&t=1599&st=0&sk=t&sd=a&start=30#p15924
Here was the response to it.

However, there is nothing else anywhere else in this topic specifically against your idea.

[quilan]

With that said, would you count looking at Sloane after spotting a pattern as cheating?

Well, it all depends upon what you're looking up... for example, if you plug in the first N answers to a problem, and use that to find the correct answer... well that's obviously cheating.

However, there are cases where you try to spot patterns in the way calculations work and having Sloane show what the pattern is can alleviate much guesswork. A recent example of which was for Problem 233 (View Problem) where I noted a pattern of prime numbers, but wasn't able to figure out what it was... turns out it was just primes that were

Expand

of the form 4n+1

. I could have eventually figured this out, but it was easy enough to look it up first. [Note -- I'm pretty sure it's not a spoiler for the problem... if it is, I can get rid of it].

I'd say for situations of the second type, it's allowable to use Sloane as a quick resource for the purpose it was intended -- to assist with identifying patterns.

[stijn263]

I don't like using Sloane, but that's mainly because I really really enjoy to find a pattern myself But all new problems are checked with Sloane, so you won't find the direct pattern there. However sometimes relevant subpatterns are in Sloane or the pattern is entered later.

Anyways, I think the best solution to this "cheating" problem, is to remove the score list. If you really want a competition, try to be the first one to post in the topic of a new problem