>__

A Gray code is a list of all 2^n  bit strings of length , where any two successive strings differ in exactly one bit (i.e., their Hamming distance is one).  source   The problem is, how to generate Gray Code for a given length n.  When n = 2 , Gray Code :  00  01  11  10 When n = 3, Gray Code : 000 001 011 010 110 111 101 100 000(0) position Gray code string 000  001(1) -> 001  010(2) -> 011  011(3) -> 010 .....  Key observation -  For the  K position, the Gray code string is S .   if i and (i+1)- th bit of K is equal then i- th char of S will be  ' 0 ', otherwise, it will be ' 1 '.   Code :               int n; cin >> n;     for(int i = 0; i < (1 << n); i++) {         int value =  ( i ^ (i >> 1) ) ;         string s = "";         for(int j = 0; j < n; j++) {             if( value & (1 << j) )s.push_back('1');             else s.push_back('0');         }         reverse( s.begin(), s.end() );      

Codeforces Global Round 6 A. Competitive Programmer According to the problem statement you are given some digits ( 0 - 9 ) , is it possible to make a number using all digits which is divisible by 60 ? To make a number from the digits which is divisible by 60, we need a zero and more than one even digits and digits sum must be divisible by 3. Code : B. Dice Tower According to the the picture given in the problem the sum of any two oppsite side of the dice is 7. Accept top dice , sum of all visible side pips in a dice is 21 - 7 = 14. We can make a tower , which all visible pips is equal to n , if n = 14 * d + 14 + pip n = 14 * D + pip where pip = { 1, 2, 3, 4, 5, 6 } Code :

Mail.Ru Cup 2018 Round 3 [ E. Check Transcription ] Solution :

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