RSS

Tag Archives: java

Facebook Hacker Cup Qualification Round

So. I have a final later today and I’m too bored of studying so I decided to write up a post on the latest Facebook Hacker Cup competition problems. As you may know, this past weekend, Facebook had the Qualification Round of their Hacker Cup. Basically, it’s a programming contest very similar to that of Google Code Jam that I mentioned a while back and follows a pretty regular format.

In this round, we only had to answer one question out of three correctly to qualify. I did qualify so I know I got at least one right. Strangely, they only tell you the results after the competition is over, which is both weird and annoying. Oh and they messed up sending out the emails to the people who qualified. I made an incredibly dumb error in that I accidentally downloaded the input file before I was done writing my code and so the 6-minute time limit expired before I could submit my result. Fortunately, Facebook lifted this six-minute restriction due to bugs in their system so my (eventual correct) solution was actually accepted. The problem description and my solution is listed below:

Double Squares

I can’t actually access the original question right now so I’m paraphrasing here. Effectively, we are given an input file with the first line being N, the number of lines that follow. Each of those lines contain an integer between 0 and 2147395600, inclusive. (Not 100% sure if that’s the right number exactly but its within that range). The solution should contain one integer per line of input containing the number of ways that the number can be written (order doesn’t matter) as a sum of two squares.

Solution

There was a very nice little hint in light gray at the top of the problem page that effectively said:

too hard for brute force, switch to dp

Nice. Gladly, I saw that and immediately switched to a smarter algorithm (I wasn’t sure how hard these problems were and I wasn’t going to waste time writing a sophisticated algorithm if it was unnecessary – although my solution is pretty straightforward for this problem).

First, I used a calculator to compute the square root of that number. It was in the order of about 46,000, which is still small enough that pre-computing a data structure of that size is not out of the question. Further, since that number fits comfortably within the range of double-precision numbers, there was nothing special I needed to do. I started off by generating an ArrayList<Double> of each of the numbers from 0 to 46,342 squared. This actually executed faster than I thought it would and so I continued along this idea. (Note: For use in the DP algorithm I will describe, a HashSet would be a faster data structure although since I couldn’t perform a binary search on it, I decided to use an ArrayList. Since this is performed only once per input line, I didn’t stress too much about it.) Next, having performed the binary search of the input number on my giant list, I computed and stored the index of the greatest value less than or equal to the number itself.

With this index, I created a second array which contained numbers only less than or equal to it. The logic here is that since all our numbers are non-negative (indeed, the squares of all real numbers are non-negative), each of the addends must be less than or equal to the number (remember, 0 is on the list too). Now having generated this sub-array, I traverse it and subtract each element of it from the input number itself. This is effectively subtracting one of the squares from the number. What is the reason for this? To check if the remaining quantity is a perfect square and if so, to note that the resulting pair is one that we are seeking. I used some quick and dirty counting scheme of adding a half for each time I saw this (since we will be hitting upon commutative pairs) and adding a whole number for the number itself. Then we simply return the count that we have accumulated.

Very simple algorithm and runs pretty fast. We do a constant amount of pre-processing so total time for that \mathcal{O}(1). Now if our number is K, then binary searching for it runs in time complexity \mathcal{O}(1) time (remember, the size of the big array is fixed). Creating the sub-array and traversing it and subtracting it from the original number runs in \mathcal{O}(\sqrt{K}) time and traversing the list to search for numbers in the original list runs in \mathcal{O}(\sqrt{K} \cdot 1) = \mathcal{O}(\sqrt{K}) time (remember again, the big array has a fixed size!). Thus, our total running time complexity for each query (input number) is also \mathcal{O}(\sqrt{K}). One optimization would be to not search the big list for a match for every number in the sub-array but rather just until \lfloor \frac{\sqrt{K}}{2} \rfloor indices and then multiplying the count by two. In addition, if I had used a HashSet for the big array instead, we would enjoy amortized constant time searching which would give us a time complexity of \mathcal{O}(\sqrt{K}), which is the same big-Oh time complexity but much faster if you write it in tilde notation.

import java.util.*;
import java.io.*;

public class Main
{
    int SIZE = 46342;
    ArrayList<Double> squares;

    public Main()
    {
        squares = new ArrayList()<Double>;

        for (int i = 0; i < SIZE; i++)
            squares.add(Math.pow(i, 2));

        solve();
    }

    private void solve()
    {
        Scanner in = new Scanner(System.in);

        int N = in.nextInt();

        for (int i = 0; i < N; i++)
            output(in.nextDouble());
    }

    private void output(double i)
    {
        if (i <= 1)         
        {            
           System.out.println("1");             
           return;         
        }
        
        double num = 0.0;
        int index = Collections.binarySearch(squares, i);
        if (index > 0)
            num++;

        index = (index >= 0) ? index: Math.abs(index) - 1;

        ArrayList subList = new ArrayList();

        for (int j = 1; j < index; j++)
            subList.add(i - squares.get(j));

        for (int j = 0; j < index - 1; j++)
             if (Collections.binarySearch(squares, subList.get(j)) >= 0)
                num += 0.5;

        System.out.println((int)num);
    }

    public static void main(String args[])
    {
        Main app = new Main();
    }
}

On my computer, running Ubuntu 32-bit and OpenJDK with Core 2 Duo processors at 2.53GHz, the total time taken to run this program on the input file given was 0.264s.

Advertisements
 
2 Comments

Posted by on January 12, 2011 in Uncategorized

 

Tags: , , , , ,

Google Code Jam 2010 Qualifying Round Solutions (Part 3)

Finally, my solution for the Theme Park problem. For this one as well, I had a somewhat optimized solution that brought down 10^8 iterations to at most 2000, with an average case of around 500-750 iterations. The solution, again in Java, is below:

import java.util.*;
import java.io.*;

public class Theme_large
{
   String filename;
   ArrayList<Group> groups;

   public Theme_large(String f)
   {
      filename = f;
      openFiles();
   }

   private void openFiles()
   {
      Scanner s;

      try
      {
         s = new Scanner(new File(filename));
         int ct;
         long R, k;
         int N;

         ct = s.nextInt();

         for (int i = 0; i < ct; i++)
         {
            R = s.nextLong();
            k = s.nextLong();
            N = s.nextInt();
            groups = new ArrayList<Group>();

            for (int j = 0; j < N; j++)
               groups.add(new Group(s.nextLong()));

            //System.err.print((i+1) + ": ");
            output(i + 1, process(R, k, N));
            //System.err.println();
         }

         s.close();
      }
      catch (Exception e)
      {
         System.err.println("I/O error: " + e);
         System.exit(0);
      }
   }

   private long process(long R, long k, int N)
   {
      long r = 0;
      int n = 0;
      long totEarn = 0;
      long k_i;
      int n_start = 0;
      long first;

      if (N == 1)
         return groups.get(0).getSize() * R;
      // loop as many times as necessary to start at same spot
      // again.
      while (r < R)
      {
         k_i = 0L;
         n_start = n;

         // check if you've already started here - a cycle
         if (groups.get(n_start).isHit())
            break;

         // set earnings at start
         groups.get(n_start).setEarn(totEarn);

         while (true)
         {
            // if adding the next group will exceed k, break
            if (k_i + groups.get(n).getSize() > k)
            {
               totEarn += k_i;
               // hit the one you started on.
               groups.get(n_start).hit();
               groups.get(n_start).setR(r);
               break;
            }
            else
            {
               k_i += groups.get(n).getSize();
               n = (n + 1) % N;
            }

            // one group can't ride more than once at the same
            // time!
            if (n == n_start)
            {
               totEarn += k_i;
               // hit the one you started on.
               groups.get(n_start).hit();
               groups.get(n_start).setR(r);
               break;
            }
         }

         r++;
      }

      if (r == R)
         return totEarn;

      long loopCt = groups.get(n_start).getR();
      first = groups.get(n_start).getEarn();

      long quo = (R-loopCt) / (r-loopCt);
      // how many full cycles will exist; round down

      totEarn = first + ((totEarn - first) * quo);
      // find that totEarn
      r = loopCt + ((r-loopCt) * quo);
      // effectively performed that many cycles

      // do loop again to take care of remainder, ignore hits

      while (r < R)
      {
         k_i = 0L;
         n_start = n;

         while (true)
         {
            // if adding the next group will exceed k, break
            if (k_i + groups.get(n).getSize() > k)
            {
               totEarn += k_i;
               break;
            }
            else
            {
               k_i += groups.get(n).getSize();
               n = (n + 1) % N;
            }

            // one group can't ride more than once at the same
            // time!
            if (n == n_start)
            {
               totEarn += k_i;
               break;
            }
         }

         r++;
      }

      return totEarn;
   }

   private void output(int caseNum, long result)
   {
      System.out.println("Case #" + caseNum + ": " + result);
   }

   public static void main(String args[])
   {
      Theme_large app = new Theme_large(args[0]);
   }
}

class Group
{
   private long size;
   private boolean hit;
   private long totEarn;
   private long r;

   public Group(long i)
   {
      size = i;
      hit = false;
      totEarn = 0;
      r = 0;
   }

   public void hit() { hit = true; }

   public boolean isHit() { return hit; }

   public long getSize() { return size; }

   public void setEarn(long e) { totEarn = e; }

   public long getEarn() { return totEarn; }

   public void setR(long rr) { r = rr; }

   public long getR() { return r; }

}

In this solution, I realized that we should just think of the line as a cyclic graph component (or, equivalently, a circular linked-list) and think of the roller coaster car as moving around the cycle. Eventually, I thought, we’re going to start someplace we started before. And if we do it once, we’ll probably do it again and again. But we already know how much money will be earned by that! So, the code first begins executing normally, but dropping “markers” every time it starts somewhere. If it sees that it has already start here, we have just found ourselves a cycle! The additional fields in the Group class just store information about how many rides there are in a cycle and how much money is made in a cycle. From this information, we can jump ahead many, many simulations of the roller coaster until we have fewer rides remaining than the length of  a cycle. From this point on, the program executes in a very simple fashion to the end. A slightly better approach would be to store the amount made in each Group element and so compute the remaining amount in constant time. But nevertheless, I was happy with this solution. The solution, on a 2.53 GHz Core 2 Duo processor, ran in 0.442s.

And that concludes this Google Code Jam solution series.

 
Leave a comment

Posted by on May 13, 2010 in Uncategorized

 

Tags: , , , ,

Google Code Jam 2010 Qualifying Round Solutions (Part 2)

Here’s my solution to Fair Warning Large input. It’s actually very similar to my Small input solution except that longs are replaced with BigIntegers (and it’s designed to handle cases larger than 3. Anyway, here’s my solution:

import java.util.*;
import java.io.*;
import java.math.*;

public class Fair_large
{
   String filename;
   ArrayList<BigInteger> list;
   ArrayList<BigInteger> diffs;

   public Fair_large(String f)
   {
      filename = f;
      openFiles();
   }

   private void openFiles()
   {
      Scanner s;

      try
      {
         s = new Scanner(new File(filename));
         int ct;

         ct = s.nextInt();

         for (int i = 0; i < ct; i++)
         {
            list = new ArrayList<BigInteger>();
            diffs = new ArrayList<BigInteger>();
            int ct2 = s.nextInt();

            for (int j = 0; j < ct2; j++)
               list.add(new BigInteger(s.next()));

            output(i + 1, process(ct2));
         }

         s.close();
      }
      catch (Exception e)
      {
         System.err.println("I/O error: " + e);
         System.exit(0);
      }
   }

   private String process(int length)
   {
      Collections.sort(list);
      BigInteger T = BigInteger.ZERO;

      if (length == 2)
      {
         T = list.get(1).subtract(list.get(0));

         if (T.equals(BigInteger.ONE))
            return "0";

         return distToNextMultiple(list.get(0), T).toString();
      }

      for (int i = 1; i < list.size(); i++)
         diffs.add(list.get(i).subtract(list.get(i - 1)));

      while (diffs.size() > 1)
         diffs.add(0, diffs.remove(0).gcd(diffs.remove(0)));

      T = diffs.get(0);

      if (T.equals(BigInteger.ONE))
         return "0";

      return distToNextMultiple(list.get(0), T).toString();
   }

   private BigInteger distToNextMultiple(BigInteger x,
                                         BigInteger T)
   {
      return T.subtract(x.mod(T)).mod(T);
   }

   private void output(int caseNum, String result)
   {
      System.out.println("Case #" + caseNum + ": " + result);
   }

   public static void main(String args[])
   {
      Fair_large app = new Fair_large(args[0]);
   }
}

So in this solution, I did use some simple optimizations to reduce the amount of actual computation needed to produce my solution. First, I handled the 2 case by itself since you don’t actually need to use GCD for that. I created an auxiliary array called diffs that holds the differences between consecutive numbers (in the sorted array). Thus, we know that adding some y \geq 0 does not change the differences between them; so, if they must all be multiples of T, then their differences must already be multiples of T. Then, the GCD of the all the numbers of the auxiliary array is calculated. In my small input solution I wrote a slightly optimized (non-recursive – to save on mem read/writes on the stack) GCD function based on Euclid’s algorithm. At some point I also used Stein’s algorithm for the GCD calculation. But for the large input, I decided to just use the built-in GCD function that comes with BigInteger.

One key property that I exploited was that:

\gcd(x_1, x_2, \ldots, x_n) = \gcd(\cdots\gcd(\gcd(x_1, x_2), x_3)\cdots)

Thus, I computed the GCD of two consecutive numbers (the first two of the aux array), removed both, and added in their GCD. Continuing in this way until there was only one element left, I had computed the GCD of all the numbers with reasonable speed. The other interesting function was the distToNextMultiple function.

Mathematically, this function returns:

(T-(x \mod T))\mod T

We know that if x < T then x \equiv x \mod T but otherwise, it is the remainder after division by T. Subtracting this value from T gives how much is left until the next multiple. But why the extra modulus T? If x \equiv 0 \mod T, then T - (x \mod T) yields T , which is wrong. Thus, the extra modulus T takes care of this case.

And that’s pretty much it. A pretty simple solution that works quickly. On the same Core 2 Duo machine, the solution for the large input runs in 0.436s. Good enough for me.

 
1 Comment

Posted by on May 13, 2010 in Uncategorized

 

Tags: , , , ,

Google Code Jam 2010 Qualifying Round Solutions (Part 1)

Okay so now I’ll post some of my solutions for Google Code Jam Qualifying Round 2010. The first one was called the Snapper problem. You can read the description of the problem here.

This solution was a very, very simple brute force solution. It worked well for the small input but obviously did not work for the large input. Anyway, here it is:

import java.util.*;
import java.io.*;

public class Snapper
{
   String filename;

   public Snapper(String f)
   {
      filename = f;
      openFiles();
   }

   private void openFiles()
   {
      Scanner s;

      try
      {
         s = new Scanner(new File(filename));
         int ct;

         ct = s.nextInt();

         for (int i = 0; i < ct; i++)
            output(i + 1, process(s.nextInt(), s.nextInt()));

         s.close();
      }
      catch (Exception e)
      {
         System.err.println("I/O error: " + e);
         System.exit(0);
      }
   }

   private String process(int N, int K)
   {
      ArrayList<Snap> list = new ArrayList<Snap>();

      for (int i = 0; i < N; i++)
         list.add(new Snap());

      // first one has power
      list.get(0).flipPower();

      // snap, snap, snap yo fingers!
      for (int i = 0; i < K; i++)
      {
         // if it has power, flip its state
         for (int j = 0; j < N; j++)
         {
            if (list.get(j).getPower())
               list.get(j).flipState();
         }

         int j = 1;

         // turn on power of all those whose prev's
         // state & power is on
         for (; j < N; j++)
         {
            if (list.get(j - 1).getState() &&
                list.get(j - 1).getPower())
               list.get(j).onPower();
            else
               break;
         }

         // j is the index of the first snapper whose prev's
         // state is off
         // turn rest's power off
         for (; j < N; j++)
            list.get(j).offPower();
      }

      // check if all powers and all states are on.
      int i = 0;

      for (; i < N; i++)
      {
         if (!list.get(i).getState() || !list.get(i).getPower())
            break;
      }

      return (i == N) ? "ON" : "OFF";
   }

   private void output(int caseNum, String result)
   {
      System.out.println("Case #" + caseNum + ": " + result);
   }

   public static void main(String args[])
   {
      Snapper app = new Snapper(args[0]);
   }
}

class Snap
{
   private boolean state;
   private boolean power;

   public Snap()
   {
      state = false;
      power = false;
   }

   public void  flipState() { state = !state; }

   public void flipPower() { power = !power; }

   public boolean getState() { return state; }

   public boolean getPower() { return power; }

   public void offPower() { power = false; }

   public void onPower() { power = true; }

}

I know that it’s super long and unnecessarily OOP’d, but it was my first solution so I figured it was okay. The solution (for small input) ran in 0.647s on an Intel Core 2 Duo 2.53 GHz, 4GB RAM, running Ubuntu 10.04.

The approach is pretty much self-explanatory so I won’t go into the details of it. It’s also sorta commented so you can figure out what I did. Obviously, I could have made it more efficient but it got me the answer quickly anyway so life’s good.

 
2 Comments

Posted by on May 13, 2010 in Uncategorized

 

Tags: , , , ,