April challenge 2014 marked the beginning of my Competitive programming journey.
Since I am new to this - it took me quite a bit of time to figure out the CNPIIM code but finally when I did - my soln took just over 1 sec to run. I was really amused to see people running it in 0.0 secs.
Now that the solns were made public - I see that they simply stored all the 2500 answers in an array.
Is this allowed ?
If yes then whats the point of time limit for questions with low test cases as anyone can have a program with a bad algorithm that gives desired output in an hour or so - all he needs to do is store them in an array after a pre run on his system.
Not to take any credibility out of those solutions but few of them are exactly identical as well. I also find it hard to believe so many people actually took the time to store those 2500 values in the array. Some guys don’t even know that 1250x1250 is max multiplication value and not the index as they have sized the array to 1250x1250.
Though most of them would have run their program to get those values - some of this still looks dubious to me as few solns are exact clones and even if they did run their original programs and stored answers then whats the point of time limit.
On a side note - When will the contest ratings be released ?
There is a cap on maximum size of code. So in most of the cases, luckily it is not possible to store all possible answers.
About your concern, everybody on this website has a different purpose. Some want to learn and some want to stay on top of chart for 1 particular question through loop-holes. I believe it should be ok to hardcode your answer (more admins can tell), but you should leave your paperwork or code snippet as comments that generated the array.
And don’t worry it seems they didn’t cheat and generated their arrays separately.
@thezodiac1994 It is perfectly legal to store values. In this question, you could get both pre computed and non-pre computed solutions accepted.However a large number of questions are designed in such a way that you have to pre-compute values. Sometimes it is more convenient and efficient to pre-compute the values and store them rather than compute each value again.You have to fit the pre-computed values inside the source code limit of 50000 bytes (Generally you can fit around 5-10k values).
As far as storing the values are concerned, it is not done manually. You can write code to pre-compute the values and store them in a file. You can then add these values to the source file. The main advantage is that the time complexity of the code to pre-compute values need not be strict. You can use a O(N^2) or O(N^3) which normally will not get accepted.
As far as ratings are concerned , they will be updated after the contest problems are rejudged. It typically takes around 2-3 days.
A valid submission for a problem consists of (1) the output file generated by the contestant and (2) all source code the contestant used to generate that output file.
can be applied in such case…
I hoped that source limit size will be decreased during the contest, but that didn’t happen. Maybe some technical problems with this?
This is also highly problem and constraints dependent.
The most common problems where I see pre-computed values are problems which use prime numbers/series of powers, etc.
While I was upset that a lot of people used pre-computed values (either because they already knew the sequence and imported it, or because they computed it offline in a time larger than 1sec), it is indeed quite funny to see how resourceful or how skilled contestants can be
Everyone here is smarter than you when you set a problem ;D
Also answering your question directly, this is not illegal as long as the source code file size allows it I also had other idea for the tests in mind, but we discarded it for being quite hard/cumbersome/inneficient for an EASY level problem
Last but not least, welcome to Codechef Hope you stick around You’ll learn a lot
Everyone here is smarter than you when you set a problem ;D
That’s why you need to set a problem smartly :D. Strong tests (aimed especially at slow/wrong approaches that’d otherwise pass) and many tests are the most important example of this. It’s a bit of a waste when the problem is too standard or too easy with some trick (like pre-computation).
Actually that is the way I originally solved the problem, because my algorithm was so slow it took one hour to complete! But instead of submitting, I thought, “Hey, this is probably cheating.” So I didn’t do that, and instead made it a lot faster!
I can’t argue with the rules, and, although it is upsetting that some people solve it that way, I think most of us are on CodeChef to learn more than just “win.”
I was the setter for CNPIIM,
You’ll learn a lot