You are not logged in. Please login at www.codechef.com to post your questions!

×

ACM ICPC Chennai Regionals

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

nickzuck_007's gravatar image

3★nickzuck_007
191621
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.

link

answered 17 Nov '15, 22:10

aakashj's gravatar image

2★aakashj
361
accept rate: 100%

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

pratikpugalia's gravatar image

4★pratikpugalia
17216
accept rate: 25%

wikified 18 Nov '15, 20:48

Thank you @aakashj and @pratikpugalia

link

answered 08 Dec '15, 23:07

nickzuck_007's gravatar image

3★nickzuck_007
191621
accept rate: 14%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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