SPOJ QUEEN

Problem Source: SPOJ Problem Set (classical): 4235. Wandering Queen

Basically you are given a grid with a start and end point along with some obstacles. You have to reach end point using smallest number of standard chess queen moves.

The first idea that pops into mind is using BFS, along with states for 8 direction. In this case, the complexity is around 8 * 256 * 1000 * 1000. Anyone who is a bit familiar with SPOJ engine, knows that, this solution will definitely get a "Time Limit Exceed" verdict.

The catch is, it doesn't matter for a standard chess queen from which direction you reach a particular cell in terms of cost. A queen moves toward 8 directions as long as nothing is blocking her paths and the cost remains the same. So, whenever you reach a cell, you will want to traverse all of the 8 possible directions from that cell. If you maintain the previous direction, the cost will not change, and if you change direction, the cost will be increased by 1. Fortunately, we can maintain the BFS property without keeping extra states for direction simply by adding a parallel flag array and modifying how we choose the next cell.

Although there are 8 possible directions, we have only 2 different scenarios, namely: whether we want to change direction or not. Instead of keeping states for direction changes, we will visit all cells in a particular direction from a specific cell before traversing from other cells and pushing them into a queue as usual. Following this, we can visit all the reachable cells from a particular cell in a single move. During this process, we will store the bit-masked flags for direction in a parallel array. Now, when we meet a new cell, there are four possible scenarios.

1 ⇒ The cell is out of the grid or contain an 'X', simply stop moving in that direction anymore.

2 ⇒ The flag value for this cell already has the bit for current direction set to 1. It means, going in this direction doesn't do anything helpful anymore.

3 ⇒ The flag value for this cell doesn't contain bit for current direction, but it has been visited form different direction earlier. We just skip this cell and continue with the direction. Note: This step is important to understand. Because at first this may seem like, we can just stop here as the cell is already in the queue and will be traversed later. But thinking carefully, you will find out that, your current move will definitely have a lower or equal cost than the current cell which resides in the queue will have (obvious BFS property). So, we may still need to update the rest of the cells following the direction. Although we skip this cell, we update its flag value to mark the direction from which it was visited. See sample case 2, that explains the necessity of this step.

4 ⇒ New cell, we visit it, do regular BFS stuffs like updating cost, pushing into queue, and additionally, we mark the direction from which it was visited in the flag array.

Oh, and ofcourse, flag for the start cell should have all the bits set. Now, we visit each cell at most 8 times for each direction, but we push each cell only once into the queue. Thus, we are able to remove the 256 different bitmasked states, and the solution is more likely to pass the time limit.

Following this procedure, I got accepted in 2.56 with STL queue, and no IO optimization. I am having a feeling that, this problem can be solved more efficiently. So, don't forget to share your idea on this problem.

Repository Transfer

Finally I have removed all of my github repositories. I have been getting request from a lot of people for removing the repositories or making them private. As github charges too much for maintaining private repositories, I have decided to switch to bitbucket, another wonderful free git server. All of my repositories are set as private. Sorry for the inconvenience. There are already plenty of sites where one can find solutions for online judge problems. My repositories were never intended to be known as a place where you get all the beautiful solutions and then just copy-paste them from your account. That is just meaning-less, stupid and of no good use of-course. Still if you want to see any of my noob-ish solutions, please send me an email.

Thanks for understanding and happy problem solving. I think I am now retired from all these beautiful little things. I will miss these programming contests forever...

Various Usage of B.I.T.

I’ve always imagined what BIT (I will omit the dots, but don't confuse it with binary bits) can do and can’t. I have seen numerous times, experienced solvers say “Oh it’s easily solvable using BIT” leaving me wondering, “BIT on this problem! How on earth!” Still I haven’t found quite a good answer for this question. Looks like BIT can do as much as you can imagine it to do (and obviously design it to do so).

However, I am not going to explain the structure of BIT or how it works etc. As there are lots of well documented articles available on the net. I can’t help putting one specific link here, which is a TopCoder algorithm tutorial for BIT. So, if you are not familiar with BIT yet, first go ahead, and read that post.

In this post, we will discuss some of the most common application of BIT for solving data structure related problems, more specifically, where range sum updates and queries are involved.

Some methods used in this post:
Update(x, v): Adds V at the position x in BIT.
Query(x): Returns the cumulative value on position x in BIT.
Read the above tutorial to know how these methods are implemented.
We will be using 1-based indexing throughout the post.

(I) Point Update, Range Query:

This is the most common form of BIT, and just about 99% of online tutorials you will find on the net will describe this application. So here we don't have much to say. If your updates are like “Add v in the x position of the array”, and queries are like “What is the sum of elements in index range [a, b] in the array?”, then all you do for update is call Update(x, v) and answer queries by Query(b) - Query(a-1). Simple cumulative sum formula, nothing really astonishing. This problem is can be solved using BIT: SPOJ - MSE06H.

(II) Range Update, Point Query:

Although not something you see every now and then, but it's readily doable. Now you are required to update v over the range [a, b] and the query is performed on a single index x. So now you call update twice, first add v at index a, then remove v for indices larger than b, which is: Update(a, v); Update(b+1, -v); And for query, you simply call Query(x). Now to see why this works, the following reasoning can be made:

Lets consider, initially you have everything 0. So Query(x) will return 0, no matter what index you call it with. Suppose you have called Update(a, v) and Update(b+1, -v). Now what will happen if you call Query(x)? Three cases can arise:
1. if x < a, the query is not affected by the updates. So you get correct result.
2. if x > b, x will be affected by the update(a, v) since x ≥ a, and update(b+1, -v) since x ≥ b+1, therefore, v-v=0 so everything cancels out. Again, you get the correct result.
3. a ≤ x ≤ b. x is only affected by update(a, v), but not update(b+1, -v), therefore, Query(x)'s value is increased by v, and it will return the correct result.

As we can see, in this fashion, we can increment or decrement for a range [a, b], and get a single index effect for some index x. This problem is an example: SPOJ - UPDATEIT

(III) Range Update, Range Query:

I didn't even know it exists until I read some post in TopCoder forums (the post was made by: AnilKishore).

I will just re-state his explanation as it was quite clear itself. All we want here is to support range updates, and do range queries. As from the previous type, if we try to store range updates, the BIT structure effectively captures updates for single positions, instead of range/cumulative sums. However, we can do some tweaking to work around this problem.

Let's just consider only one update: Add v to [a, b] while the rest elements of the array is 0.
Now, consider sum(0, x) for all possible x, again three situation can arise:
1. 0 ≤ x < a : which results in 0
2. a ≤ x ≤ b : we get v * (x - (a-1))
3. b < x < n : we get v * (b - (a-1))

This suggests that, if we can find v*x for any index x, then we can get the sum(0, x) by subtracting T from it, where:
1. 0 ≤ x < : Sum should be 0, thus, T = 0
2. a ≤ x ≤ : Sum should be v*x-v*(a-1), thus, T = v*(a-1)
3. b < x < n : Sum should be 0, thus, T = -v*b + v*(a-1)

As, we can see, knowing T solves our problem, we can use another BIT to store this additive amount from which we can get:
0 for x < a, v*(a-1) for x in [a..b], -v*b+v(a-1) for x > b.

Now we have two BITs.
To add v in range [a, b]: Update(a, v), Update(b+1, -v) in the first BIT and Update(a, v*(a-1)) and Update(b+1, -v*b) on the second BIT.
To get sum in range [0, x]: you simply do Query_BIT1(x)*x - Query_BIT2(x);
Now you know how to find range sum for [a, b]. Just find sum(b) - sum(a-1) using the formula stated above.

Pretty impressive this one! SPOJ - HORRIBLE can be solved in this approach. And thanks to Iqram Mahmud for this nice problem.

(IV) 2D BIT

How to write Update and Query methods for 2D BIT is well described in the TopCoder tutorial I've mentioned above. The only thing to notice here is how the queries and updates work. 2D BIT is basically a BIT where each element is another BIT. Adding v on (x, y) means it's effect will be found throughout the rectangle [(x, y), (W, H)], and query for (x, y) gives you the result of the rectangle [(0, 0), (x, y)], assuming the total rectangle is [(0, 0), (W, H)]. SO when you query and update on this BIT, you have to be careful about how many times you are subtracting a rectangle and adding it. Simple set union formula works here. So if you want to get the result of a specific rectangle [(x1, y1), (x2, y2)], the following steps are necessary to do so:
V = Query(x2, y2)
V -= Query(x2, y1-1)
V -= Query(x1-1, y2)
V += Query(x1-1, y1-1)

This problem is an example: SPOJ - MATSUM

This page is likely to be updated if I find and manage to solve new types of BIT problems. Please let me know if there are mistakes. This post is inspired by some random posts lying around in TopCoder forums, I just wanted to put them in one place for future reference.