Hedge Mazes - ICPC Latin America

Now I solved problem Hedge Mazes, the statement is available here.

I will just give the idea of the solution. The problem basically requires that it should be answered for each query whether there is a single simple path that connects the given vertices or if there is more than one simple path.

So basically it is asked whether there is a loop in the path between the vertices. Well, the condition for there being no loops is that the whole path should be composed only of bridges. If an edge (vi, vj) of the path isn't a bridge then there is another way from vi to vj and so there is no longer only one path from vi to vj.

So now the only thing we need to do is to check the graph for bridges and later check the connectivity of the graph composed only by them. If two vertices are in the same component composed only of bridges then there is only a single path between them.

The code is available here.

King's Poker - ICPC Latin America 2011

I've just solved problem King's Poker, the solution is here

In Braille - ICPC Latin America 2011

This time here is the solution to problem In Braille from ICPC Latin America 2011, the statement is here.

The problem is quite simple, so I'm just going to post the code as a reference:

http://codepad.org/Q5gcQNHe

Jupiter attacks - ICPC Latin America 2011

I have just solved problem Jupiter Attacks! from last year's ICPC Latin America regional contest. You can read the statement here.

Basically there is a sequence of bytes of size L (1 <= L <= 10^5), but not normal bytes, these bytes accept values in the range [0, B-1] (2 <= B <= 10^9). There are N (1 <= N <= 10^5) operations of two possible kinds:

• Change the value of a given position
• Calculate the value of a given interval, considering it a number of B bytes, big-endian. Giving the value modulo P (1 <= P <= 10^9, P prime and given in the input)

So what we need is a efficient way of changing the value of a single byte and calculating the sum of a specified interval, taking linear time to solve this problem is too slow, N*L = 10^10, what is far too much. The limits indicate a logarithmic way of summing seems reasonable.

Well, if this was a simple sum of an interval we would know how to calculate and change the sum in an efficient way, one possible way is using a Binary Indexed Tree (BIT, explanation about this structure at Topcoder), or you might use Segment Tree or a Range Minimum Query.

But we have the problem that the value of a specific cell in the summation depends on the beginning of the interval. But is that such a problem? It is possible to keep the summation with each cell i multiplied by B^(L-i) and divide the summation by the proper value, if we ask for an interval that goes from i to j we have just to divide this sum by B^(L-j) .

Now there is another problem, the values are too big to be kept without taking the modulo and we can't simply divide a value after having applied the modulo. Now comes an important information: P is prime, and as such there is always a modular inverse, which acts as the division operator in modular arithmetics. Modular inverse can be quickly calculated with extended euclidean algorithm.

My implementation to this solution is available at codepad.