Thread: New Monthly Contest!

  1. #1
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728

    New Monthly Contest!

    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!

  2. #2
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    EASY PROBLEM
    Due date March 13th, 2005

    Problem Statement:

    Mrs Granby has bought a pearl necklace the other day that consisted of gold and white pearls in random order on a string forming a complete circle. After a few days she started to realize that she was not very fond of the gold pearls and decided to one by one take them off the necklace until there are only white pearls left. However, once off she realized that she made a terrible mistake and wanted to put them back on but she can’t for the life of her remember in what order the pearls were in. She does however remember a curious fact. She remembers starting at a particular pearl and counting “K” times to the first gold pearl. She plucked it off, then continued counting “K” more times and again hit another gold pearl. She continued this pattern and every time she hit a gold pearl, never once a white pearl, until all the gold ones were removed. So given that she knows how many white and gold pearls there are, and the number K, can you write a program for her that tells her what the original necklace looked like?

    For example, say she tells you that there were 5 white pearls, 4 gold pearls, and K was 4. Then her original necklace would look like this where ‘w’ stands for white and ‘g’ stands for gold:

    “wwggwwwgg”

    Reasoning:
    Code:
    You start at the beginning and count to 4:
    
    1234
    wwggwwwgg
    
    take out the pearl you end on:
    
    wwg_wwwgg
    
    count to four again:
    
       1234
    wwgwwwgg
    
    take out the pearl you end on again:
    
    wwgwww_g
    
    count to four again, remembering that this is 
    a circular necklace so wrap around:
    
    234   1
    wwgwwwg
    
    take out the pearl:
    
    ww_wwwg
    
    count to four and take out a pearl again:
      1234
    wwwww_
    
    and you can stop since there are no more gold pearls.  
    Never once did you land on a white pearl.
    No other layout of pearls has this property for those values, only “wwggwwwgg”.

    Your task:

    Write a fuction named originalNecklace in this format (you can name the variables whatever you want):

    string originalNecklace(int numWhite, int numGold, int k)

    which returns a string representation of the necklace given the number of white pearls, gold pearls, and the value of k.

    Parameters:
    • return your input in the format “ggwgwwwg” with ‘g’ denoting gold pearl and ‘w’ denoting white pearl.
    • Both numWhite and numGold will be between 0 and 25.
    • k will not be greater than 1000 and not be less than 1.


    Examples:
    • originalNecklace(5,4,4) returns “wwggwwwgg”

      The example given above

    • originalNecklace(4,3,1) returns “gggwwww”

      You keep taking the first pearl away, so obviously they are all at the front

    • originalNecklace(0,7,25) returns “ggggggg”

      There are no white pearls, so they are all obviously gold.

    • originalNecklace(9,13,11) returns “ggggwgwgwwggwggwwwwggg”


    Remember, if you are still having problems after this weekend, feel free to PM me for a small hint!
    Last edited by PJYelton; 03-03-2005 at 07:52 PM.

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    MEDIUM PROBLEM
    Due date March 13th, 2005

    Problem Statement:

    Farmer John is running a farm on a foreign planet with all sorts of exotic animals. Unfortunately a new tax is going into effect that says he must pay a hefty fine if he goes over the limit of the number of animals he is allowed. Also, since this is an alien farm with animals that typically have more feet than what we are accustomed to here on earth, he also has a limit to the total number of feet allowed on the farm. Ideally he wants to max out both of these numbers, so for example if the law says he can have at most 100 animals and at most 400 feet, he would want to have exactly 100 animals and 400 feet. What he wants to know is, given a list of the types of animals he can raise (denoted by the number of feet they have), how many different combination of animals can he have that max out these limits?

    For example from an earth perspective, say he is allowed to raise ducks (2 feet), sheep (4 feet), octopi (8 feet) and squid (10 feet), and the law says he can have at maximum 4 animals and 16 feet. Then the total number of combinations he can have that maxes out the law are 3. These combinations are:

    4 sheep
    1 octopus, 1 sheep, 2 ducks
    1 squid, 3 ducks


    Your task:

    Write a fuction named numberCombinations in this format (you can name the variables whatever you want):

    int numberCombinations(int maxAnimals, int maxFeet, vector<int> animals)

    which returns the total number of combinations that have maxAnimal animals, maxFeet feet, and only use animals listed in the vector animals.

    Parameters:
    • The values in the vector animals will be the number of feet that animal has. The above example for instance would have animals=(2,4,8,10).
    • All values in animals will be greater than 1 and less than or equal to 20 with no repeats. The size of the vector will not be greater than 8 and not be less than 1.
    • Both maxFeet and maxAnimals will be greater than 1 and less than 500.


    Examples:
    • maxAnimals=4, maxFeet=16, animals=(2,4,8,10) returns 3

      The example given above

    • maxAnimals=5, maxFeet=63, animals=(2,4,8,12,16,18) returns 0

      Its not possible to get 63 feet and 5 animals using the animals listed

    • maxAnimals=5, maxFeet=79, animals= (1,3,8,11,17,20) returns 4

    • maxAnimals=15 , maxFeet= 50, animals=(1,2,3,4,5,6,7,8) returns 3463



    I had trouble deciding what difficulty I should set this problem at, since this will either be really easy for you or really hard depending on your knowledge of algorithms. Be warned though, brute forcing this problem (ie trying every combination) will NOT work! You will time out for large values. Remember, if you are still having problems after this weekend, feel free to PM me for a nudge in the right direction!

  4. #4
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    HARD PROBLEM
    Due date March 13th, 2005

    Problem Statement:

    Everybody has played the number guessing game where one player secretly picks a number between 1 and X and then everybody else picks a number out loud and whoever gets the closest to the original number wins. The only rule is that you can’t pick a number that has already been picked.

    Heres an example, someone secretly picks a number between 1 and 1000. Three players are picking the number and whoever gets closest wins. Player 1 picks 500. Player 2 then can pick any number BUT 500 so he picks 750. Player 3 now goes and can pick any number BUT 500 OR 750 so he picks 499. The actual number is 600 and since player 1 is the closest he wins.

    Your job is given the range of numbers to pick, a list of the numbers chosen before you and the number of people who are choosing after you, write a program that will tell you which number maximizes your winning percentage. If there are two numbers that have the same winning potential you MUST pick the lowest one.

    Your task:

    Write a fuction named whatNumber in this format (you can name the variables whatever you want):

    int whatNumber(int range, vector<int> prevGuesses, int numAfter)

    which returns the best number to choose based off the range from 1 to range inclusive, a list of the guesses made before you, and the number of people left to choose after you.

    Parameters and notes:
    • You must assume that the people choosing after you will make the best guess possible for them following the same guidelines you do (ie picking the lowest of two numbers that have equal chances of winning)
    • Ties do not count as wins!
    • Range will be no greater than 1,000,000 and no less than 1
    • prevGuesses will have anywhere from 0 to 10 elements with no element greater than range and with no repeats
    • numAfter will be anywhere from 0 to 6
    • range will be at least 1 greater than numAfter + prevGuesses.size()
    • range^numAfter will be less than 1,000,000


    Examples:
    • range=1000, prevGuesses=(500), numAfter=1 returns 501

      The first person chose 500. If you choose 501, player 3 then has two chances to win with probability of 499/1000 depending on if he chooses 502 or 499. You can assume he’ll chose the lower of the two and thus you will have a winning probability of 500/1000. You can’t do better that that.

    • range=10, prevGuesses=(), numAfter=0 returns 1

      All answers have the same winning chances, so you should return the lowest one.

    • range=1000, prevGuesses=(), numAfter=2 returns 750

      This may seem counterintuitive since almost everybody would pick 500 if they picked first. But watch what happens, you pick 500, player 2 picks 501, player 4 picks 499 leaving you with only a 1/1000 chance of winning which is terrible. If you pick 750, player 2 will know that 250 is his best chance to win, and player 3 can choose any number from 251 to 749 for the same winning chance and will thus choose the lowest one in 251. Again, no value will give you a better winning chance than this assuming player 2 and 3 play perfectly.

    • range=477, prevGuesses=(11,33,57,239,400), numAfter=2 returns 86

    • range=10, prevGuesses=(), numAfter=6 returns 9
    Last edited by PJYelton; 03-02-2005 at 08:34 PM.

  5. #5
    Registered User
    Join Date
    Mar 2004
    Posts
    494
    Great, thanks for this contest and the 2 links you provided. I will try and enter the contest for the easy problems as im not really an expert or anything and i really need to work on the algorithms. I will pm you with 2 questions i have, i hope its alright.
    When no one helps you out. Call google();

  6. #6
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Please feel free to ask any questions here in this thread, that way everyone can benefit from the answers.

    He asked about adding timing functions to your code. I will be timing all of your code myself so please don't send anything like that in your finished programs. The first two can be solved in less than a second if done right, although the medium can be long if you try to brute force. The hard you might have problems and you might want to keep track of time yourself but just using the second hand on your watch would suffice.

    Also, please post in this thread when you submit code to me, that way I'll know to look for it and let you know if I didn't receive it.

  7. #7
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Great initiative, but there's no chance I'll have time to paticipate
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  8. #8
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Depending on how many entries I receive, I might push back the due dates to give people more time.

  9. #9
    unleashed alphaoide's Avatar
    Join Date
    Sep 2003
    Posts
    696
    This is sweet. Finally could get back to coding in C++ again. I haven't got a chance to read the problem thoroughly, but I'll be sure to participate in one of them. Keep it up.
    source: compsci textbooks, cboard.cprogramming.com, world wide web, common sense

  10. #10
    Registered User
    Join Date
    Dec 2004
    Posts
    465
    Wow I'd love to enter, but I don't think I could manage any of them
    My computer is awesome.

  11. #11
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Sure you can, trust me the first one isn't that hard. Just think about how you would do it in real life

    If the general concensus is that even the easy problem is too hard for a lot of people who want to participate, I might consider adding another problem this weekend.

  12. #12
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    I think I see an error in the first one:
    originalNecklace(6,4,4) returns “wwggwwwgg”
    There's only five whites...
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  13. #13
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Ack, you're right, I typed it wrong up top then copied the incorrect info to the bottom. The problem has been corrected to now be 5 whites.

  14. #14
    Registered User
    Join Date
    Aug 2004
    Location
    San Diego, CA
    Posts
    313
    You have PM with my entry.
    Last edited by Lithorien; 03-03-2005 at 08:01 PM. Reason: Beaten to the error.

  15. #15
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    You have PM with my entry.
    Entry received

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. May Monthly Contest Results
    By PJYelton in forum Contests Board
    Replies: 28
    Last Post: 05-27-2005, 01:43 AM
  2. May monthly contest
    By PJYelton in forum Contests Board
    Replies: 43
    Last Post: 05-18-2005, 06:37 PM
  3. Results of March Monthly Contest
    By PJYelton in forum Contests Board
    Replies: 23
    Last Post: 04-17-2005, 09:46 AM
  4. WANTED: Contest Master
    By kermi3 in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-23-2003, 10:15 PM