Josephus Problem!

You're forced to commit suicide, and you will use math to save yourself!

weird, huh? but this actually happened. Quoting from Wikipedia:

"The problem is named after Flavius Josephus, a Jewish historian living in the 1st century. According to Josephus' account of the siege of Yodfat, he and his 40 soldiers were trapped in a cave, the exit of which was blocked by Romans. They chose suicide over capture and decided that they would form a circle and start killing themselves using a step of three. Josephus states that by luck or maybe by the hand of God, he and another man remained the last and gave up to the Romans."

Problem Statement

There are people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. The task is to choose the place in the initial circle so that you are the last one remaining and so survive.

so how can we solve this problem?

We'll consider the case where we repeatedly execute the second person in the circle (k = 2) in a circle of size N. We want to find the position of the person who will be the last to execute himself, but of course he wouldn't, he would like to survive!

let's see the case for N = 1, Solution = 1 as this is the only person in the circle.
for N = 2, Solution = 1, as the second person will execute himself and "1" remains.

for N = 3, we have circle = (1, 2, 3). 2 will execute himself, then we're now standing at "3" as the first element and we have circle = (1, 3). the second person will execute himself "1", then the survivor is "3".

for N = 8, we have circle = (1, 2, 3, 4, 5, 6, 7, 8).

in the first run, "2", "4", "6" and "8" will all be executed and we'll end up with (1, 3, 5, 7).
we repeat again, "3" and "7" will be executed". we now have "1" and "3". "3" will be executed, now we have "1" as the survivor.

here is a list of the results for some N.

N = 1, S = 1
N= 2, S = 1
N = 3, S = 3
N = 4, S = 1
N = 5, S = 3
N = 6, S = 5
N = 7, S = 7
N = 8, S = 1

How can we solve this with code?

Trivial solution is to model the group as a circular linked list and repeatedly delete every second element until the size of the list is zero.

Code for this is something like

typedef struct Node
{
   int value;
   Node *pNext;
} Node;

int josephus(int N)
{
   Node *head, *curr;
   // Error case
   if(N <= 0)
      return -1;

   // Create a circular list of people with
   // 1 -> 2 -> 3 -> .... -> N -> 1
   curr = head = new Node();
   head->value = 1;

   for(int i = 2; i <= N; ++i)
   {
         curr->pNext = new Node();
         curr = curr->pNext;
         curr->value = i;
   }

   curr->pNext = head;

   curr = head;
   // While not everyone is dead
   while(N > 1)
   {
      Node *tmp = curr->pNext;
      curr->pNext = tmp->pNext;
      delete tmp;
      curr = curr->pNext;
      --N;
   }

   return curr->value;
}

This is an O(N) time complexity solution and also O(N) space. Can we do better?
Yes!

With a few observations, if we have a circle of size (2 * N), meaning that it has an even number of people, like (1, 2, 3, 4, 5, 6). After the first run, "2", "4", "6" are eliminated and we have "1", 3", and "5". A circle of size "3" where each person id is multiplied by "2" then "1" is subtracted from it.

So, in order to find the solution of a circle with size N where N is even, we simply find the solution of circle (N/2) then multiply it by "2" and subtract "1".

in other means, S(N) = 2 * S(N-1) - 1, where N is even.
What if we have a circle of odd size?

(1, 2, 3, 4, 5, 6, 7) let's say it's of size (2 * N + 1).

After the first run, "2, 4, 6" are deleted which eliminates the "N" part, we then need to eliminate one more item to get to the smaller subproblem, so the next element to be eliminated is "1".

We end up with "3, 5, 7". Comparing it to "1, 2, 3". we see that each element is multiplied by "2", then added to "1"

so the total recurrence is:

S(N) = 2 * S(N/2) - 1, where N is even
S(N) = 2 * S(N/2) + 1, where N is odd

We can simply write a recursive solution for this with the base case of N(1) = 1, the complexity of this solution is O(lg N) as it divides the size of problem by two.

code for this can be something like

int josephus(int N)
{
   if(N <= 0)
      return -1;
   else if (N == 1)
      return 1;
   else
   {
      // testing the least significant bit to know
      // if this is an odd number
      if(N&1)
         return 2 * josephus(N/2) + 1;
      else
         return 2 * josephus(N/2) - 1;
   }
}

Can we do better than O(lg n)? Yes we can!
Let's see some other simple observations

N = 1, S = 1
N= 2, S = 1
N = 3, S = 3
N = 4, S = 1
N = 5, S = 3
N = 6, S = 5
N = 7, S = 7
N = 8, S = 1
N = 9, S = 3
N = 10, S = 5
N = 11, S = 7
N = 12, S = 9
N = 13, S = 11
N = 14, S = 13
N = 15, S = 15.

You can see that at every power of "2", solution resets to "1" then, "2" is added repeatedly till we reach the next power of 2. This can be proved by mathematical induction. So one way to solve this is the following:

if M is the biggest power of "2" that is less than or equal to N, let L = N - M;
Now multiply L by 2 as we're adding "2" at every step, then finally add "1". The result will be S = 2 * L + 1.

let's see some example
for N = 14, the last power of "2" is "8", set L = N - 8 = 6;
S = 2 * L + 1 = 13!

how can we find the last power of "2" greater than or equal to N? this is simply the leftmost set "1" bit in N if we represent it in binary.

Now, how can we write code for this in O(1)? it should be something like this:

This code will work if int is 32-bit size. It's called bit smearing and is used to find the left-most "1" bit, we're then going to reset it and that will simply subtract the power of two from the number.
we'll then shift it left by "1" to multiply it by two and add "1".

int josephus(int n)
{
   int m = n;
   if(n <= 0)
      return -1;
   m |= (m >> 16);
   m |= (m >> 8);
   m |= (m >> 4);
   m |= (m >> 2);
   m |= (m >> 1);
   m ^= (m >> 1);
   n &= ~m;
   return (n << 1)|1;
}

You can search or think of solutions for the general case when k != 2.


See you soon...

TopCoder BiggestRectangleEasy

This is an easy problem, but can be solved with short code using bit-wise binary operators, and as I'm always a big fan of binary tricks, I decided to post it here.

Problem Statement

Little Josh has found several sticks that are each 1 inch long. He wants to form a rectangle with the biggest possible area, using these sticks as the perimeter. He is allowed to glue sticks together, but he is not allowed to break a single stick into multiple shorter sticks. For example, if Josh has 11 sticks, he can create a 2 x 3 rectangle using 10 sticks. This rectangle has an area of 6 square inches, which is the biggest area that can be achieved in this case. You will be given an int N, and you must return the maximal area (in square inches) of a rectangle that can be created using N or less sticks.

so how can we solve this problem?

Let's see what we can do. First if the number of sticks is odd, we have to remove one stick as there can't be a rectangle with an odd perimeter. We have a rectangle with a perimeter N, and we all know that the perimeter of a rectangle is 2 * (rectangle's width + rectangle's height).

suppose width is "w" and height is "h", we divide by "2" to get sum = "w + h".

Now, we want to maximize "w * h" and we already have sum = "w + h".
one way to find "w" and "h" that maximize the product, is to try with "w" = 1 and h = "sum - 1" then store their product, then keep increasing "w" and decreasing "h" to find the values that will maximizes their product.

So this will give us a linear-time solution in terms of "w + h". A simple observation however, is that in order to maximize "w * h", "w" and "h' have to be as close as possible (I don't know a mathematical proof for that, if you know one please post it here". So, we simply set "w" = sum/2 and "h" = sum - w, and we have the maximum area that we can have with N sticks!.

Now let's see code for this.

int findArea(int N)
{
   // If the number of sticks is odd, remove one.
   // Divide by 2 to get "w+h"
   N >>= 1;
   // set "w" to "N/2"
   int w = N >> 1;
   // return "w * h"
   return (w * (N - w));
}

UVa 10570 - Meeting with Aliens

UVa Problem

This problem has to do with an important concept, permutation cycles.

Code:

#include <iostream>
#include <list>
#include <vector>

using namespace std;

typedef vector<int> perm;

list<perm> getPermCycles(perm p)
{
   const int N = p.size();
   list<perm> permCycles;
   vector<bool> used(N, false);

   for(int i = 0; i < N; ++i)
   {
      if(used[i] == false)
      {
         used[i] = true;
         perm newPerm;
         newPerm.push_back(i);

         int nextIndex = p[i];

         while(nextIndex != i)
         {
            newPerm.push_back(nextIndex);
            used[nextIndex] = true;
            nextIndex = p[nextIndex];
         }
         permCycles.push_back(newPerm);
      }
   }
   return permCycles;
}

int numSwaps(const list<perm>& perms)
{
   int result = 0;

   for(list<perm>::const_iterator i = perms.begin();
         i != perms.end(); ++i)
   {
      result += i->size();
   }

   result -= perms.size();

   return result;
}

perm mulPerm(perm perm1, perm perm2)
{
   perm result(perm1.size());
   perm inverted(perm1.size());

   for(int i = 0; i < inverted.size(); ++i)
      inverted[perm1[i]] = i;

   for(int i = 0; i < perm1.size(); ++i)
   {
      result[inverted[i]] = perm2[i];
   }

   return result;
}

int main(int argc, char *argv[])
{
   int N;

   while( (cin >> N) && N)
   {
      perm initPerm(N);
      perm rInitPerm(N);
      for(int i = 0; i < N; ++i)
      {
         cin >> initPerm[i];
         --initPerm[i];
         rInitPerm[N - i - 1] = initPerm[i];
      }

      int nSwaps = N - 1;

      perm identity(N);
      for(int i = 0; i < N; ++i)
         identity[i] = i;

      for(int i = 0; i < N; ++i)
      {
         perm res = mulPerm(identity, initPerm);
         nSwaps = min(nSwaps,
               numSwaps(getPermCycles(res)));

         res = mulPerm(identity, rInitPerm);
         nSwaps = min(nSwaps,
               numSwaps(getPermCycles(res)));

         for(int j = 0; j < N; ++j)
            identity[j] = (identity[j] + 1) % N;
      }
      cout << nSwaps << endl;
   }
   return 0;
}

UVa 533 - Equation Solver

UVa Problem

This problem is about how to solve a linear equation. Since we're sure that it will always be a linear equation, the solution is simple.

we have a complex equation like this "(42-6*7)*x=2*5-10"

my solution divides the equation into two expressions around the "=" operator.
then we reduce each expression into one of the form "a * x + b" where "a" and "b" are integers.

so we reduces the whole equation to "a1 * x + b1 = a2 * x + b2"

there are three possibilities:

1. "a1 = a2" and "b1 = b2", in this case we have an infinite number of solutions as any value of x will satisfy the equation.
2. "a1 = a2" and "b1 != b2", then we have no solutions as no value of x will ever satisfy the equation.
3. "a1 != a2", then we can calculate "x" simply as "x" = (b2 - b1) / (a1 - a2).

I wrote a simple recursive-decent parser for the problem and kept reducing the expression as I go up in the parse tree.

Code:

#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <sstream>

using namespace std;

enum TokenType
{
   TOKEN_INT,
   TOKEN_EQ,
   TOKEN_X,
   TOKEN_LP,
   TOKEN_RP,
   TOKEN_PLUS,
   TOKEN_MINUS,
   TOKEN_MUL,
   TOKEN_END
};

class Token
{
public:
   Token(TokenType tokType) : mType(tokType)
   {

   }
   TokenType getType()
   {
      return mType;
   }
private:
   TokenType mType;
};

class IntToken : public Token
{
public:
   IntToken(int value) : mValue(value),
   Token(TOKEN_INT)
   {

   }
   int getValue()
   {
      return mValue;
   }
private:
   int mValue;
};

class Lexer
{
public:
   Lexer(istream& iStream) : mStream(iStream)
   {

   }
   Token* getNextToken()
   {
      int ch = mStream.get();
      char ccc = (char)ch;
      while(ch == ' ')
         ch = mStream.get();

      switch(ch)
      {
         case '=':
            return new Token(TOKEN_EQ);
            break;
         case '+':
            return new Token(TOKEN_PLUS);
            break;
         case '-':
            return new Token(TOKEN_MINUS);
            break;
         case '*':
            return new Token(TOKEN_MUL);
            break;
         case 'x':
            return new Token(TOKEN_X);
            break;
         case '(':
            return new Token(TOKEN_LP);
            break;
         case ')':
            return new Token(TOKEN_RP);
            break;
         case EOF:
            return new Token(TOKEN_END);
            break;
         default:
            if(ch >= '0' && ch <= '9')
            {
               int number = 0;

               while(ch >= '0' && ch <= '9')
               {
                  number *= 10;
                  number += ch - '0';
                  ch = mStream.get();
               }

               mStream.putback(ch);

               return new IntToken(number);
            }
            else
            {
               return new Token(TOKEN_END);
            }
            break;

      }
   }
private:
   istream& mStream;
};

class Solver
{
public:
   Solver(istringstream& exprStream):
      mLexer(exprStream), mCurrTok(0)
   {
      mCurrTok = mLexer.getNextToken();
      pair<int, int> result = expr();
      m_x = result.first;
      m_num = result.second;
   }


   int get_xFactor()
   {
      return m_x;
   }

   int get_numFactor()
   {
      return m_num;
   }

private:

   pair<int, int> expr()
   {
      pair<int, int> result = term();
      pair<int, int> tmp = rExpr();
      result.first += tmp.first;
      result.second += tmp.second;
      return result;
   }

   pair<int, int> rExpr()
   {
      pair<int, int> result = make_pair(0, 0);
      if(mCurrTok->getType() == TOKEN_PLUS)
      {
         match(TOKEN_PLUS);
         pair<int, int> tmp = term();
         result.first += tmp.first;
         result.second += tmp.second;
         tmp = rExpr();
         result.first += tmp.first;
         result.second += tmp.second;
      }
      else if (mCurrTok->getType() == TOKEN_MINUS)
      {
         match(TOKEN_MINUS);
         pair<int, int> tmp = term();
         result.first -= tmp.first;
         result.second -= tmp.second;
         tmp = rExpr();
         result.first += tmp.first;
         result.second += tmp.second;
      }
      return result;
   }

   pair<int, int> term()
   {
      pair<int, int> tmp1 = factor();
      pair<int, int> tmp2 = rTerm();

      return make_pair(tmp1.first * tmp2.second +
            tmp1.second * tmp2.first,
            tmp1.second * tmp2.second);

   }

   pair<int, int> rTerm()
   {
      if(mCurrTok->getType() == TOKEN_MUL)
      {
         match(TOKEN_MUL);
         return term();

      }
      return make_pair(0, 1);;
   }

   pair<int, int> factor()
   {
      if(mCurrTok->getType() == TOKEN_X)
      {
         match(TOKEN_X);
         return make_pair(1, 0);
      }
      else if(mCurrTok->getType() == TOKEN_INT)
      {
         IntToken* intTok = (IntToken*)mCurrTok;
         int val = intTok->getValue();
         match(TOKEN_INT);
         return make_pair(0, val);
      }
      else
      {
         match(TOKEN_LP);
         pair<int, int> exprVal = expr();
         match(TOKEN_RP);
         return exprVal;
      }
   }

   bool match(TokenType tokType)
   {
      if(mCurrTok->getType() == tokType)
      {
         delete mCurrTok;
         mCurrTok = mLexer.getNextToken();
         return true;
      }
      else
      {
         // Handle errors
      }

      return false;
   }
private:
   Lexer mLexer;
   Token *mCurrTok;
   int m_num;
   int m_x;
};

int main(int argc, char* argv[])
{

   string strLine;
   int iEqu = 1;
   bool firstTime = true;

   while(cin >> strLine)
   {
      istringstream inputStream(strLine);
      int iPos = strLine.find_first_of('=');
      string expr1 = strLine.substr(0, iPos);
      string expr2 = strLine.substr(iPos+1);

      istringstream strStream1(expr1);
      istringstream strStream2(expr2);

      Solver s1(strStream1);
      Solver s2(strStream2);

      if(!firstTime)
         cout << '\n';
      else
         firstTime = false;

      cout << "Equation #" << iEqu << endl;

      if(s1.get_xFactor() == s2.get_xFactor())
      {
         if(s1.get_numFactor() == s2.get_numFactor())
         {
            cout << "Infinitely many solutions.\n";
         }
         else
         {
            cout << "No solution.\n";
         }
      }
      else
      {
         double x = (double)(s2.get_numFactor() -
               s1.get_numFactor())/
               (double)(s1.get_xFactor() -
               s2.get_xFactor());
         
         printf("x = %.6f\n", x);
      }
      ++iEqu;
   }
   return 0;
}

Select k random elements from a list of size n

Today, I'm going to talk about a popular problem which is how to select "k" random elements of a list of size "n" and how to do this when the size of the list is unknown like if the list is some kind of an endless stream.


First attempt:

Randomly shuffle the list and return the first k elements. This is an easy solution, however, you would have to either modify the array or use O(N) extra storage where you'll copy the array elements before shuffling them.

How to shuffle the array?

You traverse the array from i = 0 to i = n - 1 and generate a random number from a random number generator between i and n - 1 and swap that element with i.

Code should be something like this (Error checking ommitted for simplicity)

void krandom(int *arr, int *output, int n, int k)
{
   int *cpyArr = new int[n];

   for(int i = 0; i < n; ++i)
      cpyArr[i] = arr[i];

   for(int i = 0; i < n; ++i)
   {
      int j = rand(i, n - 1);
      swap(cpyArr[i], cpyArr[j]);
   }

   for(int i = 0; i < k; ++i)
      output[i] = cpyArr[i];

   delete cpyArr;
} 

Second attempt:

In this attempt, we'll pass through the array once and decide if we should insert  the element into the output array or not.

This is an O(N) solution with no extra storage

let's see how we can implement this.

if we have an array of 100 elements and we want to choose 100 random elements, then each one of these elements should have a 100% percent chance of being in.

if after choosing some random elements we end up having 10 elements to choose from and 5 random elements to choose, then the next element should have a 50% chance of being in.

what if we have 4 elements to choose from and "0" elements choose from these four? then the next element should have a 0% chance of being inserted in the output.

this suggests the following algorithm

void krandom(int *arr, int *output, int n, int k)
{
   // Where to insert the element into output array
   int iOutput = 0;
   int kRest = k;
   int nChoose = n;

   for(int i = 0; i < n && kRest != 0; ++i)
   {
      // Generate a random number between 1 and
      // nChoose inclusive
      int iRand = rand(1, nChoose);
      // give the element a kRest/nChoose chance
      // of being inserted
      if(iRand <= k)
      {
         output[iOutput++] = arr[i];
         // we have one less random item to insert
         --kRest;
         // we have one less element to choose from
         --nChoose;
      }
   }
} 

Third attempt:

This is an easy solution using O(K) extra storage and O(K) time complexity when you have a good pseudo-random generator, this is very efficient when N is very big and K is relatively small.

The solution uses a hashtable to check if the current item was inserted after selecting one random element from the input array.

void krandom(int *arr, int *output, int n, int k)
{
   hash_map<int> tableItems;
   int iOutput = 0;

   while(tableItems.size() != k)
   {
      int iRand = rand(0, n-1);

      if(!tableItems.containsKey(iRand))
      {
         tableItems.insert(iRand);
         output[iOutput++] = arr[iRand];
      }
   }
}

Now what if you don't already know the size of the list? maybe it's a very big linked list that you don't want to traverse twice to know the size of or it's an endless stream, how do you choose k random elements from this list?

First think how would you do it when the list has only k elements? how do you choose 10 random elements from a 10-size list? you just insert all items in the output.

What if you get another element? the 11th element? you should choose if you should replace it with one of the items you already chose or just ignore it. This can be done by generating a number between 1 and 11 and replace the item with one already there if the generated random number is between 1 and 10.

This way items at the beginning of the array will have a big chance of being in and also a big chance of being thrown away later. Items at the end of the last will have a smaller chance of getting in but also a smaller chance of getting out once they get in.

This is known as the reservoir method.

See you in another post!

UVa 10946 - You want what filled?

UVa Problem

Solution:

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

bool comp_1(const pair<char, int>& a,
      const pair<char, int>& b)
{
   return a.first < b.first;
}

bool comp_2(const pair<char, int>& a,
      const pair<char, int>& b)
{
   return b.second < a.second;
}

class Problem
{
public:
   Problem(const vector<vector<char> >& problemMap) :
      mMap(problemMap)
   {

   }

   vector<pair<char, int> > getSolution() const
   {
      return mHoles;
   }

   void solve()
   {
      for(int iRow = 0; iRow < mMap.size(); ++iRow)
      {
         for(int iCol = 0; iCol < mMap[0].size(); ++iCol)
         {
            if(mVisited.count(make_pair(iRow, iCol)) == 0)
            {
               if(mMap[iRow][iCol] != '.')
               {
                  char character = mMap[iRow][iCol];
                  int holeSize = floodfill(iRow, iCol, character);
                  mHoles.push_back(make_pair(character, holeSize));
               }
            }
         }
      }
      sort(mHoles.begin(), mHoles.end(), comp_1);
      stable_sort(mHoles.begin(), mHoles.end(), comp_2);
   }

private:
   bool valid(int row, int col)
   {
      return row >= 0 && row < mMap.size() &&
            col >= 0 && col < mMap[0].size();
   }
   int floodfill(int row, int col, char c)
   {
      int holeSize = 0;

      if(valid(row, col) && mVisited.count(make_pair(row, col)) == 0)
      {
         if(mMap[row][col] == c)
         {
            ++holeSize;
            mVisited.insert(make_pair(row, col));
            holeSize += floodfill(row+1, col, c);
            holeSize += floodfill(row-1, col, c);
            holeSize += floodfill(row, col+1, c);
            holeSize += floodfill(row, col-1, c);
         }
      }

      return holeSize;

   }
private:
   const vector<vector<char> >& mMap;
   set<pair<int, int> > mVisited;
   vector<pair<char, int> > mHoles;
};

int main(int argc, char *argv[])
{
   int numRows, numCols;
   int iProblem = 1;


   while(cin >> numRows)
   {
      cin >> numCols;

      if(numRows == 0 || numCols == 0)
         break;

      vector<vector<char> > problemMap(numRows);

      for(int iRow = 0; iRow < numRows; ++iRow)
      {
         string strLine;
         cin >> strLine;

         for(int iCol = 0; iCol < numCols; ++iCol)
            problemMap[iRow].push_back(strLine[iCol]);
      }

      Problem prob(problemMap);
      prob.solve();

      vector<pair<char, int> > sol = prob.getSolution();

      cout << "Problem " << iProblem << ":" << endl;

      for(int i = 0; i < sol.size(); ++i)
      {
         cout << sol[i].first << ' ' << sol[i].second << endl;
      }

      ++iProblem;
   }
   return 0;
}

UVa 216 - Getting in Line

UVa Problem

Solution:

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>
#include <limits>

using namespace std;

struct Point
{
   int x, y;
};

struct Link
{
   Point start, end;
   double distance;
};

class NetworkSolver
{
public:
   NetworkSolver(const vector<Point>& nodes) :
      mNodes(nodes), mTotalLength(numeric_limits<int>::max()),
      mConfig(nodes.size() - 1)
   {
   }

   double getTotalLength()
   {
      return mTotalLength;
   }

   vector<Link> getConfig()
   {
      return mConfig;
   }

   void solve()
   {
      vector<Point> buffer(mNodes.size());
      vector<bool> bFree(mNodes.size(), true);
      doSolve(buffer, bFree, 0);
   }
private:
   void doSolve(vector<Point>& buffer, vector<bool>& bFree, int level)
   {
      if(level == mNodes.size())
      {
         double currDist = 0;

         for(int iNode = 0; iNode < level - 1; ++iNode)
         {
            currDist += (16 + sqrt( (buffer[iNode].x - buffer[iNode+1].x)
                  * (buffer[iNode].x - buffer[iNode+1].x)+
                  (buffer[iNode].y - buffer[iNode+1].y)
                                    * (buffer[iNode].y - buffer[iNode+1].y)));
         }

         if(currDist < mTotalLength)
         {
            mTotalLength = currDist;
            for(int iNode = 0; iNode < buffer.size() - 1; ++iNode)
            {
               mConfig[iNode].start = buffer[iNode];
               mConfig[iNode].end = buffer[iNode+1];
               // Euclidean Distance
               mConfig[iNode].distance =
                     (16 + sqrt( (buffer[iNode].x - buffer[iNode+1].x)
                           * (buffer[iNode].x - buffer[iNode+1].x)+
                             (buffer[iNode].y - buffer[iNode+1].y)
                           * (buffer[iNode].y - buffer[iNode+1].y)));
            }

         }
         return;
      }

      for(int i = 0; i < mNodes.size(); ++i)
      {
         if(bFree[i])
         {
            bFree[i] = false;
            int tmp = buffer.size();
            buffer[level] = mNodes[i];
            tmp = buffer.size();
            doSolve(buffer, bFree, level+1);
            bFree[i] = true;
         }
      }
   }

private:
   const vector<Point>& mNodes;
   vector<Link> mConfig;
   double mTotalLength;
};


int main(int argc, char *argv[])
{
   int iNetwork = 1;
   int numComputers;

   while( (cin >> numComputers) && numComputers)
   {
      vector<Point> nodes;

      for(int iNode = 0; iNode < numComputers; ++iNode)
      {
         Point currNode;
         cin >> currNode.x;
         cin >> currNode.y;
         nodes.push_back(currNode);
      }

      // Node and Distance of result configuration
      vector<Link> links;

      double totalLength;

      NetworkSolver solver(nodes);
      solver.solve();
      links = solver.getConfig();
      totalLength = solver.getTotalLength();


      printf("**********************************************************\n");
      printf("Network #%d\n", iNetwork);
      for(int iLink = 0; iLink < links.size(); ++iLink)
      {
         printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2f feet.\n",
               links[iLink].start.x,
               links[iLink].start.y,
               links[iLink].end.x,
               links[iLink].end.y,
               links[iLink].distance);
      }
      printf("Number of feet of cable required is %.2f.\n", totalLength);
      ++iNetwork;

   }

   return 0;
}

UVa 167 - The Sultan's Successors

UVa Problem

This is a famous problem of how to arrange 8 queens on a chessboard without having any queen threaten another one (by sharing the same row, column, or diagonal).

This can be solved simply by using recursion and backtracking. We iterate through all rows and try to find a free column to insert the queen into by checking that the cell won't share the same column, left diagonal or right diagonal with another queen, then mark the column, left diagonal and right diagonal as non-free.

this problem has one additional requirement. Each cell on the board is given some value, and as there can be many valid solutions, we wish to find the solution which maximizes the sum of the values of the cells containing the queens.

Solution:

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

class GameSolver
{
public:
   GameSolver(const vector<vector<int> >& board) :
      mBoard(board), mBoardSize(board.size()),
      mCurrMaxScore(0)
   {
      mQueens.reserve(mBoardSize);

      for(int iCol = 0;
            iCol < mBoardSize;
            ++iCol)
         mFreeColumns.push_back(true);

      for(int iDiag = 0;
            iDiag < 2 * mBoardSize - 1;
            ++iDiag)
      {
         mFreeLeftDiags.push_back(true);
         mFreeRightDiags.push_back(true);
      }
   }

   int getMaxScore()
   {
      doSolve(0);
      return mCurrMaxScore;
   }
private:

   void doSolve(int iRow)
   {
      if(iRow == mBoardSize)
      {
         int score = 0;
         for(int i = 0; i < mBoardSize; ++i)
         {
            score += mBoard[i][mQueens[i]];
         }

         mCurrMaxScore = max(mCurrMaxScore, score);
         return;
      }

      for(int iCol = 0; iCol < mBoardSize; ++iCol)
      {
         if(mFreeColumns[iCol] &&
               mFreeLeftDiags
               [iRow - iCol + mBoardSize - 1] &&
               mFreeRightDiags[iRow + iCol])
         {
            mFreeColumns[iCol] = false;

            mFreeLeftDiags
            [iRow - iCol + mBoardSize - 1] = false;

            mFreeRightDiags[iRow + iCol] = false;

            mQueens[iRow] = iCol;
            doSolve(iRow+1);

            mFreeColumns[iCol] = true;
            mFreeLeftDiags
            [iRow - iCol + mBoardSize - 1] = true;
            mFreeRightDiags[iRow + iCol] = true;

         }

      }
   }

   int mBoardSize;
   const vector<vector<int> >& mBoard;
   vector<int> mQueens;
   vector<bool> mFreeColumns;
   vector<bool> mFreeLeftDiags;
   vector<bool> mFreeRightDiags;

   int mCurrMaxScore;

};


int main(int argc, char *argv[])
{
   const int boardSize = 8;

   vector<vector<int> > board;

   for(int iRow = 0; iRow < boardSize; ++iRow)
      board.push_back(vector<int>(boardSize, 0));

   int k;
   cin >> k;

   for(int iBoard = 0; iBoard < k; ++iBoard)
   {
      for(int iRow = 0; iRow < boardSize; ++iRow)
         for(int iCol = 0; iCol < boardSize; ++iCol)
            cin >> board[iRow][iCol];

      GameSolver game(board);
      int score = game.getMaxScore();

      printf("%5d\n", score);

   }

}

UVa 10344 - 23 out of 5

UVa Problem

You have five numbers (a0 ... a4) as input and you're required to determine if there's an arrangment of the numbers and operators (+, -, *) that can give a total value of "23"

the expression must be of the form  ( ( ( a0 o a1) o a2)  o a3) o a4
every "o" can be replaced by any of the above operators "+, -, *" and you can use any permutation of the numbers (order is not required).

Solution:

I solved the problem using recursion and backtracking

#include <iostream>
#include <algorithm>

using namespace std;

bool isReachable(int *numbers, bool *used,
      int numsTotal, int numsAvailable, int valExpr)
{
   if(numsAvailable <= 0)
      return false;
   if(numsAvailable == 1)
   {
      for(int i = 0; i < numsTotal; ++i)
      {
         if(!used[i])
            return valExpr == numbers[i];
      }
      return false;
   }

   for(int i = 0; i < numsTotal; ++i)
   {
      if(!used[i])
      {
         int currNum = numbers[i];
         used[i] = true;

         if(isReachable(numbers, used, numsTotal,
               numsAvailable - 1, valExpr - currNum))
         {
            return true;
         }

         if(isReachable(numbers, used, numsTotal,
               numsAvailable - 1, valExpr + currNum))
         {
            return true;
         }

         if(currNum == 0 && valExpr == 0)
            return true;
         if((currNum != 0) && (valExpr%currNum == 0) &&
               isReachable(numbers, used,
                     numsTotal, numsAvailable - 1,
                     valExpr / currNum))
         {
            return true;
         }
         used[i] = false;
      }
   }
   return false;
}

int main(int argc, char *argv[])
{
   const int finalValue = 23;
   const int arrSize = 5;

   int arrNums[arrSize];
   bool used[arrSize];

   while(cin >> arrNums[0])
   {
      bool exit = (arrNums[0] == 0);

      for(int i = 1; i < arrSize; ++i)
      {
         cin >> arrNums[i];
         if(arrNums[i] != 0)
            exit = false;
      }
      if(exit)
         break;

      for(int i = 0; i < arrSize; ++i)
      {
         used[i] = false;
      }

      if(isReachable(arrNums, used, arrSize,
            arrSize, finalValue))
         cout << "Possible" << endl;
      else
         cout << "Impossible" << endl;

   }
   return 0;
}

UVa 100 - The 3n + 1 problem

UVa Problem

#include <iostream>
#include <algorithm>

using namespace std;

int main(int argc, char *argv[])
{
   int t1, t2;

   while(cin >> t1)
   {
      cin >> t2;

      int start, end;

      start = t1;
      end = t2;

      if(start > end)
         swap(start, end);

      int maxCycleLen = 1;

      for(int num = start; num <= end; ++num)
      {
         int cycleLen = 1;
         int currNum = num;

         while(currNum != 1)
         {
            if(currNum%2 == 0)
               currNum /= 2;
            else
               currNum = 3 * currNum + 1;

            ++cycleLen;
         }
         maxCycleLen = max(maxCycleLen, cycleLen);
      }

      cout << t1 << " " << t2 << " " << maxCycleLen << endl;
   }

   return 0;
}

UVa - 10392 - Factoring Large Numbers

Problem on UVa


Problem F: Factoring Large Numbers

One of the central ideas behind much cryptography is that factoring large numbers is computationally intensive. In this context one might use a 100 digit number that was a product of two 50 digit prime numbers. Even with the fastest projected computers this factorization will take hundreds of years.

You don't have those computers available, but if you are clever you can still factor fairly large numbers.

Input

The input will be a sequence of integer values, one per line, terminated by a negative number. The numbers will fit in gcc's long long int datatype. You may assume that there will be at most one factor more than 1000000.
Output

Each positive number from the input must be factored and all factors (other than 1) printed out. The factors must be printed in ascending order with 4 leading spaces preceding a left justified number, and followed by a single blank line.

#include <iostream>
#include <vector>

const int N = 1000000;

using namespace std;

vector<int> primes;

void sieve(void)
{
   vector<bool> nums(N+1, true);

   for(int i = 2; i * i <= N; ++i)
   {
      if(nums[i])
      {
         for(int j = i * 2; j <= N; j += i)
         {
            nums[j] = false;
         }
      }
   }

   for(int i = 2; i <= N; ++i)
   {
      if(nums[i])
      {
         primes.push_back(i);
      }
   }
}

int main(int argc, char *argv[])
{
   sieve();

   long long num;

   while(cin >> num)
   {
      if(num < 0)
         break;

      for(int i = 0; (i < primes.size()) &&
         (primes[i] <= num); ++i)
      {
         while( (num % primes[i]) == 0)
         {
            cout << "    " << primes[i] << '\n';
            num /= primes[i];
         }
      }

      if(num > N)
      {
         cout << "    " <<  num << '\n';
      }

      cout << endl;
   }

   return 0;
}

UVa - 10533 - Digit Primes

Problem on UVa

A prime number is a positive number, which is divisible by exactly two different integers. A digit prime is a prime number whose sum of digits is also prime. For example the prime number 41 is a digit prime because 4+1=5 and 5 is a prime number. 17 is not a digit prime because 1+7 = 8, and 8 is not a prime number. In this problem your job is to find out the number of digit primes within a certain range less than 1000000.



Input

First line of the input file contains a single integer N (0<N<=500000) that indicates the total number of inputs. Each of the next N lines contains two integers t1 and t2 (0<t1<=t2<1000000).



Output
For each line of input except the first line produce one line of output containing a single integer that indicates the number of digit primes between t1 and t2 (inclusive).

#include <cstdio>

#define N 1000000

bool primes[N+1];
int digitPrimes[N+1];

void sieve(void)
{
    for(int i = 0; i <= N; ++i)
    {
        primes[i] = true;
        digitPrimes[i] = 0;
    }

    primes[0] = primes[1] = false;

    for(int i = 2; i * i <= N; ++i)
    {
        if(primes[i])
        {
            for(int j = 2 * i; j <= N; j += i)
            {
                primes[j] = false;
            }
        }
    }

    int countDigPrimes = 0;

    for(int i = 2; i <= N; ++i)
    {
        if(primes[i])
        {
            int tmp = i;
            int sumDigits = 0;

            while(tmp)
            {
                sumDigits += tmp%10;
                tmp /= 10;
            }

            if(primes[sumDigits])
            {
                ++countDigPrimes;
            }
        }
        digitPrimes[i] = countDigPrimes;
    }
}

int main(int argc, char *argv[])
{
    int numLines;

    int t1, t2;

    sieve();

    scanf("%d", &numLines);

    for(int iLine = 0; iLine < numLines; ++iLine)
    {
        int numDigiPrimes;

        scanf("%d %d", &t1, &t2);

        if(t1 == 0)
            numDigiPrimes = digitPrimes[t2];
        else
            numDigiPrimes = digitPrimes[t2] - digitPrimes[t1 - 1];
        printf("%d\n", numDigiPrimes);
    }

    return 0;
}

UVa - 10168 - Summation of Four Primes

UVa - 10168 - Summation of Four Prime

My solution relies on Goldbach's conjecture which states that "Every even integer greater than two can be expressed as the sum of two primes".

This conjecture has been proved right up until 4 * 10 ^ 80.
In this problem, we'll have an N with a maximum value of 10 ^ 7, so we can use the conjecture safely.

The problem simply gives you an integer N and you're required to find four primes that sum up to that integer or output "Impossible" if you can't find them.

sieve is an algorithm that marks prime numbers from 2 to N. It works this way, starts from 2 and marks all multiples of 2 as "not primes", then it goes to 3 and marks all multiples as "not primes" then "4" but found out that "4" is already marked as composite so it doesn't need to mark its multiples which must be already marked and so on.

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

vector<bool>* sieve(int n)
{
    vector<bool>* pNums = new vector<bool>(n+1, true);
    vector<bool>& nums = *pNums;
    nums[0] = nums[1] = false;

    for(int i = 2; i * i <= n; ++i)
    {
        if(nums[i])
        {
            for(int j = 2 * i; j <= n; j += i)
            {
                nums[j] = false;
            }
        }
    }

    return pNums;
}

int main(int argc, char *argv[])
{
    const int N = 10000000;
    vector<bool> *pNums = sieve(N);
    vector<bool> &nums = *pNums;

    int n;

    while(cin >> n)
    {
        if(n < 8)
            cout << "Impossible." << endl;
        else
        {
            int remainingSum;

            if(n%2 == 0)
            {
                cout << "2 2 ";
                remainingSum = n - 4;
            }
            else
            {
                cout << "2 3 ";
                remainingSum = n - 5;
            }

            int i;
            for (i = 2; i < remainingSum;++i)
            {
                if(nums[i] && nums[remainingSum-i])
                {
                    cout << i << " " << remainingSum - i << endl;
                    break;
                }
            }
            if(!(nums[i] && nums[remainingSum-i]))
                cout << "Impossible." << endl;
        }
    }
    delete pNums;
    return 0;
}

UVa 10219 - Find the ways !

UVa 10219 - Find the ways !

So in this problem, we are given as input (n, k) and we are required to calculate the number of digits in "n choose k".

for instance, "10 choose 5" equals "252", so we should print "3" as "252" has 3 digits.

one simple way to solve this is to calculate "n choose k" using dynamic programming and count the number of digits found. However, this will use a lot of memory and there's a simpler approach to the problem.

We all know that (n choose k) equals n!/(k! * (n - k)!)
We also know that the number of digits of "n" equals log10(n)+1
and we also know that log(a * b) = log (a) + log (b)

then the number of digits in "n choose k" = the number of digits in n!/(k! * (n - k)!) = log(n!) - log(k!) - log (n - k)!

and we know that log(n!) = log(1) + log(2) + log(3) + .... + log(n)

this gives the following solution to the problem

/*
 * Main.cpp
 *
 *  Created on: Jun 7, 2013
 *      Author: usama
 */
#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

const int N = 1000000;

vector<double> cache(N+1, 0);

void digitsFact(int n)
{
    double result = 0;

    for(int i = 2; i <= n; ++i)
    {
        result += log10(i);
        cache[i] = result;
    }
}

int digitsCombin(int n, int k)
{
    int result = 1;
    result += (int)(cache[n] - cache[k] - cache [n - k]);
    return result;
}

int main(int argc, char *argv[])
{
    int n, k;
    digitsFact(N);
    while (cin >> n)
    {
        cin >> k;
        if(n == k)
            cout << "1" << endl;
        else if(n < k)
            cout << "1" << endl;
        else
        {
            if(n >= cache.size())
            {
                double result = cache[cache.size()-1];
                for(int i = cache.size(); i <= n; ++i)
                {
                    result += log10(i);
                    cache.push_back(result);
                }
            }
            cout << digitsCombin(n, k) << endl;
        }
    }
    return 0;
}

Back to Programming!

Since I have some free time, actually plenty of it! I decided to spend some of my time solving problems at UVA and TopCoder, I also decided to use this blog to post my solutions to some of the problems I'm going to solve.

See you soon!
Usama

Find the start of a linked list loop in O(n) Part 2

Hi again

In the previous post, I wrote about how you can do it in O(n²), now we will do it in O(n).

There's a trivial solution using a hashtable but it will require O(n) extra storage, however, we will attempt to solve it without the O(n) extra storage.

Let's start thinking about how we can do it for a while.

Imagine for instance that we only have a circle and two pointers running in it. One is called "slow" and is at position "0", the other is called "fast" and moves double the speed of slow and is also at position "0". If we start moving them at their relative speeds, when will they meet? fast will complete a cycle when slow is at the middle of the lap then they will meet again at the start point when fast completes two cycles and slow will have completed only one. Now suppose fast has a head-start of "1" position before they start the race. It will meet slow "1" step before the start point", the same applies if it had a head-start of 2, 3, 4, etc.

Now to generalize, have two pointers "fast" and "slow" with fast moving the double speed of "slow" and is "k" steps ahead of slow. they will meet at "k" steps before the start point.

Back to our problem, if we start moving "fast" and "slow" from the head of the above list and consider the length of the line segment before the start of the loop to be "k". Then "slow" will be at the start of the loop while "fast" will have moved "2k" steps from the head of the list, that is, it will be "k" steps ahead of "slow". If we move both of them until they meet. we know they will meet at "k" steps before the start of the loop.

now we start a new point "slow2" and point it to the head of the list, and move it at the same speed with "slow". They will meet after "k" steps at the start of the loop. and we've got our solution in O(n) !

I will post C code for this later.

Find the start of a linked list loop in O(n) Part 1

As for a second post, I decided that it'll be a technical one. I will start publishing solutions to problems that may sound kinda hard.

I'll start with this problem:

Problem: You have a circular linked. Find the node that is the start of the list in O(n).

Now lets first see how we do it in O(n²). This should be easy, you start with two pointers : ahead and behind, you start with ahead = list_head->next and behind = list_head. At each step, you check if ahead->next == behind, if this is the case, then"behind" is the start of the loop, if not, then set "behind" = "behind->next" till "behind" == "ahead". Then repeat the whole thing for the next element in the list.

This should be something like this

if(head == NULL || head->next == NULL)
   return ERROR



for(ahead = head->next; ahead != NULL; ahead = ahead->next)
   for(behind = head; ; behind = behind->next)
      if(ahead->next == behind)
         return behind as the head of the list;
      else if (behind == ahead)
         break;
      else
         behind = behind->next

return ERROR

That's how we do it in O(n²). In the next part I'll show you how we do it in O(n).
Stay tuned.
      

Back again!

So it's been years since I last posted anything in a blog. This blog is gonna be where I post my thoughts, my ideas, my opinions and any random thing that comes up to my mind.

Some of the posts are going to be technical, reflecting my passion for programming, and some are not. Feel free to pass by anytime, you're more than welcome!

See you soon.