>__

Straightforward LCA implementation. Problem: LCA - Lowest Common Ancestor SPOJ Algorithm Source : CP-Algorithms

Problem  :  TSHOW2 - Fibonacci brain Solution : We can easily calculate nth Fibonacci number by dynamic programming using the recurrence relation - \[ { f(x) } = \left\{ \begin{array}{ll} { f(x-1) + f(x-2) } & \mbox{if } x > 2 \\ 1 & \mbox{if } x = 2 \\ 0 & \mbox{if } x = 1 \end{array} \right. \] f[1] = 0 f[2] = 1 for i in { 3 ... n } f[i] = f[i-1] + f[i-2] But we cannot calculate Fibonacci number by dynamic programming when n is large like 10^18. We can easily calculate large 10^18 Fibonacci number by  matrix exponentiation . We can write that, \[ \begin{bmatrix} {1} & {1} \\ {1} & {0} \end{bmatrix} ^ {n} = \begin{bmatrix} { f(n+1) } & { f(n) } \\ { f(n) } & { f(n-1) } \end{bmatrix} \] n is large , using binary exponentiation we can calculate nth Fibonacci number by O(log n) complexity.    

Infinite fractions \[ \text{When is }\ x \mid y \text{ ?} \ \] x can be represent as \[ {x} = \prod_{i=1}^n p_{i}^{k} \] \[ \text{where}\ p_{i} =\text{ is a prime factor of } {x} \text{ and } {x} \text{ has } {n} \text{ prime factors.} \] \[ \text{Example: }\ {x} = {12} = {2}^{2} \times {3} \] We can represent the y by the same way. x divides y ( x is a divisor of y ) if and only if all prime factors of x are available in y prime factorization and each prime factor (p) power (p^a) in x factorization is less than equal to prime factor (p) power (p^b) in y factorization (a <= b). Or we can say that when GCD(x, y) = x  , x divides y. \[ \text{When is }\ x\nmid y \text{ ?} \ \] y = q * x + r [ where r < x ] When reminder (r) is not equal to 0, y is not divisible by x.  Only when r is not equal to zero there are numbers after the decimal point of fraction p/q. How to get numbers after the decimal point of a fraction ? We recursively do it until MOD = 0. initially MOD

I woke up early today for SRM ( 7 AM ) . I solved 2 problems DIV-2 Easy and Medium. DIV-2 easy is just an implementation problem.  Problem Statement of DIV-2 easy      You found a deck of slightly non-traditional playing cards. Each card has a value and a suit. The value of each card is a positive integer, and the suit is a lowercase English letter ('a'-'z'). We will use (v, s) to denote a card with value v and suit s. You want to know whether the deck is perfect. A perfect deck has two properties: All cards in the deck are distinct. (I.e., no two cards share both value and suit.) For any two cards (v1, s1) and (v2, s2) in the deck, the deck also contains the cards (v1, s2) and (v2, s1). You are given the following data:

The problem states that, A greedy king wants to build a wall around his castle with minimum cost and wall should not come closer to the castle than a certain distance. Given N Cartesian 2D points and minimum distance between castle and wall is  L .  To solve the problem , At first I build a convex hull using the points .  The wall should be L distance from castle . So, we need another 4 * acos(0.0) * L length ( Summing up all round length of each point of the convex hull ) .  Problem ::  Wall  

I could not solve the D. Perfect Security in last night's codeforces contest. In the morning I finally understood that the problem was actually a Trie problem. To solve the problem I used a structure name trie which has two trie type structure zero and one and a counter name cnt. For each trie node the cnt stores the number of zeros or ones in that node. As problem says to minimum XOR values. So, the search operation traversing the same bit node ( bit 1 for one and 0 for zero trie type node ) of the Trie tree. If the search operation fail to found the same bit node with a positive counter values, then the operation check for reverse bit node with positive counter. If the conditions are not satisfied, it stops the search operation. For Trie type node one turned on the return value bit position. value | = (1 << position) . The search operation always reduce the traversing nodes counter by 1, So no need to delete operation for each keys.

First Time I have solved a problem with Perl in Codeforces . It's an amazing language. http://codeforces.com/contest/946/submission/36063847

Solution

Problem

Problem : MSTICK

Problem :: MDOLLS