SARWAR

HDU - Fibonacci Tree Problem in short:  Given some black and white edge, you need to check if there exists a spanning tree where the number of the white nodes is a Fibonacci number. Idea:  Count the number of maximum needed white edge to form a spanning tree. Let it be need_mx. Count the number of minimum needed white edge to form a spanning tree. Let it be need_mn . If there exists a Fibonacci number between [ need_mn , need_mx ] then there exists a spanning tree where the number of the white nodes is a Fibonacci number. Check if the graph is connected or not. To get  need_mx we first consider all edges with white color. And for need_mn first consider all edge with black color. We can do this easily with Kruskal's algorithm. Code

1038 - Race to 1 Again Idea: let n = 2; it has 2 divisors, 1 and 2. so the probability to move from 2 to any other value is (1/2.0) = 0.5 from Expected Value, if the expected value to go 1 from 2 is E then we can go to 1 with 1 move and if we go to 2 then we need (1+E) moves E = 0.5*1 + 0.5*(1+E) => 2E = 1 + (1 + E) => 2E = 1 + 1 + E => E = 2 let n = 50 divisors of n are : 1, 2, 5, 10, 25 ,50. It has 6 divisors. so the probability to move from 50 to any other value is = (1/6.0). let the Expected value of any number to go 1 is P() except 50. from Expected Value, if the expected value to go 1 from 50 is E then E = (1/6.0)*(1+0) + (1/6.0)*(1 + P(2)) + (1/6.0)*(1 + P(5)) + (1/6.0)*(1 + P(10)) + (1/6.0)*(1 + P(25)) + (1/6.0)*(1 + P(50)) => E = (1/6.0)*1 + (1/6.0)*(1 + P(2)) + (1/6.0)*(1 + P(5)) + (1/6.0)*(1 + P(10)) + (1/6.0)*(1 + P(25)) + (1/6.0)*(1 + E) =>E - (1/6.0)*(1+E) = (1/6.0)*1 + (1/6.0)*(1 + P(2)) + (1/6.0)*(1 + P(5)) + (1/6.0)*(1 + P(10)) + (1...

1044 - Palindrome Partitioning Idea: i) First, generate all possible palindromic substring (both odd length and even length). And store them in a list. let str[] = "QWERTYTREWQWERT" We have a palindrome form  str[0] to str[0]. So we store (0+1) at List[0], which means that if we consider this palindrome we can jump to index [1] to find our next palindrome.   We have a palindrome form  str[0] to str[10]. So we store (10+1) at List[0], which means that if we consider this palindrome we can jump to 11'th index to find our next palindrome.  We have a palindrome form  str[4] to str[6]. So we store (6+1) at List[4], which means that if we end our previous palindrome at index [3], then we can consider a palindrome which starts at index[4] and ends at index[6]. 2) The second step is to calculate the minimum number of jump needed to reach the end of that string from index[0]. Code