Archive for May, 2010

Uncategorized

Determine the Angle between the Clock Hands

Problem: You are given the time of day in HH:MM format. You need to write a program to return the angle formed between the hands of an analogue clock displaying the given time.

Solution: This is not all that difficult if you think about it. Lets consider each hand in isolation first. The minutes hand of the clock rotates 360 degrees in 60 minutes so each minute represents 6 degrees. The hours hand of the clock rotates 360 degrees in 12 hours so we know it moves a total of 30 degrees after each hour, but you need to factor in the advancement of the hours hand between hours. i.e. at 3:30 the minutes hand is on 6 and the hours hand has progressed past 3. We can calculate this advancement simply by (minutes/60) * 30 degrees which is equivalent to minutes/2.

So once we know the degrees of each hand we simply find the difference. Here's some simple C# code to show this:

        public static void Main()
        {
            int hour = 2;
            int minute = 45;

            double degrees = Math.Abs(((hour*30.0 + minute/2.0) - minute*6.0) % 360);

            Console.WriteLine( string.Format("Angle between clock hands = {0}",degrees) );
        }

Uncategorized

Google Code Jam 2010: Snapper Chain

Google Code JamCode Jam 2010 started with a qualification round that was harder than previous years. The first problem, Snapper Chain, involves a series of N switches arranged in sequence, that toggle when you snap your fingers if they are receiving power. The problem asks that you indicate if a light plugged into the end of the chain of N switches will be on after K toggles. A brute force evaluation of the state of the light would have a run time ~ O(NK). This isn't feasible since the upper limits on N and K are 30 and 108 respectively. That would take far too long to evaluate. Intuitively you know there must be some sort of pattern so in an effort to get clarity on it it's best to list the states for some toggles. So let's start with N=5 and see what we find...

K State
0 00000
1 10000
2 01000
3 11000
4 00100
5 10100
6 01100
7 11100
8 00010
9 10010
K State
10 01010
11 11010
12 00110
13 10110
14 01110
15 11110
16 00001
17 10001
18 01001
19 11001
K State
20 00101
21 10101
22 01101
23 11101
24 00011
25 10011
26 01011
27 11011
28 00111
29 10111
30 01111
31 11111

Now it becomes clear how things work. The first switch toggles with every snap so it's immediately obvious that after an even number of snaps the light cannot be on. Conversely, if N=1 then the light would be on for all odd values of K. If N=2, then we can see that the light would be on when K=3, 7, 11, 15, 19, 23 27,31. That seems to be a pattern with common increments of 4. If N=3, the light would be on when K=7,15, 23,31 - common increments of 8. And for N=4, the light is on when K=15,31 - an increment of 16. It seems that the increments are powers of two. In other words, for a given N and K we can hypothesize that the light is only on when K satisfies the following formula:

Here c is any non-negative integer. In other words, the light is on after a certain number of snaps and it comes back on after a cycle of 2N more snaps. Since N << K the summation term here is not a major concern. It is in fact the sum of a geometric progression so the summation could be replaced with a simpler term but since N is fairly small (<30) I didn't bother to optimise it further. I did add memoization to remember the sum of N items so we only ever need to calculate the sum of 30 items once. Here's some C# code to solve the problem:

   1:  using System;
   2:  using System.Collections.Generic;
   3:  using System.IO;
   4:   
   5:  namespace GoogleCodeJam2010.Qualificiation.SnapperChain
   6:  {
   7:      class Program
   8:      {
   9:          static void Main()
  10:          {
  11:              const string basePath = @"";
  12:              var infile = new StreamReader(basePath + "large.txt");
  13:              var outfile = new StreamWriter(basePath + "output.txt");
  14:   
  15:              var termSum = new Dictionary<int, ulong>();
  16:              var cycle = new ulong[31];
  17:              ulong sum = 0;
  18:              ulong current = 1;
  19:              for (int i = 0; i < 31; i++)
  20:              {
  21:                  sum = sum + current;
  22:                  termSum[i] = sum;
  23:                  current = current * 2;
  24:                  cycle[i] = current;
  25:              }
  26:              
  27:              int t = Int32.Parse(infile.ReadLine());
  28:              for (int caseNo = 1; caseNo <= t; caseNo++)
  29:              {
  30:                  var data = infile.ReadLine().Split(' ');
  31:                  int n = Int32.Parse(data[0]);
  32:                  ulong k = UInt64.Parse(data[1]);
  33:   
  34:                  string answer = "OFF";
  35:   
  36:                  if ((k - termSum[n-1]) % cycle[n-1] == 0)
  37:                      answer = "ON";
  38:   
  39:                  outfile.WriteLine("Case #{0}: {1}", caseNo, answer);
  40:              }
  41:              infile.Close();
  42:              outfile.Close();
  43:          }
  44:      }
  45:  }

Uncategorized

A Greek Tragedy : Sovereign Debt and Liquidity Issues

To understand the current sovereign debt problems in Europe one has to understand the monetary policy options available to the government of a sovereign state. Basically, there are several options available to manage national debt:

  1. Print More Money
  2. Devalue the Currency
  3. Raise Taxes
  4. Raise More Money
  5. Default

Let's run through each of these options and consider how it applies to the current Greek situation, and perhaps soon to Spain and Portugal.

Print More Money

The majority of Greece's public debt is denominated in Euros - the "local" currency - which means that it could simply print more money to pay off its large debts (you can't do this if your debt is denominated in foreign currencies). Printing more of the local currency does have consequences - it causes inflation which effectively reduces the nominal value of all other debt denominated in the local currency.

However there is a problem here. Although technically and legally a sovereign state, the Greek government doesn't have all the fiscal options usually available to an independent nation. Because it uses the Euro, and that is a shared currency with other nations, it cannot simply print more money because that's controlled by the monetary union of the euro zone. This restriction is in place to prevent other member nations from suffering currency devaluations should a member nation decide to print more of the shared currency (Euros).

Problem one.

Devalue the Currency
A government can devalue its local currency to make the domestic currency cheaper relative to other currencies. There are two implications of a devaluation. First, devaluation makes the country's exports relatively less expensive for foreigners. Second, the devaluation makes foreign products relatively more expensive for domestic consumers, thus discouraging imports. This may help to increase the country's exports and decrease imports, and may therefore help to reduce the current account deficit.

However, for the same reasons stated above - the usage of a shared currency - Greece is unable to devalue its "local" currency because its not in control of the Euro.

Problem two!!

Cut Public Spending and Raise Taxes
To increase its revenue intake the Government can raise taxes in an effort to help pay down the public debt. This is politically unpopular and thus most governments are reluctant to consider it, unless backed into a corner. Greece is doing this, but due to the magnitude of public debt it's going to find it quite difficult to raise enough money fast enough using just this option. It's been reported that Greece owes 300 billion euros which represents a public deficit of 14% of the GDP.

Problem three!!! Now into the "options of last resort"...

Raise More Money
Despite having debt problems, in order to service debts falling due Greece needs to raise more money through issuance of Government Bonds however this is a short-term solution at best. Its been reported that Greece needs to raise some 30+ billion Euros just to meets its obligations for the next 12 months. Taking on new debt obviously doesn't solve the problem of indebtedness long term, and flooding the market with sovereign bonds at a time when many investors think a default is likely causes investors to demand higher yields which makes debt raising a very expensive option.

Problem four!!!!

Default on its Debt
Defaulting on its debt would cause Greece's sovereign credit rating to decrease causing it have to pay more for future borrowings, and industry also suffers. But because Greece is a member nation of the Euro zone any default on its behalf also affects other euro-nations like Germany, Spain, Portugal, and Italy.

A default is likely unless a sufficient large bailout package from the IMF and/or other Euro-nations gets put in place along with other measures. The 3-year 110 million euro package currently on offer courtesy of the IMF is a good start!

Conclusion
Moral of the story... if you let your debt get out of control you are in for a lengthy period of financial hardship to recover. Indeed, that is what Greece currently faces, and its citizens will have little respect for the politicians responsible for monetary policy for letting such an unpleasant situation happen in the first place.