-

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



Comments

Post a Comment

Popular posts from this blog

-
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
Read more
-
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...
Read more

My Programming Contest And Problem Solving Profiles

-
  Programming Contest: Participated in around 15 national programming contests including 1st AUB IUPC 2018 (MBSTU_Legendary_NEWBIE, 3rd) NCPC AKA HACKATHON BY BSCCL AT UITS 2018 (Partha Saha's Team,16th)  LU CSE Carnival 2019 Inter-University Programming Contest (Legendary NEWBIE, 16th) RUET Technocracy 2019 (MBSTU_Legendary_NEWBIE, 24th) SUST Tech Fest 2019 (MBSTU_Legendary_NEWBIE, 25th) BUET CSE Fest 2019 (MBSTU_Legendary_NEWBIE, 36th) IUBAT NCPC 2018 (MBSTU_Legendary_NEWBIE , 37th) ACM ICPC Dhaka Regional 2017(MBSTU_Legendary_NEWBIE) ACM ICPC Dhaka Regional 2018(MBSTU_Legendary_NEWBIE) ACM ICPC Dhaka Regional 2019(The Last of the NEWBIE) Training: BACS Regional Programming Camp-2017(Khulna, Beginner) BACS National Programming Camp-2017 (Intermediate) Online Judge & Contest Judge ID: Solved more than 2000 problems in different online judges and participated in more than 100 online contests. Codechef:  ID: sarwar05 Maximum Rating: 2142 (5*) Codeforces:  ...
Read more