Why Do You Keep Changing Problem Specifications?

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

Post Reply
rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Why Do You Keep Changing Problem Specifications?

Post by rjhadley » Sat Jan 03, 2004 8:26 pm

Problem 623 is called 500! and it's previous specification said
Assumptions: Value of a number ``n" which factorial should be calculated of does not exceed 500.
So why did you change it to 1000? What "mistake" did that "fix"?

All these changes only frustrate people. It is hard enough to solve problems and now we are suppose to (a) also predicate what fanciful changes will be made to the specification at some point in the future when solving the problem or (b) keep "fixing" all our solutions. I think the only "mistake" here is the fact that the problem specifications keep changing...

Tahseen Mohammad
Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
Location: Bangladesh

Post by Tahseen Mohammad » Wed Jan 07, 2004 12:24 pm

Sometimes they do increase the limit for rejecting brute-force solution.
But nowadays its almost useless with so many problems to solve. I don't
mind some people getting away with inefficient solutions of some problems.

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

How about proportionnaly disminishing the time limit ?

Post by Julien Cornebise » Wed Jan 07, 2004 1:50 pm

I agree that changing occasionaly specs to avoid new brute-force solutions can be useful. Nevertheless, it appears to happen more and more often ! Wich is particularly annoying.

Wouldn't it be more fair to disminish the time limit for the problems wich could now be solved by brute-force in the actual time limit (due to the increasing computing power of the machines) ? I don't know if the time limit can be set on a per-problem basis, but if it can, in my opinion, it should (in this case) !!! That would really be more fair, and would solve the problem.

Is there something that I don't see and that makes this solution impossible ?

User avatar
Carlos
System administrator
Posts: 1286
Joined: Sat Oct 13, 2001 2:00 am
Location: Valladolid, Spain
Contact:

623

Post by Carlos » Wed Jan 07, 2004 8:30 pm

Hi!
Actually we increased the limit of the problem not to avoid brute force solutions, but to avoid precalculated solutions. Most of AC submissions with 0.000 time were a 20Kb precalculated table and just scanf and printf. I don't think that's a good way to improve anyone's skill in programming.
It was the same with some problems like 100. Some people manage to compress 1MB table in a 40Kb mail (that's the maximum allowed by the judge).
One more thing, what about 495? Some people complained because we increased the limit...now it's one of the most submitted codes becose everyone looks for a faster solution. I don't think they would try to improve their codes if they get 0.000 solving time.
So I'm sorry if it anoys you, but I think it's the only way to make the ranklist fair and make people improve theirselves.
Carlos.
PS: I'll try to make a poll in the fixing mistakes section about that.

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Re: 623

Post by Julien Cornebise » Wed Jan 07, 2004 8:47 pm

marceh wrote:PS: I'll try to make a poll in the fixing mistakes section about that.
Hi Carlos

Your arguments are indeed also good. A poll would be really useful, I think.
I've got to confess that it's very very very frustrating to have 2 problems out of 142 ACs suddenly turning to WA or TLE or RTE in 2 days...

Anyway, thanks for the work on the judge, even if we can sometimes find some changes frustrating, let's not forget that we owe you this awesome online judge.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Wed Jan 07, 2004 9:14 pm

I agree that marceh's argument is quite good, and here is my opinion:
- Leave the problem as it is, people will solve it and noone will try to improve their algorithm since judge can't difference between 2 solutions.
Yes, no one will try to improve their algorithm. However, not all the problems are so easy. If one doesn't try to learn better algorithm, he will only know how to solve trivial problems. We don't need to push him to learn by changing the problems, it is his decision to learn on not.
Also, as Shahriar Manzoor says, we can imagine that we will have much faster judge servers in years later. So at that time, a slow algorithm may still pass the time limit again. Then we need to change the problem again??
- Increase input size, by repeating the same test input several times. Then, the best algorithm is the one who reads and prints faster.
If one people can do some fantastically fast IO, why don't we appreciate them?? It is not so simple to do fast IO.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Wed Jan 07, 2004 9:29 pm

.. wrote:
- Increase input size, by repeating the same test input several times. Then, the best algorithm is the one who reads and prints faster.
Rapid IO is not easy. But ACM ICPC isn't a coding contest, is it ? It's entitled "Programming" contest, but isn't the algorithmic part the most important one ? One thing more : IO relies much on the libraries shipped with the language you use. Regionals' organizers (or at least SWERC ones) tell that they're taking care that all problems can be solved with almost the same difficulty level. Using IO as a criterion for the AC or TLE state wouldn't fit in this way.

These questions can be summarized briefly in :
what is the part of pure algorithmic, and the part of pure programming, in ICPC and thus in uva.es ?
Vast subject, almost a polemic.

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Re: 623

Post by CDiMa » Wed Jan 07, 2004 11:01 pm

marceh wrote:So I'm sorry if it anoys you, but I think it's the only way to make the ranklist fair and make people improve theirselves.
Changing specifications of a problem isn't about good programming. It's about solving different problems.
Problems who can be solved by precalculation have a specification that allow such solutions.
To allow people improve themselves you can set another problem with higher specifications that can't be solved by precalculating.
That's the only way to make problem setters improve theirselves 8)

Ciao!!!

Claudio

rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by rjhadley » Wed Jan 07, 2004 11:56 pm

Most of AC submissions with 0.000 time were a 20Kb precalculated table and just scanf and printf. I don't think that's a good way to improve anyone's skill in programming.
I agree that this situation should be avoided, but is changing the input size limit really the best solution? For example, have you considered reducing the size limit for code? (Globally or on a per-problem basis). Out of my almost 400 submissions, only about 10% are larger than 5KB and only 1 is larger than 20KB. I would suspect that this observation holds for most members. Changing the code size limit would then only affect those "undesirable" pre-calculated tables, instead of hassling everyone.
I don't think they would try to improve their codes if they get 0.000 solving time.
Also, there are plenty of problems in the set which are very difficult to solve quickly. If someone desires a challenge, they can tackle those. If there isn't enough then make new problems instead of changing old ones. But I don't learn anything nor improve myself my making a trivial change in my code to account for the new input size limit. So what has good has this change done for me?
One more thing, what about 495?
I quit solving problems on ACM for 2 years, mostly due to the numerous changes being made then to specifications, including 495. I didn't have sufficient time to perform "maintenance" on my existing solutions to keep up with the pace of the re-probleming...maybe the changes stimulate some members, but they also turned-off others.

Tahseen Mohammad
Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
Location: Bangladesh

Post by Tahseen Mohammad » Sat Jan 10, 2004 12:27 pm

I think "rjhadley" got a point. I think out of my 400+ ACs all are
less then 10K. I think >5k s are less than 20.

And if you don't mind "rjhadley" for which problem you got 20K code? :D
And to the administrator why is the limit as high as 40K. I know ICPC is
not about compact code but 40K seems a mess.

And about making ranklist fair & so on. I've said it before and it seems
very few agree with me,
How far are they gonna go with preCalc
and
What do they want, A Rank or Learning something
I don't know much about compression but if one can compress 1M
into 40KB including codes for decompression, why can't he just
find a faster algo for an easy problem like p100. These problems you
are changing are mostly trivial. If these people can go so far for
preCalc why can't they just solve in normally. :(

rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by rjhadley » Sat Jan 10, 2004 8:43 pm

And if you don't mind "rjhadley" for which problem you got 20K code?
The only problem where I've used more than 20KB for source code is for 10311 Goldbach and Euler...that's a hard problem!

A good chunk of that size is a list of Carmichael numbers (I'm using a Miller-Rabin primality test so I need some means of excluding composite numbers which satisfy Fermat's Little Theorem), plus there is a prime sieve, and some other primality testing heuristics, more comments in the code than ususal, etc.

Post Reply

Return to “Other words”