Posts

Combinatorial Game Theory

Image
Sometimes we find questions where two Players say A and B play a game optimally and we have to find out who ultimately is going to win the game provided there are some constraints. These questions are generally branched under the topic Combinatorial Game Theory. And the speciality about these is that the coding part is relatively very small and easy. The key to the Game Theory problems is the hidden observations which can be sometimes very hard to find. First, we will look at the basic division of positions to winning and losing . Question:  Two players are playing a game with n stones where player 1 always plays first. The two players move in alternating turns and play optimally. In a single move, a player can remove either 1, 3 or 4 stones from the pile of stones. If a player is unable to make a move then that player loses the game. Given the number of stones, find and print the name of the winner. Approach:  As we can see positions 1, 3 and 4 are winning positions since the
Post a Comment
Read more

Discrete Binary Search ( SPOJ AGGRESSIVE COWS)

We all know the standard Binary Search and it's working, let's explore some non-trivial applications of Binary Search and see the Real Power of Binary Search in this post. Discrete Binary Search : -  Before proceeding any further I would request you all to read the  famous SPOJ problem AGGRCOW . And try to think in terms of standard binary search on how can it be solved. If you got the solution, bingo you know what Discrete Binary Search is and can directly proceed to solve a similar question at the end of this post. If not, let's first learn what is Discrete Binary Search. Basically, assume that You have a function f(x) which is monotonically increasing (decreasing) on the interval [a, b]. f(a) < C < f(b) You want to find x such that f(x) = C. Then you can use binary search to find x. Essentially, you half the possible interval for the variable  x  each time. For the AGGRCOW question let's check for the test case, 1 5 3 1  2 4 8
Post a Comment
Read more

Bit Manipulation Problems

We may face many Interview Questions which can ask us to find the Sum of XOR of all pairs of the array OR  Sum of XOR of all subsets   Generally, the constraints for these questions are very high with the value of each array element to be as large as 10^18. So that is a catch to use Bit manipulation method to solve the questions. We will be discussing some of these questions in this post.   Question  1:  Sum of XOR of all possible subsets   Given an array arr[] of size n, we need to find sum of all the values that comes from XORing all   the elements of the subsets.   Input                                                Output  3                                                       28  1 5 6   Explanation:  The most important clue for solving these questions is to find a pattern  with respect to the                property of XOR .  1 = 001 5 = 101 6 = 110 1 ^ 5 = 100 1 ^ 6 = 111 5 ^ 6 = 011 1^5^6 = 010 Total number of subs
Post a Comment
Read more

Fenwick Tree or Binary Indexed Tree(BIT)

Image
We are given an array a[], and we want to be able to perform two types of operations on it. Change the value stored at an index i. (This is called a  point update  operation) Find the sum of a prefix of length k. (This is called a  range sum  query) Solving this question using brute force method would result in a time complexity of O(k) for finding the sum.  Using segment tree the same can be done in O(logK) time. How much better can BIT do to the time complexity?  Ans: No Better.. Time complexity will be same as O(logK) Then why use it? Ans: B ecause binary indexed trees require less space and are  very easy to implement  during programming contests (the  total code is not more than 8-10 lines ).   We know the fact that each integer can be represented as sum of powers of two. Similarly, for a given array of size N, we can maintain an array BIT[] such that, at any index we can store sum of some numbers of the given array. This can also be called a part
Post a Comment
Read more