PROBLEM LINK:Author: Chandan Boruah DIFFICULTY:Simple PREREQUISITES:Greedy PROBLEM:Given N balls, each ball colored either red or blue, we have to find maximum number of green balls we can make. A Green ball can be made by merging consecutive red and blue ball. QUICK EXPLANATION
EXPLANATIONAll we need to do is to merge red and blue ball whenever we find a pair of such balls. All we need to prove now is that this approach is optimal. Consider example: RBRB Here, if we choose to merge second and third ball, our final compostion would look something like this RGB. Since we cannot move Green ball from inbetween, we cannot merge the remaining red and blue ball. This proves that we should perform the merge operation as early as possible, otherwise Green ball might block future merge operation. Instead of pair (2, 3), had we chosen (1, 2), we can still merge (3, 4) getting 2 green balls in the end, thus, being the optimal approach for merging. Complexity: AUTHOR'S SOLUTIONS:
asked 12 Aug '18, 10:54
