Need tips for choosing algorithm and debugging.

general
, ,
1

Hello,

I am interested in learning how to write problems for contests (of course at first they may not be contest-worthy but i would like try). I searched for articles on Codechef’s Forums regarding this but was unable to find any. Is there any guide regarding this?

Also, if there are any problem setters reading this and don’t mind answering the following,

  1. How do you decide by which algorithm the problem will be solved? do you decide the algorithm first and then write the specifics of the problems?

  2. How to generate Test cases which are strong enough to test all Corner cases, Memory and Time constraints all at the same time? I believe they are huge (as in many cases N is of order 10^6) and they can’t be written manually.

  3. What are the things you need to keep in mind as users are free to use any language (It is not uncommon for users of languages like Python and Java to be get wrong answers due to some formatting issues etc)

  4. There are problem setters and problem testers, how do you find these testers? do you contact people with good rating and are interested in testing? or Codechef or any other organisation has some to whom you can send in your problems to be tested?

  5. I believe there may be times when you would like to get opinion of others about your problem, you can’t simply share that online to ask queries (who know’s it may be featured in next snackdown!) what do you do then?

Please also share your experiences and some other information which may be relevant.

Thank you in advance.

Divyansh Gaba

2

For point 1-

If you are planning for full score, its time saving to analyse algorithm first. If you have procedure clear, then whats left is mere implementation and writing the code. The time complexity of algorithm can be easily decided by looking at constraints. You need to keep some things in mind-

  • Online judge can perform ~10^8-10^9 instructions per second. Meaning, whatever you do, you must do within these many operations.

Now lets say we are given that, assuming for some question, number of elements in an array are 10^5.

Now, for any nested loop of this type-

for(i=0;i< n;i++)
{ 
   for(j=0;j< n;j++
   { 
     ...
   }
}

We can see that for every i, it repeats N times. Note that the first loop repeats N times, and for every time first loop iterates, second loop also repeats N times. So we can find that total number of iterations are N*N = 10^10. This exceeds number of instructions allowed, and will give TLE.

This is a rough way to determine time complexity, and helps a lot in deciding algorithm.

For third point-

Its true that python and java users have that disadvantage in case test cases are faulty. I usually use C++, as it can handle exceptions of extra space/extra line very well. Meaning as long as input data is correct, c++ works really well.

Lol, i cant get what you mean to tell by your 5th point. If the problem you asked query about, is not related to any on-going contest, then its always fine. If it gets featured in next snackdown, or if its solution is available online, then its problem setters fault. Its their prime responsibility that the problem they give is unique, and isnt answered by a simple google search. Thats my personal opinion.

3

Mostly top coders give questions based on two things.one is they try to design logical or conceptual question on their own and secondly they take some standard algorithms like kadane and try to modify them.
Testcases can be generated by using another code in which we use rand() function and some other techniques.For example if you need to give n integers 0 to n-1 in random order then it can be done like this.Take an array a[n] and initialise a[i]=i for all 0<=i<n then random_shuffle(a,a+n) and then print array a.
These input and output can be taken into files by using some commands andbthese commands changes from compiler to compiler.Yiu can google to know these commanads

4

Thanks @vijju123. Suppose for better understanding i should start writing a few, see where that’ll take me :slight_smile:

5

You can always come back to us in case of doubt, or if you want, you can also send me a mail at my email id (its visible in my main profile)

6

I will do that, if necessary :slight_smile: Thank you very much.