How do I solve these questions
https://www.codechef.com/ACMCHN15/problems/CHN15B
https://www.codechef.com/ACMCHN15/problems/CHN15C
from ICPC regionals held this year …I didn’t found any editorial
Please help
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 :
1)Every participant is a node.
2)Every Team Relation is a bi-directional edge.
3)So every component in the graph represents a team.
4)You need to find the expected number of team , i.e. the expected number of connected components.
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(x-1)
1 Like
The third problem can be done through dynamic programming. At every step:-
- You can pick either the leftmost or rightmost bowl.
- You can place it either at the left of the new line or right of the new line.
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) = min( ans(i+1,j) + min( inversion_count_left(i,j,i), inversion_count_right(i,j,i)),
ans(i,j-1) + min( inversio_count_left(i,j,j), inversion_count_right(i,j,j));
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 inversion-count-left 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 inversion-count-right 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.
2 Likes