# Results of March Monthly Contest

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 03-24-2005
PJYelton
Results of March Monthly Contest
Ok everyone, I am going to post the results as well as my solutions in this thread. I'll start with the medium since noone posted code for that one, then the hard one, then tomorrow I'll post the results of the easy problem.

Medium Problem

Like I said when I posted this problem, I was a little torn about the difficulty of this problem. Since nobody posted code I now know it should have been listed as difficult, but once you see how this problem can be solved in only a couple of lines you'll see why I thought it might be easy.

Solving the number of combinations can be very difficult if you try to brute force it. You could recursively try every combination of animals but you'll soon find that you'll quickly max out your time. It turns out this problem can be solved very easily using a technique called dynamic programming. I'm not gonna lecture on it so if interested I'd recommend reading up on it, but its a powerful way to solve seemingly impossible problems. Its similar to recursion in that you break the problem up into smaller and smaller parts, but you use an intuitive data storage to prevent recalculating the same results over and over again.

Heres an example thats similar to my problem. How many different ways can you combine US coins to equal 17 cents? Again you could try every possible combination of coins but thats far too much work. Heres how to do it with dynamic programming:

Start off with an array of zeros of size n+1 where n is your target number. In this case we are looking for 17 cents, so our array would be size 18. Now what does this array represent? At each index, its the total number of combinations to get to that point. So index 10 is the number of combinations to 10 cents, etc. What we care about is index 17 or the last index. At this point everything is zero since we haven't calculated anything yet. First thing is to set index 0 to 1 since we automatically know that theres only one combination to get zero cents, and thats no coins at all. So our array looks like this:
Code:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Now you loop through the array with each coin type. Now heres the tricky part, at each spot in the array you know how many combinations it takes to get there since its the value of the index you are at. So if you are array[7] and the value is 5, then you know that there are five different combinations that get you to there. Now say you are looping through with pennies, if you know theres five ways to get where you are now, then add a penny to each of those and you know that theres five combinations to get to array[8]. If array[8] already had 3 combinations of its own, you now know theres 5+3 combinations to get to array[8]. Get the idea? So heres the basic algorithm:
Code:

// target is value we are shooting for
int howMany(int target)
{
int coins[5]={1,5,10,25,50}; // coin values
int combinations[500]={0};  // big array to keep the combos :D
combinations[0]=1;

for (int i=0; i<5; i++)
for (int j=0; j<target; j++)
combinations[j+coins[i]]+=combinations[j];

return combinations[target];
}

It can be optimized further but you get the idea. So after pennies our array looks like this:
Code:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
After nickels:
Code:

1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4
After dimes:
Code:

1 1 1 1 1 2 2 2 2 2 4 4 4 4 4 6 6 6
And no reason to do quarters or half dollars. So returning array[17] gives us 6 which is the correct number of combination of coins to 17 cents.

So if you can understand this one, it should be easy to figure out how to solve my problem. Since we need to know the number of combinations of feet AND heads, we now use a two dimensional array, where array[h][f] is the number of combinations that have h heads and f feet.

Heres my code to solve the problem (again which could be optimized further but no real need):
Code:

// target is value we are shooting for
int numberCombinations(int maxAnimals, int maxFeet, vector<int> animals)
{
int combinations[500][500]={0}; // again lazy, could be dynamically created
combinations[0][0]=1;

for (int i=0; i<animals.size(); i++)
for (int curFeet=0; curFeet<=maxFeet; curFeet++)

return combinations[maxAnimals][maxFeet];
}

• 03-24-2005
jverkoey
Ok, that big font's really ........ing me off.
• 03-24-2005
Perspective
Quote:

Originally Posted by jverkoey
Ok, that big font's really ........ing me off.

+1

...
• 03-24-2005
PJYelton
>>Ok, that big font's really ........ing me off.<

Sorry, if you mean the long lines, I shortened them. If not, let me know whats wrong.
• 03-24-2005
l0cke
It's not the line length, it's the size of the font.
• 03-24-2005
PJYelton
:confused: The font size is no different than normal for me... I'll take the size tags off of the problem header and see if that helps. Let me know.
• 03-24-2005
l0cke
It's back to a readable size, thanks.
• 03-25-2005
PJYelton
Hard Problem

I tried hard to find an elegant solution to this one but it appears that brute force is needed. The problem is that calculating every possibility for even the simple examples would easily time out, so one must still find some method for pruning the search tree. Turns out one such method exists which greatly reduces the running time.

If someone is picking after you theres no way to narrow down the numbers to choose from and will have to test them all, but what if you are the last to choose? Do you still have to try every number? Nope. For example, if this is the graph of peoples choices so far and you are last to choose:
Code:

------X--------X-------X-----X-X-----
the ONLY spots you need to check are:
Code:

-----OXO-------XO------XO----XOXO----
So your choice of moves is very limited when you or anyone else chooses last. This might not seem like it helps out a lot but lets choose an example. Say you have approximately 1000 numbers to check and you have one person after you and one person who picked before you. For each of your 1000 moves your opponant has 999 moves, to check each combo would result in 1000*999 possibilities or 999000 states to check. Now use the above trick, you'll only need to check 3 places in the last level, so for each of your 1000 moves the last player has 3 choices, resulting in only 3000 possibilites to check. 999000 vs 3000 is a HUGE difference!

So the algorithm basically goes, recursively try every solution except on the last level where you only choose based off of the above trick. To compute the score for any move, its basically the score above + the score below your number + 1.

For the score below, if you are the lowest number than the score is simply your number - 1. If not, then its (your number-previous number-1)/2. For the score above, if you are the highest number than its (range-your number) and if not its (next number-your number-1)/2.

Only one person submitted code and thats Karthur. Unfortunately I wasn't able to get his code to compile in MSVC++ due to several errors which I'm assuming are compiler dependant. His method appears to compute the correct answer although many items would time out.

So for Karthurs score I give a 9/10 with 1 point being deducted for the timeouts, plus an extra 10 snazzy points for being the only one brave enough to submit an entry for a grand total of 19 points and the contest winner for the hard solution. Congratulations! I highly encourage everyone to give this man some well deserved rep for his hard work!

My solution and his code are attached, let me know if you have any questions, and I'll have the last problem graded and reviewed very soon.
• 04-08-2005
Lithorien
And the easy problem, PJ...?
• 04-10-2005
Micko
Quote:

Originally Posted by PJYelton
and I'll have the last problem graded and reviewed very soon.

And that was on 03-25-2005....
• 04-10-2005
PJYelton
Sorry guys, I feel really bad considering this is a March contest and its April :o I took on this contest because my work wasn't giving me anything to code and I had lots of extra time, then mid march they suddenly slapped a huge project on me thats taken up all of my free time. But I am finishing with that today so tomorrow night I can guarantee I can finish this contest. Thanks for your patience!
• 04-10-2005
Lithorien
Quote:

Originally Posted by PJYelton
Sorry guys, I feel really bad considering this is a March contest and its April :o I took on this contest because my work wasn't giving me anything to code and I had lots of extra time, then mid march they suddenly slapped a huge project on me thats taken up all of my free time. But I am finishing with that today so tomorrow night I can guarantee I can finish this contest. Thanks for your patience!

Understood. Thanks for the update. :)
• 04-11-2005
PJYelton
All right, only a month late but the results for the easy problem are now in. This was a very tough call with three people turning in code that produced correct results every single time.

First off, here is my solution to the problem. At first it seems like this problem will require some kind of nasty backtracing to recreate the necklace from scratch. Turns out theres a much easier solution. Since you know how many pearls the original necklace had, by simply retracing her exact steps as she plucked the gold pearls out you can easily tell where the gold pearls were. And if you know where they were, then you know all the rest must be white and viola you have your necklace. So simply start with a necklace consisting of (numWhite+numGold) pearls, keep counting to k and mark that pearl as gold. Continue around and around the necklace until there are no more gold pearls left making sure NOT to count pearls you've already marked since they are no longer on the string, and when done, mark the rest as white. Or even easier, make the entire necklace white to begin with and just change the marked ones to gold. Here is my code:
Code:

string neck(int numWhite, int numGold, int k)
{
string s(numWhite+numGold, 'w'); // string is now all white

int p=-1;  // placeholder value, where we are in the necklace
int c=0;  //  our counter
int x=0;  //  number of golds we have placed so far

while (x<numGold)  // while we still have golds left
{
p++;  // increment placeholder
p%=(numGold+numWhite);  // circle to beginning
if (s[p]=='g')  // DON'T count this pearl if its gold
continue;

c++;  // increase our count
if (c==k)  // if we've reached k, mark this pearl as gold
{
s[p]='g';
c=0;  // reset count
x++;
}

}

return s;
}

Everyone's code and my score are to follow in a couple of seconds.
• 04-11-2005
PJYelton
Here is Karthur's code:
Code:

class Karthur {

#include <stdio.h>;

int test_main ( void )
{
originalNecklace(1,0,6); printf("should return \"w\"\n");
originalNecklace(0,1,6); printf("should return \"g\"\n");
originalNecklace(5,4,4); printf("should return \"wwggwwwgg\"\n");
originalNecklace(4,3,1); printf("should return \"gggwwww\"\n");
originalNecklace(0,7,25); printf("should return \"ggggggg\"\n");
originalNecklace(9,13,11); printf("should return \"ggggwgwgwwggwggwwwwggg\"\n");
originalNecklace(21,31,4);
originalNecklace(333,667,23);
originalNecklace(500,500,23);
originalNecklace(500,500,22);
originalNecklace(666,334,23);
originalNecklace(23,29,101);
printf("Completed.");
return 0;
}

int color;

#define WHITE 0
#define GOLD  1

void originalNecklace ( int white, int gold, int jump )
{
int i = 0;
int j = 0;
int k = 0;

// printf("originalNecklace(%d,%d,%d)\n",white,gold,jump);
// if ((white < 1 && gold < 1) || jump < 1) return;

try {
for (; i < white ;i++) { // BUILD ALL-WHITE CHAIN
if (!added) throw("Out of Memory");
if (i) {                  // TACK ONTO END
} else {                  // or PICK UP FIRST BEAD (WHITE)
}
}
if (white > 0) { // TIE ENDS TOGETHER
latest->next = first;
first->prev = latest;
}
} catch (Exception e) {
printf("WHITE %s\n",e);
}

try {

for (j = 0; j < gold ;j++) { // INSERT GOLD BEADS
if (!added) throw("Out of Memory");
if (i+j >= 1) {                  // INSERT BEFORE CURRENT
} else {                          // or PICK UP FIRST BEAD (GOLD)
}
if (i) {
for (k = 0; k < jump ;k++) {  // JUMP BACK TO NEXT INSERTION POINT
latest = latest->prev;
}
}
if (white == 0) { // TIE ENDS TOGETHER
latest->next = first;
first->prev = latest;
}
}
} catch (Exception e) {
printf("GOLD %s\n",e);
}

try {
first = latest->next;
latest->next = null; // DISCONNECT CHAIN FOR SIMPLE TERMINATION
for (latest=first; latest ;latest=latest->next)
printf("%c",(latest->color == WHITE) ? 'W' : 'G');
printf("\n");
} catch (Exception e) {
printf("PRINTING %s\n",e);
}

/*************** NOW TRY TO REMOVE THE GOLD ONES ***************/
try {
first->prev->next = first; // TIE ENDS BACK TOGETHER
latest = first->prev;
while (gold--) {
for (int n = 0; n < k ;n++)        // COUNT TO NEXT BEAD
latest = latest->next;
if (latest->color != GOLD) {        // MSG & QUIT ON ERROR
printf("** error **\n");
break;
}
latest->prev->next = latest->next;  // REMOVE GOLD BEAD
latest->next->prev = latest->prev;
}
// Note: if all-gold, last one still remains as "first" and "latest"
// latest = latest->next;
// if (!white)
//  latest = null;
// first = latest;
} catch (Exception e) {
printf("CHECKING %s\n",e);
}
/**************************************************  *************/
}

};

Unfortunately I couldn't get it to compile, even after I tried changing a few things and the logic of his code eluded me. Perhaps you can explain it to us Karthur?
• 04-11-2005
PJYelton
Here is Brain Cells code:
Code:

char * originalNecklace(int numWhite, int numGold, int k)
{
int length = numWhite + numGold;

char * str = new char[length+1];

for(int i=0; i<length; i++)
str[i] = 'w';

str[i] = '\0';

for(int step = k; numGold!=0; step+=k, numGold--)
{
while(step > length)
step -= length;

if(str[step-1] == 'g')
{
numGold++; step++;
}
else
str[step-1] = 'g';

}

return str;
}

Instead of incrementing by one his loop increments by k everytime. Unfortunately the problem with this is that it makes it nearly impossible to "skip" gold pearls when looping back through the necklace. Anytime it runs out of gold pearls before looping and hitting a gold it produces correct results, but doesn't for any more than that.

My score: 7/10 for semi-correct results, +1 snazzy point for realizing you can initialize the entire beginning string as white for a total of 8 points.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last