**An n×n grid of squares contains n^2 ants, one ant per square.**

**All ants decide to move simultaneously to an adjacent square**

**(usually 4 possibilities, except for ants on the edge of the grid or at the corners).**

**We define f(n) to be the number of ways this can happen without any ants ending on**

**the same square and without any two ants crossing the same edge between two squares.**

**You are given that f(4) = 88. Find f(10).**

So where to start? Well, if Mr. Intelligence is not around you can always trust in your old pal the Brute Force. In this post I sketched the code for computing (and drawing) all the different board positions for (n = 4) using a DFS algorithm:

If this were the case the time my computer would take to compute 10^9 boards would be nearly 0.8 seconds (with an Intel Core 2 Duo at 2.4 GHz for processor). Lets round that time to one second for 10^9 boards, therefore it would take (2^100/10^9) seconds to compute all the other boards. This is more than 40 millions of millions of years! Forever. However, this is just a wild guess, we'll see that the constraints in this particular problem are a lot more restrictive and that the real answer is not that big, (more in the order of 2^57) and I'll need to await "only" 1300 days to get the answer.

So, How do we compute this faster? This is where DP comes to save the day. The main idea behind DP is to construct the final answer from the smaller parts. What is the smallest part in this problem? A single cell.

**We need to find a way to construct the final board adding one cell in every step**. With every added cell we need to maintain the list of incomplete boards already formed. The total number of these boards when the whole board is assembled is our answer. Easier said than done, let's go step by step. What are the valid moves for the first cell?

The tree below shows the whole process for (n = 2) considering only valid moves. Every node is an incomplete board and their children are linked by lines. Every step is a row in the graph. The cell that we'll add to our zone in the next step in marked with a red border. As expected there are only 2 ways to assemble the final board:

The first observation looking at the above graph is that in every step not all the cells are required to deduce the next board, all the action is happening in the border between the zone and the empty board, so we could ignore all the board cells except the cells at the zone frontier (the ones marked with red at the right):

How much time would take this algorithm to find the answer? Every cell has 4 options, there are (n) cells in the border, so in every step would be a maximum of (4^n) nodes, there are (n^2) steps (one step for every cell) so we could guess it would take (n^2)*(4^n) steps to find the answer (if we use a hash data container to look for duplicated nodes in constant time). For (n = 10) this is 100*4^10 (nearly 10^8). We can finish this in C in less than a second! This is an impressive improvement compared to awaiting 1300 days.

I hope that with this explanation you are ready to code the solution for yourself. However, if that is not the case, there is not helping but sitting with a pencil and paper and trying by hand the above steps. The little fella below approves:

## No comments:

## Post a Comment