aishraj

The number of 1's in the range 0..X (X is positive) is easy to calculate (Can you get a simple recurrence which does this in O(log X) ?) Another observation is that the number of 1's in -X is equal to the number of 0's in ~(-X) = X - 1. Using this, it is easy to calculate the answer for negative ranges as well.

aishraj

The line graph of a graph G is a graph having the edges of G as it's nodes and edges between them if the corresponding edges in G are adjacent. The Hamiltonian Completion Number is the minimum number of edges to be added to a graph for it to have a Hamiltonian Cycle.

Formally, the problem can be stated as asking for the Hamiltonian Completion Number of the line graph of a tree. While this problem is NP-Complete for the general case, it is in fact solvable in polynomial (linear actually) time for trees. Again, I do not have a simple algorithm, or a proof of why the algorithm works. Feel free to look at solutions or read up more about the problem online. See: http://en.wikipedia.org/wiki/Hamiltonian_completion http://www.sciencedirect.com/science/article/pii/S0020019000001642

Note that the caterpiller trees discussed above are precisely the trees for which the Hamiltonian Completion Number of their line graphs is 0.

aishraj

`The required answer is : 1 / (n + k) * n-choose-r(n - 3,k) * n-choose-r(n + k, n - 1).

While I am not aware of a simple way to prove this which I can describe here, here's some practical advice on how such problems can be approached. It helps to write down a simpler solution and searching Google or OEIS (Online Encyclopedia of Integer Sequences) for small inputs like k = 3 and N = 1,2,...10. This usually gives you a formula describing the sequence, and possibly generalizations for the same.

Computing the answer using the above formula requires calculating the power of MOD (1e6 + 3) in the numerator and the demonimator. If the power of MOD is bigger in the numerator, the answer is 0. Otherwise, we can calculate all the factorials with the powers of MOD cast out. For example, if MOD = 3 and N = 11, we would calculate the product 1 * 2 * 3 / 3 * 4 * 5 * (6 / 3) * 7 * 8 * (9 / 9) * 10 * 11. This can be done easily in O(MOD). Once we have that, we can multiply the values in the numerator and mltiply with the mo

aishraj

Turan's theorem gives us an upper bound on the number of edges a graph can have if we wish that it should not have a clique of size x. Though the bound is not exact, it is easy to extend the statement of the theorem to get an exact bound in terms of n and x. Once this is done, we can binary search for the largest x such that f(n,x) <= m. See: http://en.wikipedia.org/wiki/Tur%C3%A1n's_theorem

aishraj

The answer is the number of inversions in the array, which is the number of pairs i,j such that i < j and a[i] > a[j]. Counting this is a fairly classical problem with many solutions such as using data structures such as Balanced Trees or Binary Indexed Trees. Another particularly elegant solution involves modifying merge sort to count the number of inversions when merging the two sorted halves in the algorithm.

aishraj

Considering each permutation of the letters as a variable, we get a number of simultaneous equations which can be solved using Gaussian Elimination to compute the expected value of each permutation. However, the number of variables is very large. This can be reduced by making the observation that many states such as "abab" and "baba" are essentially the same since the letters in them are simply relabelled. Thus we can normalize each string by letting it start with an 'a', replacing the next occuring character with a 'b' and so on. For example, string "paddpa" would be normalized to "abccab". This reduces the number of variables greatly, and also helps us efficiently memoize across various test cases. Also, we should note that running one Gaussian Elimination gives us the expected values for many states (and not just one), all of which should be saved for future reference.

aishraj

Such a tour exists only when the tree is a caterpiller tree which is a tree consisting of a straight path with some leafs attached to nodes on that path. Using this observation, getting a recurrence and solving it using Dynamic Programming is greatly simplified. Also, working out some examples on paper, it is easy to see that the answer is 2 * n1! * ... * nk! where n1,..,nk are the number of leafs attached to each node on the path defining the caterpiller tree. A special case is when the tree is a star, when the answer is simply (n - 1)!. See: http://en.wikipedia.org/wiki/Caterpillar_tree

aishraj

Queens on a Board Solution (InterviewStreet CodeSprint Fall 2011)

aishraj

The main observation is that the card at index i (1 <= i <= N) ends up at index K * i % (N + 1) after 1 shuffle. So after x shuffles, the card will be at position K^x * i % (N + 1). We want to find the smallest x such that K^x * i = i for all i. In other words, we want K^x = 1. This is known as the multiplicative order of K mod (N + 1). Lagrange's theorem implies that this will be a factor of phi(N + 1) where phi is the Euler Totient function. So we can check all factors of phi(N + 1) and find the smallest one which works. See: http://en.wikipedia.org/wiki/Euler's_totient_function http://en.wikipedia.org/wiki/Lagrange's_theorem_(group_theory)

aishraj

The answer is the number of inversions in the array, which is the number of pairs i,j such that i < j and a[i] > a[j]. Counting this is a fairly classical problem with many solutions such as using data structures such as Balanced Trees or Binary Indexed Trees. Another particularly elegant solution involves modifying merge sort to count the number of inversions when merging the two sorted halves in the algorithm.