×

# ACM ICPC Chennai Regionals

 0 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 asked 17 Nov '15, 15:22 191●6●21 accept rate: 14%

The third problem can be done through dynamic programming. At every step:-

1. You can pick either the leftmost or rightmost bowl.
2. 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★aakashj
361
accept rate: 100%

 1 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) link This answer is marked "community wiki". answered 17 Nov '15, 16:17 172●1●6 accept rate: 25%
 0 Thank you @aakashj and @pratikpugalia answered 08 Dec '15, 23:07 191●6●21 accept rate: 14%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,101
×40

question asked: 17 Nov '15, 15:22

question was seen: 1,731 times

last updated: 08 Dec '15, 23:07