spoj POUR1 – Pouring water

You can read the problem statement at here.

this problem can be solved using a brute-force approach i.e by doing a bfs on the states of the jars. we can also do a dfs to find a solution but since the problem asks us to find a minimum solution, we have to do bfs.

https://gist.github.com/027531207ada11d6cb31

PS: another of way solving is by using extended euclid’s theorem.(from spoj comments.)

spoj MICEMAZE – Mice and Maze

this problem can be solved using a direct Implementation of Floyd-Warshall’s algorithm(complexity ). If the graph is undirected it is better to solve it using Dijkstra’s Algorithm(complexity Screenshot from 2015-03-28 17:58:14). But unfortunately it is directed graph

https://gist.github.com/53d105c33e3af7c5fc88

codeforces #297 B. Pasha and String

you can get the problem statement from here.

One important point we have to remember here is that if there are two update operation x, y (x < y < n/2) then the positions from y to n - y + 1 remain same as before the update operations.

One easy of looking the problem is as a simple lazy segment tree propagation problem O(n*log(n)). Using the segment tree's we have to record the number of swaps at each position. i.e we just have to perform the update operations(adding 1) in a lazy manner. and after that we have to swap the character if the number of swaps are odd.

https://gist.github.com/546ca7fe7e624fab615a

but this problem can also solved in O(n). i.e counting the number of swaps.

https://gist.github.com/546ca7fe7e624fab615a

spoj PEBBLE – Pebble Solver

you can get the problem statement from here.

after analysing the question a bit, we can come to the conclusion that 1’s in the bit string need odd toggles and 0’s in the bit string need even toggles. and also that we can safely strip the prefixed zero’s.

because if you try to toggle any of them you need to toggle some other-thing preceding that zero(which is also zero), so you don’t want to toggle the prefixed zero’s. based on these conclusions you can easily solve the problem..

https://gist.github.com/071aca1636248cb0e13c