Are we going insane?

[shahriar_manzoor]

I found out that 623 has been rejudged and the limit is changed to 1000!.
I don't know who changed it and I don't care but can someone explain me why it is done? if 500! is a small number so is 1000!. Why don't u use 10000! because after 10 years this judge may run on a 100 times faster computer? Then someone might think 1000! is too small so let's make it 10000!

Or is it that the person involved likes big number manipulation very much. These problems are easy to change and to show that u r changing something but is it required. Don't we have our political leaders to do all the unnecessary works of the world ?

[..]

As I know, one of the direction of rejudge is "don't let someone get 0.00 runtime". I think 623 is modified to fit this rule. I only agree to increase the size of input file to remove 0.00 runtime, but not changing the problem itself.
Now the problem 623 looks like so srtange now, the name is "500!" but asks for "1000!". I worry that one day they will rejudge 439 by making the chessboard size to be 26x26.

Changing the problem is too annoying for everyone. As you say, if the server is upgraded in future, do we need to solve 623 for N = 10000???
I think that, if the 0.00 runtime can't be removed by icnreaseing the size of input file, it may mean that the problem setter want to set an easy problem at all. So why don't keep it easy?? The Uva online judge is so popular, partly because new comers can always find some easy problems to start solving.

I suggest making a poll to collect opinion about rejudge by modifying the problem.

[mbakht]

As I know, one of the direction of rejudge is "don't let someone get 0.00 runtime".

My personal opinion is that preventing 0.000 runtime should never be the aim of change of problem statement. The two valid causes that I can think of are (there might be other ones too - but not the above one) -

1. Prevent precalculation. There is a Josephus problem in volume 4 where many people submit precalculated answer.

2. Prevent using algorithms whose complexity is much more than the one desired. For example if there is a good algorithm to solve a problem in O(nlogn) but people are doing it using brute force or O(n^3) algorithm - then the problem statement can be changed to allow the O(nlogn) solution only.

if 500! is a small number so is 1000!.

I support Sumit Bhai. It is ridiculous to change range from 500! to 1000!. What difference does it make ?? It seems some one out there has nothing more constructive to do excepting making such funny changes.

[Adrian Kuegel]

The same thing happened with problem 100, 147, 357, 10007.
When the problem specification of 147 and 357 was changed, some people already expressed their opinion in this thread:
http://online-judge.uva.es/board/viewtopic.php?t=4630

I suggest making a poll to collect opinion about rejudge by modifying the problem.

I think that the result will be that most of us agree that the problem specification shouldn't be changed.

By the way, argument number 2 might apply for problem 623, but then it would mean they should reduce the time limit, not change problem specification. I "solved" this problem as a beginner in programming, and I had only written a biginteger addition so far, so for multiplication by n I just added n times the number. Runtime: 9.6 seconds

[Tahseen Mohammad]

I also really don't understand any of this. I do understand some
old problems can now have pre-calc solution, brute-force solutions
that are now valid because of fast system. But you cannot go on
changing problems as the system changes.

There are over 1200 problems now (>1250 solved already). How far
is one gonna get if he use brute-force or pre-calc. And whats he gonna
do in actual contest.

One mustn't forget the spirit in which most of us do Contests. We want
to improve ourselves. Here the actual limit is not the problemsetter, not
the judes time-limit, Its all about me proving myself to me.

[Carlos]

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.

[Ivor]

It has been some time since I really enjoyed some insane solving and search for better algorithms. As Carlos said 495 is one of the most interesting problems and the battle with Scott and Ivan is the one I enojoyed very much. So, 623 has actually become a lot more interesting problem from the solving point though I haven't had time to resolve it. I actually was waiting for such a change for some time... though not one so drastical.

Changing a problem description is not a very nice thing to do to members. But let's look from another point. If you have solved a certain problem then being a decent programmer it sholudn't be hard to solve a problem again. And thus do it better. So, I actually quite approve improving the problems. My aim has never been to increase the number of solved problems (well it was for a month but I just had to strain my mind and was in desperate need of a change ). My aim has usually been to squeeze the most out of the problem. I must admit though that because of the lack of time and my usual challenger, Scott, I have skipped the very ultimate part. Shame...

Anyway, keep up the good work. Do what you like while it improves the problems and the site. The only thing I'd like to ask: would you change the name of 623 to 1000!. Don't keep the old name... it's sort of silly.

Thanks for attention,
Ivor

[junbin]

If there are 2 solutions to a problem, one which takes DP, say O(logn) and another which takes brute force, say O(n^2). Is the DP one definitely better?

DP as we know requires the construction and maintenance of huge tables for reference. Is that necessarily better? What if the DP solution has a memory complexity of O(n^2) and the brute force one has a memory complexity of O(1) (most brute force without memorization has very little memory needs). Which one is better now?


I agree that pre-calulated tables are a form of "cheating" in that the goal of the website, but if some people choose to delude themselves, then let them. The goal of the website is to promote programming skills and to encourage people to improve themselves, not to compete in some mindless rat race. If you really want to see your name in the 0.00 list, then just do the pre-calculation yourself.

As far as I am concerned, if my solution is accepted, the time it took was reasonable and I know my algorithm is good, then I see no reason why I should prevent others from "cheating". Think of it this way. If you come up with better limits, people will just come up with a bigger table. If you come up with a limit so huge that pre-calculation is impossible, it will probably also mean that people who do NOT use pre-calculation but use a slower compiler (eg: pascal, java, etc.) have slightly worse algorithms will not get accepted as well. When I first started, I have no idea how DP works, but the fact that brute force (with pruning) works for some questions kept me going and see where I am now (not far from where I start .

[Lars Hellsten]

There are over 1200 problems now (>1250 solved already). How far is one gonna get if he use brute-force or pre-calc. And whats he gonna do in actual contest.

One mustn't forget the spirit in which most of us do Contests. We want
to improve ourselves. Here the actual limit is not the problemsetter, not
the judes time-limit, Its all about me proving myself to me.

I totally agree. If someone submits a precomputed table instead of actually solving the problem, *who cares*? They are only cheating themselves. Besdes, precomputing results is a perfectly valid strategy in the real ACM contest. Have you ever heard of a problem statement being changed in the middle of the contest because the judges didn't like the way it was solved? The effort that's spent changing these old problems would be better spent on writing or testing new problems.

I've pretty much given up on UVA, because of poorly worded problem statements, problems with the judging data, and ridiculous time limits intended to thwart "cheaters" (even on fairly easy problems that nobody cares about). There have been several problems I've seen, for example, where using C++ iostreams instead of scanf/printf causes an otherwise good solution to time out. Or using long longs instead of ints. These things are petty annoying, because real ACM contests (at least in my region, and the finals) tend not to have such issues.

[shahriar_manzoor]

General Reply (Sorry about the previous quote)

a) Sometimes we are strict about time limits because we want to reduce load on our server (especially during contest). Easy problems suffer this problem frequently.

b) Sometimes I feel annoyed when people compare sites like topcoder with UVa. The total idea is voluntary here and when we have less time in our hand the contests have more mistakes. As we just cannot enforce people to give certain ammount time as they are working in voluntary basis. Quite a while ago (About six months or more I guess) I came to know that hundreds of poeple line up to set problems for topcoder, that is not the case for UVa site and everyone knows why .

c) I agree that UVa is more frequently being inconsistant about time limits and it should stop. But for server limitation this problem will always persist in Online Contests.

d) We have some people who sincerely write alternate solutions whenever we ask (None more sincere than Derek). But the problem is sometimes we start preparation for a contest only 7 days before. Then we don't have the time to consult alternate solution writers or reviewers to check the problem statements.

I just wanted to say that in most cases our limilation in resources make us make mistakes.

[Tahseen Mohammad]

I have made some post ragarding this topic and I've always
opposed this vast rate of rejudging.

But please everyone at UVA, don't get me wrong. Programming
Contests has been such a great part of my education life & my life
as a whole. It has made me realize & learn so many things. I have
meet & known so many wonderful people. And my contest carrier
has certainly been centered around this site. In my university there
are not much people who are related with contests or are capable.
So if its not for this site & help of some wonderful people (Shahriar
& sajjad bhai & many others in this board), I would have been no
where.

So no matter how much I criticise you all people at UVA, I apperciate
your effort to make & run this site (and VOLUNTEERLY). It is becuase
you have done such a wonderful job that I expect so much of you.

I'll talk some more about this rejudging in a later post. Goodbye for now.

Thank YOU ALL again.

[hicham]

Hello everyone,
New to the VOJ and to the forum. Joined VOJ because I was challenged to solve problem 110, and I like it. I would like to thank all involved for a wonderful site.
This thread was quite interesting to read because of the rather strong views concerning changing problems and especially precalculation.
Whenever one is confronted with these kinds of choices, the only logical and safe course of action is pragmatism. Given some code the only objective gauge to judge it is, of course a correct answer, and physically quantizable and measurable attribute, namely time complexity and/or space complexity. In other words, if a precalculated table lookup is faster than the most elegant algorithm, the precalculation is better. After all, memory is cheap, life is short. I don

[scottaugust]

I have used both run-time calculation and pre-calculation. In my career I have had the need for both. Some times you need to calc a sqrt and other times you don't have the time, but have the space for a look-up table. I salute the solver that was able to compress a 1Mb lookup into a 40kb.

At times it has bothered me at times that some-one was able to beat me on time with a look-up when I had very good real-time calculations. Until I put this in perspective that in the real world, the faster that you can do something within the limits (code space, execution time, etc.) the better.

I don't think that a lookup table is cheating. If these solutions get a 0.000 time, so be it. If I want to compete with that time, I should work on a lookup table solution (as one of the options for problem solving) and see what I can do.

In the end, we need to look at it as some problems are better suited to lookup table solutions and others are not. My background is real-time embedded systems and I prefer the problems that resemble that kind of a problem (as well as others that are just fun to solve).

I don't agree with changing the problem description to change the solve rate, however I do understand the reasons for it. I will still stand behind the maintainers and operators of the VOJ website - it is the best that I have seen!

Just my opinions,
Scott E August