How to approach the question CHAOS .

general
,
1

What should be approach for the question CHAOS

        https://www.codechef.com/EXTE2015/problems/CHAOS
1 Like
2

movers and packersn new ashok nagar @ http://www.delhilocal.in/packers-movers-new-ashok-nagar.html

Packers and movers Punjabi bagh @ http://www.delhilocal.in/packers-movers-punjabi-bagh.html
Packers and movers hari nagar @ http://www.delhilocal.in/packers-movers-hari-nagar.html
Packers and movers uttam nagar @ http://www.delhilocal.in/packers-movers-uttam-nagar.html
movers and packers dwarka @ http://www.delhilocal.in/packers-movers-dwarka.html
Packers and movers janakpuri @ http://www.delhilocal.in/packers-movers-janakpuri.html
movers and packers laxmi Nagar@ http://www.delhilocal.in/packers-movers-laxmi-nagar.html
movers and packers mayur vihar @ http://www.delhilocal.in/packers-movers-mayur-vihar.html

3

N = 14 M = 2

_ _ X1 _ _ _ X2 _ _ X3 _ _

here Xi denotes chaotic cities.

let C denotes no of cities between particular consecutive chaotic city.
The order in which cities become chaotic range from 1 to N-M
thus we have to find no of ways of selecting C orders out of N-M = combination(N-M,C);
once order has been selected ,cities present on these order will permute among them self.
e.g. there are 3 cities between X1 & X2 let we numbered it as 1,2 & 3.
no of ways of arrangement are:(because of constraint of chaosing)
1 2 3

1 3 2

3 1 2

3 2 1

= 4

we can find for any n consecutive as:
2^(n-1) //22…*(no of candidate for ith position of selected order ) *2…*1

thus number of ways of order cities between Xi & Xi+1 = comb(N-M,C) * 2^(C-1)

after set,no of available orders are :N-M-C

do this for all cities between consecutive chaotic cities and multiply them.
find no of ways of order cities§ before 1st chaotic city as:comb(remaining orders,p) and multiply it.
after multiplication you will get answer.

feel free to ask any question:)

1 Like
5

crystal clear explanation !! thanks buddy :slight_smile: