Clones of problem with public solution

[SourSpinach]

It seems to me like having problems with findable solutions isn't a big deal. As mentioned, this is already the case for many problems on SPOJ, and it's possible to find non-official solutions to (or discussions about) many more. I don't think it's exploited a whole lot, and if some people really do want to do that for some problems, I think it's impossible to prevent (due to the existence of so many such problems already) and isn't a big issue anyway.

It does make sense for people adding such problems to SPOJ to optionally consider altering the constraints, turning them into Challenge problems, or maybe not listing the source to make it more difficult to find solutions, but I don't think any such actions should be forced.

However, I really do like the idea of introducing a new category of problems, worth no points, with all submissions viewable by everyone (or, with an option to make your own submissions publicly viewable or not). This would give a new option for problems from past contests which some problem setters would probably like to use, and I think it would be a nice category for learning in general.

• Jacob Plachta

[dhinwa123]

@Francky @cyclops

As I had proposed my views in the light of reason of the current issue of clone of problems being not allowed due to cheating issue only. But as Francky says it is not, I am very much confused about agenda of the the issue. Please clarify your reasons about why not allow clone problems and why it will provide some benefit to spoj? I am totally kind of clueless about premise of discussion now.

[andypertamax]

Each possibility suggested before has some pros and cons

* New section where solutions are public
The problem with this is if you get points for solving these problems, a lot of user will just submit all of the problems without even understanding the solution. But if you don't get points, it's not much different than putting these problems in tutorial, still great for "bundling" purpose though (so they don't split between classical-tutorial).

* A rewording of description, and a problem code that doesn't link immediately to a 'solution'
I think this is good, but it requires some work (more so if you migrate the entire contest). Rewording a mostly straightforward problem is not easy either (many encryption problem).

* Change constraints to make a new problem, harder, so that public solutions won't pass
Some problems already have very good constraint that expanding them would lead to problems like biginteger or I/O optimization, which is totally unnecessary to make the problem harder. Also, some solutions are already very good that no matter how you increase the difficulty, the official solution would pass.

* Modify them as challenge problems, so 'public' solution will give few points, and good ones give real points
This is good especially for the competitive minded. I suggest everything equal or worse than the official solution gives 0 point, so only better solution can get points. However, this requires even more work from the problem setter than just rewording.

* Do nothing
It's ok to do nothing, but this encourages more cheaters (there are already a lot of them, but still).

Regardless of the choice, I think it's better to create a new section for contest problems. It makes it easier to find other problems in the contest, and also not clogging up the classical section with contest problem (not that there's anything wrong with it, but I prefer if the problem setter creates the problem himself). Other than what Francky posted above, I have some other suggestions:

*Make it self-sustaining
Basically user can add test data for the problem if there is at least an accepted solution that will not get accepted with the new test data (kinda like codeforces contest). This saves a lot of trouble for the problem setter. Implementing it might be hard though, since the site might have to be rebuilt to be able to do this. The other problem with this is if the official solution is not 100% correct, but that can be taken care of somewhat easily.

*Only accepted user can see the solution
But if the solution is already available somewhere why would this matter? Well for this to be effective than a difficulty increase might be necessary so that the official solution won't pass (this brings the same problem as of the earlier suggestion)

While the suggestion by all the people here is good, implementing it might not be so easy, especially for older problems. So at the end of the day, this might be up to the admins to decide.

[francky]

@Francky @cyclops

As I had proposed my views in the light of reason of the current issue of clone of problems being not allowed due to CHEATING ISSUE ONLY. But as Francky says it is not, I am very much confused about agenda of the the issue. Please clarify your reasons about why not allow clone problems and why it will provide some benefit to spoj? I am totally kind of clueless about premise of discussion now.

Please take time to read quietly.
1) Nobody wants problems not being allowed. Where did you read that? We want the best place for such collections at spoj, but maybe not in classical, nor tutorial.
2) It's not a pure cheating issue : what is the meaning of propose a problem for which the solution is "indicated" by the code ? At least if the problem-code wasn't related to the original contest, and maybe the title changed... (and, please do not use capitalizing ; it's like shouting).
The goal isn't to give more job to psetter, nor EB members, nor admins. We've got enough for sure.
3) Wouldn't it be nice if such collections were grouped and solutions public like the original contest?
4) And it would be useless to separate tutorial/serious ones, the group stay compact.
5) We are waiting for constructive propositions. Thanks in advance.

The answer will perhaps be : do nothing, but better is to ask for everyone's advice.

[dhinwa123]

@francky:
As you said it is not a pure cheating issue. So people will try solving the problem genuinely and having a reference for learning is always great. So it seems like they deserve as much as to be in classical than "actual" classical ones.

I still feel that most of the problems essentially achieve this status of having an editorial and a solution code/codes in some time. So only difference I see is the amount of time in that. Nowadays forums for problem discussion are not much active, so that might be a reason for more increase in duration of that.

Making a separate section with all solutions public in it, should be a great idea, But it is also highly suggested to have all the problems of a contest grouped by contest name itself. It will also be a great learning place. Currently some of the contests problems of spoj allow public viewing of the solutions, there interface of contest is excellent. It can be simply used for this purpose, only new thing is to do is to allow submissions on that.

There might be a slight issue of people not attempting those problems as they wont give any points to them and problem setter stop uploading the problems because of low attraction on their problems, or may be participation might increase due to grouping and public solutions available.

P.S. I was using capitalizing inter-changably with bolding of the words. As I was new to interface, so I was not acquainted with it:( . I am sorry if looked like shouting, I hope you understand that it was not the purpose.

[leppyr64]

I appreciate what you're up to francky.

I have remained silent on the topic (as well as the cheating topic) since it doesn't particularly interest me. I don't focus at all on the scores and helping people learn on the forum. If you look at my history you will notice that I don't solve a whole lot of problems on the main site, but others problems on the forum..

That being said, I do like the idea of having public viewable solutions for some problems. There is a lot of value in being able so see someone else's code and see how they solved the problem. I do not think that this should be done without the permission of the solver. It should be known that a solution would be public before the solver submits. Changing this parameter later should not change the private status of the solution. Many users have canned code that they would not want to make public (like my C# Fast Input method)

I also like the idea of having a repository of problems, such as USACO or GCJ. I don't personally set problems so I don't know how difficult or easy this would be, but it would really be frustrating to have a partial set of problems for a contest but not all of them.

Keep up the good work.

[francky]

We've received some more thoughts and I want to share :

Personally I'm no great fan of publicising clones of problems with publicly available solutions on the original website of
the problems. If people want to try them they can do so if they want.
I find it disturbing that so many participants seem to indulging on copying solutions from elsewhere and I find this
very demotivating.
In my opinion the classical set of problems should be entirely dedicated to original problems.
However, it's too late to adhere to that adagium as SPOJ has been flooded already with problems copied from elsewhere. I'm afraid there is no way back from the course that has been taken.
In my opinion the SPOJ problem set has grown to such an enormous size that no newcomer can ever achieve going through it and keep up with the deluge of new problems copied from elsewhere that a serious restriction on what further to publish would be healthy.

We perhaps can't do anything, it's true.

What are other propositions to improve the quality of SPOJ problem set ?
Please be constructive.

[ffao_sof]

It appears this topic is coming from the premise that problem clones are inherently a bad thing, which I do not consider to be true, so I'll give my opinion here:

You can either treat SPOJ as a competition in and of itself (as many of the people that solve lots and lots of problems do), or you can consider this to be a space for training with a huge problem collection, as seems to be the original intent (the first classical problems already have a lot of "clones" from other competitions, for example). Under that second perspective, "cheating" is a really silly thing to do, since you gain absolutely no knowledge from submitting other people's solutions, and the clones are a considerable benefit to the quality of SPOJ's problemset.

Having that said, the idea to split them into a different problemset for training purposes is great, and would satisfy pretty much everyone. Between having the problems and not having them at all, I like having the problems better.

[francky]

It appears this topic is coming from the premise that problem clones are inherently a bad thing, which I do not consider to be true (...)

Where did you find something that let you think that ????? Please be constructive, and don't make false assert, please.

• Problems with public solutions can't (for me) belongs to classical section, but I hope those problems can take a full good place in spoj. Tutorial section don't suit for that, everybody accord to that.
• Integrity of the whole set is very good, a new section for those contest-clone problems won't split the set anymore.
• For those where a public solution is available in the original contest site, I think we can't do anything else than : make all solutions public too for those problems, and/(or unless) don't give points for this set in the ranking system.
• spoj have a great educational purpose, we have to improve it : such a new section would well participate.
• The ranking system is not perfect but we can't destroy it. Those clones in classical threatened it.

[cyclops]

Thanks everyone for expressing your thoughts on the matter. I know it's a bit late, but here are my views:

I fully agree with Francky from a problem setter's point of view. Why would I ever set a problem where a simple or obvious search would lead immediately to a working solution that can be copied and pasted without even reading the problem? To me it doesn't make sense. I prefer to encourage original submissions. Of course it's always possible for an (inconsiderate) solver to publish his solution and allow others to cheat easily, but I certainly don't want this situation at time of problem publication. If that means extra work rewriting or redesigning a problem, I consider it well worth the effort.

As solver, I would like any problem to change as little as possible after it is published. There may be a petty aspect to it (in terms of recognition), but I dislike the result of my time and work "taken away". It's part of why I brought up grandfather clauses. (It seems fair not to change older problems, both for the solvers and the problem setters of those problems.) And I would also prefer not to have the rank lists of problems I've solved polluted by people who didn't solve the problem, but I recognise it as something I have very little control over (but the problem setter has a bit more control over it), and I usually don't pay much attention to that.

As EB member, I want a clear policy that I can follow without thinking overly hard about it, and that has some official statement somewhere so that I can refer any (unhappy) problem setter to look there as an explanation of my action. (And of course I don't want to enforce a policy I don't agree with.) For here, I think creating a new section for clone problems with publicly available source would improve the quality of SPOJ, and the idea I like best is to let users decide on a per-submission basis whether their source will be public, but it may take some time for admins to set this up (if they are agreeable to the idea).

Until now, we haven't brought admins into the discussion, because we wanted to hear opinions from the community and allow natural discussion. Now as it seems everyone interested enough to state their opinion has stated it, so we've emailed the admins and are waiting for their reply. Please hold tight a little longer. We would like to hear the admins' opinions on the best proper action to take with this issue at this point.

[dhinwa123]

Issue was of 2 March, Today we have 4 May, Entire 2 months have passed. Please take action regarding the issue.

[francky]

We had a very short answer from admins on 01/05/2014.
They are working hardly on interface, it takes many times, and answers will be provided after.
We have no other information to share.

[wisfaq]

Any news from the admins yet?

[dhinwa123]

It's been a quite a long time, I doubt that there will be any action over the issue, They have surely forgotten the issue and gone past that. I am also pretty sure that nobody is making sure that clone problems of the contests don't get added in the classical sets. It was only an exception for our contest problems. In my understanding of the issue, one of the editorial board members felt insulted when the author decided to not to tell him a test case. You can see the conversation in the IOPC_14A problems thread. Ideally in my opinion, author should have given the test case, but the decision of taking the problems down was really silly. I have already stated my opinions in this forum and problem page already.

Finally, I have little expectations from spoj admins. The issue in my humble opinion, was not that what editorial board members has made it. Nevertheless due to the incidence, at least I am not that motivated or in a mood of putting up any more problems on spoj regardless of the outcome of the issue. So for me, at least the things are settled. Thank you editorial members for all your replies, I really like to thank Mitch Schwartz for all his replies and fruitful discussions. I would like to say sorry to him if some error has been done on our side.

[kokosek]

Problems with public solutions:

• problems from other contests (like CodeChef, TopCoder, etc.)
• problems described on blogs
• codes available on e.g. GitHub, Ideone

Possible solutions that have been mentioned here and my own:

• leaving these problems in classical problemset
  Cons:
  [list][*]people can copy solutions from the web and get points which will decrease points and ranks of honest users

Pros:

• leaving valueable and profesionally made problems

[/*:m]
[li]making new, equivalent problems with new descriptions, titles and codes
Cons:

[*]big amount of work needed[/li]
[li]need of many Problem Setters or Editorial Board involvement[/li]
[li]users who post those codes can easily modify their codes or articles with little effort[/li]
[li]users may resubmit their codes when they realize that it's the same task as the one that has been deleted[/li]

Pros:

• problems of good quality are still available
• honest users will probably remember they have solved new problems and just resubmit their codes

[/*:m]
[li]changing problem constraints so that public solutions won't pass
Cons:

[*]it is very probable that user who posted their solution online has made a better code than 50% of users who solved the problem – that means that if we make his problem get WA/TLE/RE many honest users will loose points[/li]
[li]many problems already require a very good algorithm and making constraints won't be possible (without making optimal solutions get TLE/RE)[/li]
[li]users who solved such a problem in language like Python, Java, C# or Jostner will probably get TLE[/li]

Pros:

• problems will be of better quality (assuming that the more difficult problem is, the better it is)
• some solutions will become invalid

[/*:m]
[li]moving such problems to the tutorial problemset
Cons:

[*]these problems will attract less users as they won't get any points for them (and they might be interesting and Problem Setters who made them deserve to have them in classical problemset)[/li]
[li]honest users will loose even more points and indirectly loose time spent on these problems[/li]
[li]if users continue to upload their valid solutions to the internet, more and more good problems will end in tutorial problemset[/li]
[li]spam in the tutorial problemset - there will be easy problems (which is good) but also hard problems but with public solution; so if a user feel that a problem is too hard he'll assume there is a public solution and look for it instead of leaving the problem (the problemset will loose it's purpose)[/li]

Pros:

• dishonest users won't get points for copying codes for these problems

[/*:m]
[li]change them to challenge problems
Cons:

[*]huge amount of work needed[/li]
[li]need of many Problem Setters involved (Editorial Board can't modify tests)[/li]
[li]spam in the challenge problemset (not all problems suit to be a challenge)[/li]
[li]if users continue to upload their valid solutions to the internet, more and more good problems will end in challenge problemset[/li]
[li]if user with top solution published his code, making the problem a challenge won't change a thing[/li]

Pros:

• good problems will stay
• honest users will get more points than dishonest ones

[/*:m]
[li]ban users who copy published codes
Cons:

[*]assuming that users will report suspicious ones, admins will have to check their codes and look for them online (to make sure they ban for a reason)[/li]
[li]some users might have benefited from published articles and copied the code knowing what it does (and I talk about ones that first try to solve a problem on their own)[/li]

Pros:

• some cheaters will be banned
• users might be afraid to copy someone else's code as they can be banned
• problems will be left as they are

[/*:m]
[li]new section whit public solutions - solving a problem in this section would have to result in getting 0 points, as with tutorial problemset so this solution is equivalent to moving all problems in the tutorial section (except for the last con)[/li][/list:u]
The solution in my opinion should be:

• users should inform authors of problems if they think that some user pasted a code in their problem – then Problem Setter (if he's active and has time) can check suspect's code and look for it online; if he finds it – notify an admin in a special thread and the user will be banned
• leaving all past problems as they are (grandfather clauses, as cyclops mentioned)
• making a problemset „contests” or „from_contests” or even not making a problemset but entire contest in which there would be problems from other competitions
  [list][*]if separate contest – problemsets would be names of the competitions (e.g. IOPC 2013)
• if another problemset – problems would have prefixed in the titles with competition names (e.g. [IOPC2013] Title)

[/*:m]
[li]these problems would give no points[/li]
[li]this solution won't solve the problem of cheaters, though (except for maybe decreasing the number of problems in which one can cheat)[/li]
[li]perhaps, in the distant future, there can be an option „allow others to see your codes in problemset XXX” and users who tick this checkbox will be able to see codes of others in problems they got AC but others will also be able to see their codes[/li][/list:u]
But regarding the solution I agree with – I'm also a user on Polish SPOJ and there was a time that somebody made a new problemset with a title of some contest and moved all problems from this contest to this problemset (with 0 points for each problem). And I was (and am) against that. Because I and many users spend some time solving these problems and we thought that we earned the points. And even implementing cyclops's idea with leaving past problems as they are and adding only new ones to this problemset would not satisfy me if we were talking about SPOJPL. The reason I find this solution okay on main SPOJ is that there are already enough problems there and it won't hurt to give 0 points for some if they come from other contests. I'm saying it just for the sake of SPOJPL (we don't want any changes there, in my opinion).

[francky]

(...)
The solution in my opinion should be:

(...)

• leaving all past problems as they are (grandfather clauses, as cyclops mentioned)
• making a problemset „contests” or „from_contests” or even not making a problemset but entire contest in which there would be problems from other competitions
  [list][*]if separate contest – problemsets would be names of the competitions (e.g. IOPC 2013)
• if another problemset – problems would have prefixed in the titles with competition names (e.g. [IOPC2013] Title)

[/*:m]
[li]these problems would give no points[/li]
[li]this solution won't solve the problem of cheaters, though (except for maybe decreasing the number of problems in which one can cheat)[/li]
[li]perhaps, in the distant future, there can be an option „allow others to see your codes in problemset XXX” and users who tick this checkbox will be able to see codes of others in problems they got AC but others will also be able to see their codes[/li][/list:u]
But regarding the solution I agree with – I'm also a user on Polish SPOJ and there was a time that somebody made a new problemset with a title of some contest and moved all problems from this contest to this problemset (with 0 points for each problem). And I was (and am) against that. Because I and many users spend some time solving these problems and we thought that we earned the points. And even implementing cyclops's idea with leaving past problems as they are and adding only new ones to this problemset would not satisfy me if we were talking about SPOJPL. The reason I find this solution okay on main SPOJ is that there are already enough problems there and it won't hurt to give 0 points for some if they come from other contests. I'm saying it just for the sake of SPOJPL (we don't want any changes there, in my opinion).

I really hope this can be done easily.
Many thanks for this great answer.

[tjandra_sof]

I have another solution, in my opinion, how about leaving all clone problems in classical but making all clone problem worth 0 points for only those who copy other solution?

This can be checked after judging process using byte-by-byte (basic) comparation with every another user's accepted solution, if it match with another user's code, then he will get no points from this problem (considered unsolved problem) but only he will see that his (cheat) code get accepted. For example codeforces.com already implemented this "basic" code comparation technique, if there are two or more users submit exactly same code, they will get "skipped" verdict.

Of course this "basic" detector isn't perfect, user can still cheat by just renaming some variable, this detection can be perfected using edit-distance (advanced) comparation, if two code having edit-distance

Although "basic" detection still not perfect (it still have chance to cheat), it has been proven to reduce the many cheater on codeforces.com site (I've seen many "skipped" verdict there). If this "basic" detection is not enough it still possible to calculate the O(45 Billion) complexity in less than 1 second using parallel algorithm and enough processor available. Another option is to check similarity of two code using heuristic edit-distance with is much faster than general edit-distance but less strict detection (still better than "basic" detection). This solution need some SPOJ system change, but it's one of many possible solutions (solutions that has been described by francky and others above).

What do you think about this Solution?

[wisfaq]

I'm not sure if this is really a good solution for several reasons.
Reason 1:
In many languages you can change every return character (chr 10) or chr(13) with a random string of whitespace without affecting the code's working.
So it shouldn't be too difficult to change the downloaded code by changing every return in a lenghty string of whitespace.
In fact this can also be done with spaces but you have to be careful not to change spaces inside output strings.
You can also add numerous comments into the code.
Combine this with some clever variable renaming, et voila.
Reason 2:
For some problems you can precompute the answers and store them hardcoded in your submission.
If several members did this chances are high that your edit distance thingy will unjustified flag their submission as cheating. (I think you will lose your pole position for several problems).

Reason 3)
For some challenge problems where shortest code is asked chances are also high that your code resembles other's code too much even if you're not cheating.
(e.g. KAMIL)

In fact I think that problem setters simply must make a choice:
design a problem for a contest or design a problem for SPOJ. If they want both they should make the decision not to publish solutions on the contest's site.
Is that asked too much?

[francky]

Those recent days I saw very good comments, mails, and ideas. All very different solutions ; well justified.
I didn't see majority rising.

It's a shame to see good problems not to be placed in classical ; and I had to move some : it was hard to do.
We saw some clones will almost 100% of cheat on them ; it's a non sens to be in classical in those conditions.
I think it's a real problem ; we can't do nothing imho ; but if majority wants that, it'll be that.

Create a new problem set for clones : I no more think it's the best idea : it would promote more the copy/paste, and kill more the problem. Who really wants that ?

I really think psetter (only original psetter) should change description, title, problem_CODE, no more provide reference, to such clone,
so that they can't be easily tagged and linked to an official solution.
I know it's a bit more work, but not too much.

In addition, and independently, I think some scripts should run to prevent deviant psolvers.
wisfaq pointed the risk of false positive : we can easily avoid most of them (eg skip comments and special chars ; skip some problems, ...); it's better not to publicly publish the ways to make simple and quite efficient scripts ; but we can debate in private for that. I think some basic checks could be enough to prevent most of problems ; even if stop all is impossible.
Moreover users with rather bad attitude should be hidden (and really hidden) from rank list, points... and their AC shouldn't decrease points of regular users as it does. They will silently continue their misfit without consequences on other users.

my 2c, as always, hope to be constructive.

[mogers]

Hi all,

I was not aware of this discussion. I recently added the problems of SWERC 2014 and they were moved to tutorial due to this discussion. I asked permission of the other judges to publish these problems on SPOJ, so I won't modify them nor remove the SWERC reference.

I was surprised with this. When I was more active on SPOJ, I don't recall seeing such a tight control and cheater hunt. It may be that I didn't follow the relevant threads on this forum, but I've always seen SPOJ as a training/learning platform. There are no prizes here, besides maybe bragging rights.

I'm not saying cheating is ok, I'm just saying that unlike sites like Topcoder, I don't see the need to invest the scarce time SPOJ staff have to x-ray user submissions (which I believe will involve a lot of manual work).

(SPOJ front page...)After mentioned thread all users from top100 (and then top256) will be x-rayed.

One thing I think you should be careful about is that people train for team contests and solve problems together, later submitting the same code. I don't think this should be considered cheating.

As everyone agrees, problems from contests like ICPC regionals do not belong to tutorial. As soon as SWERC problems were moved to tutorial, people essentially stopped trying to solve them.
A new section dedicated to contest practice and separate ranking would be ok. Otherwise I think these problems belong to classical.

I believe there is great value in reading other people's code. I suggested a long time ago in this forum to introduce this in SPOJ:
- Allow a user to lock a problem after successfully solving it.
- After locking, no further submissions will affect the ranking of that problem.
- After locking, the user can read other's submissions.

And to make it clear, when we spoke here of 'public solution available' problems are those who are clones of problems with original contest with public solution, not those (numerous) for which a solution can be googled

I fail to see any difference, besides, perhaps, 5min of googling time?
It is virtually impossible to remove a good % of the problems with publicly available solutions, so the grandfather clauses are the only way to go.

While a decision is not made (I see it's been months in discussion), I think problems should stay in classical.