CodeChef-Bytelandian Gold Coin

using System;
using System.Collections.Generic;

public class Program
{
   public static void Main()
   {
      uint input;
      bool b = true;

      while(b)
      {
         b = uint.TryParse(Console.ReadLine(), out input);
         if(b)
         {
            Console.WriteLine(FindBestDeal(input));
         }
      }
   }

   static Dictionary<uint, uint> cache = new Dictionary<uint, uint>();

   public static uint FindBestDeal(uint n)
   {
      if(cache.ContainsKey(n))
      {
         return cache[n];
      }

      if(n/2 + n/3 + n/4 > n)
      {
         uint sum = FindBestDeal(n/2) + FindBestDeal(n/3) + FindBestDeal(n/4);
         cache[n] = sum;
         return sum;
      }
      else
      {
         return n;
      }
   }
}

This is my final solution to the Bytelandian Gold Coin problem on CodeChef. This was my first shot at a problem of a medium level of difficulty on this site. And honestly I thought it was surprisingly simple at first but that was only because I didn’t give the problem proper considerations. I busted out some code, submitted it feeling confident and then found out my solution was incorrect. I went through a number of iterations and finally came up with this.

Here’s a description of the problem here.

I won’t go through every iteration I went through but here are a couple of key concepts required for a problem like this.

Recursion

Recursion is a concept in which an algorithm calls itself.  In the problem, we need to take a coin, divide it by two, three, and four, and add up the quotients.  If the sum of quotients is greater, than we have to return the highest possible sum.  And in order to do that, we have to divide all of the previous quotients by two, three, and four, and up up those quotients.  For example, 24 becomes 12 +  8 + 6 which is a total of 26.  26 however is not the right answer because one of our new quotients is 12.  And 12 becomes 6 + 4 + 3 which is 13.  So the correct answer for 24 is 27.  So basically you just have use the same logic on all of the cascading quotients as you do the initial input.  Have a look at line 32 to see where the recursion begins.

Memoization

It’s weawy hawd for me to even think about this technique without giggling.  It weawy takes me back to my pwe-speech class days when I had twouble with my ‘r’ sounds.  Anyways, memoization is a technique used to optimize repeated methods.  It works by caching data and then checking that cache to determine whether or not certain data has already been computed. It seems like a good practice for recursive algorithms as it saves tons of CPU cycles.  And in this problem on CodeChef, you need to implement memoization in order to stay under the time limit.  You can look at the memoization parts of this program on lines 21, 25-28, and 33.

The uint Data Type

There really isn’t much to this but because the problem potentially requires integers larger than a regular int can store, you need something with a larger boundary like a uint.  Though if you test this program with 1000000000 you still get very close to the maximum integer a uint can store.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s