NEW MONTHLY CONTEST

Hey everyone, this is something I’ve been thinking about doing for awhile and this last weekend I finally sat down and started to figure it out. Basically what I would like to do is start up a monthly algorithm contest where I post various problems ranging from easy to difficult for anyone to solve. The due dates will generally be approximately 2 weekends after the start which I feel should be enough time to solve without giving too much time to forget. If this March contest goes well then you can expect to see new contests every month!

Here are the details, I am going to post three problems, an easy, medium, and difficult one. The idea of what constitutes easy or difficult will likely change in future contests based off feedback from this first run. Each challenge will have a problem statement that gives a little background and defines exactly what your function needs to accomplish. Your function must be able to solve the problem and produce the correct answer for any input given to it within the specified parameters. Several example answers will be given that you can use to test to see if your function produces the correct results. Feel free to send me entries for as many problems as you can accomplish. Please submit your entries via PM to me no later than midnight of the due date. If you do multiple problems please send as separate files, and you are welcome to resubmit changes, only the last one sent to me will be graded. Winners get a satisfaction, a hearty congratulations from all of your peers, and of course plenty of reputation points

Guidelines and notes:

  • I will be grading the entries on the following basis: 0-10 points for program correctness. If you code correctly answers everything I throw at it you will get 10 points. You will get between 5-9 points if your code only fails a couple of times, and less than 5 for more serious or frequent incorrect answers. On top of these I will add on bonus points for your algorithm, with more points being given to interesting or elegant solutions and less points for those who brute force. Also, these points will be weighed depending on the skill level of the programmer so that beginners have more of chance of winning the easier problems and not have to fear someone like Prelude turning in a solution

  • Your code must finish each example within 8 seconds as judged by my 2.0 GHz processor. So be sure to check to see if your code can handle the worst case scenario that I can throw at it and still finish under that time.

  • I will give the parameters and bounds for all inputs. You do NOT need to do any error checking for the input. For example, if I pass an integer to your function and say that this number is between 1 and 100, nowhere in your code do you need to check to see if it is indeed within that range. You can just assume that it always will be.

  • I will NOT be judging on coding practices such as memory usage. For example, if the algorithm calls for a two dimensional array that you don’t know the size of and one person just creates a very large array that may or may not be used while another person creates it dynamically with no memory wastage, they will be given the same score all other things being equal. By all means though, use whatever coding practices you feel comfortable with.

  • I will also NOT be grading on code size or code speed. If two people have the same algorithm they’ll get the same score. That said though, smaller, faster code usually implies a better algorithm and will be graded accordingly.

  • Please explain your algorithm somewhere in the program, either as a description up top or with various comments throughout. I admit that I am terrible at following other people’s logic and I’ll give up quickly on your code if I can’t understand whats going on and thus you’ll get little to no bonus points.

  • I want as many people to enter as possible, but I admit that I’m worried that problems could perceivably be listed as easier than they really are for a large portion of the contestants. Until I get a feel for the difficulty that is appropriate I will allow those having difficulties with the first two problems to ask me for a nudge in the right direction via PM. In this case, starting next Monday if you are stuck and desperately need a small hint please ask and I’ll give it you. Since this contest is just for fun I feel that there shouldn’t be any problem with this, although if you think this is inappropriate just let me know.

  • Your function name and parameter types must match the function name and parameters I stipulate in the problem statement, although feel free to call the parameters anything you want. This function must be placed publicly within a class named after your cprog user name. If you are new to programming and are confused by what I am talking about its really simple.

    If the problem says the function name and parameters are “int foobar(int x, int y, string s)” then the code you send to me should look like:
    Code:
    // put your includes here

// No Global Variables!

class PJYelton  // Instead of PJYelton, put your name here
{
    public:
        int foobar(int x, int y, string s)
        {
                // put code here
        }
        //  feel free to add any other functions, 
        //  just be warned that I will ONLY call foobar
};
    The function foobar MUST have three parameters and must be in the same order as listed (in this case int, int, string) but you didn’t have to call them x, y, and s so choose whatever names work for you. If you are still confused and asking isn't helping, then just send your code as is and I'll quickly format it for you if I can without changing your algorithm. I'd rather you send code than get hung up on this cosmetic matter.

  • Knowledge of STL might prove useful but is not necessary. HOWEVER, I will be using vectors from time to time to pass to your function. If you have never used vectors before I highly suggest you read up on them. If you don’t have time to learn about them, that’s ok. Just think of them and treat them as an array. The only functions you need to know are size(), push_back(), and pop_back(). The first function size() will tell you the size of your vector, push_back() will add a value to the end of your array, and pop_back() will delete the last value in your vector. If you can follow and understand the following code, then you are good to go:
    Code:
    #include<iostream>
#include<vector>  // you must include this! 
using namespace std; 

int main()
{
   vector<int> myVec;          // creates a vector of ints called myVec
   cout<<myVec.size()<<endl;   // will print 0 since your vector is empty

   myVec.push_back(3);         // adds a 3 to the end of your vector
   cout<<myVec.size()<<endl;   // will print 1 since it contains 1 item
   cout<<myVec[0]<<endl;       // should print 3
   myVec.pop_back();           // drops the last number in your vector
   cout<<myVec.size()<<endl;   // will print 0 again since its empty

   // now lets add the numbers 1-10 into our vector
   for (int x=1; x<=10; x++)
        myVec.push_back(x);

   cout<<myVec.size()<<endl;  // should print 10

   // now lets print out the values in the vector
   for (int x=0; x<myVec.size(); x++)
         cout<<myVec[x]<<endl;

   myVec.pop_back();          // delete the last number
   cout<<myVec.size()<<endl;  // should print 9 which is the new size

   return 0;
}
    If you could understand that then you know all you need to know, although I would still recommend learning more about vectors and all the wonderful things they can do.

  • Just for the record all problems are not entirely my creation. While there will be differences, the general concepts of the problems have been seen at various places including algorithm books, topcoder, and other problem sites.

  • If you enjoy doing this type of thing then I highly encourage that you check out TopCoder which is an excellent site to compete against others and test your algorithm coding skills. If you are more interested in something a little more laid back where you aren’t against the clock, then check out the UVA problem set archive which has thousands of problems you can try and submit at your own leisure.


If you are unsure or have any other questions, please don’t hesitate to ask. With that said, on to March’s problems!