How do I solve these questions asked 17 Nov '15, 15:22

The third problem can be done through dynamic programming. At every step:
So, there are 4 possible combinations: (pick from left, place at left), (pick from left, place at right), (pick from right, place at left), (pick from right,place at right). You have to choose the best from all the 4 options. The recurrence relation will be like this:
ans(i,j) denotes the part of array for which you have to still compute the result. So computing answer for this part means that elements not belonging to this range have already been included in the final permutation. After you place a bowl at left or right position, you don't need to count the number of inversions of whole array, you just need to count what is the change in the existing inversion count. This can be done easily in O(n). For inversioncountleft count the number of elements which do not lie between i to j and are less than the element you have put in the left most position. For inversioncountright count the number of elements that do not lie between i to j and are greater than element you have just inserted to the rightmost position. answered 17 Nov '15, 22:10

For the B problem there is a simple O(N) solution that even I figured out after the contest. : Analyze the question in the following way :
Now every player can start his own team ( has 1 ) or join a team of a higher rated coder ( do not have 1). If he starts his own team, he increases the connected components by 1, otherwise he does not affect the number of components. For every lazy coder, 0.5 probability is there that he will join a team & 0.5 probability is there that he will start his own team. Let x = Frequency of 1 in the given array Number of Lazy Coders = x  1 Expected Number of Teams = 1 + 0.5(x1)
link
This answer is marked "community wiki".
answered 17 Nov '15, 16:17
