BESTBATS - Top Batsmen explanation

NOTE: look for image numbers and corresponding images below.
**

codechef BESTBATS - "top batsmen" guidance:
lets sort scores of players(qsort). here i sorted in decreasing order. the number of ways depends on k_th element, it doesnt matter if all elements except k are equal, the situation wont change. if k_th element has equivalents then it does affect the situation. for 1st case in given sample input, there is no equivalent of k, so only 1 way of output is possible. however, on the 2nd sample input, the k_th element=p[i]=2, and it has 4 equivalents(there exist 4 number "2" in the set). so lets calculate how many different ways there exist. assume, 2nd sample input as a set. A = {2, 5, 1, 2, 4, 1, 6, 5, 2, 2, 1}. after sorting set "A" we get, A = {6, 5, 5, 4, 2, 2, 2, 2, 1, 1, 1}. as you see, k_th element is 2, and there are 4 "2"s, and two of them is in set and other two of them is out of the set. so, lets get another set B, which has elements exactly equivalents of k. B = {2, 2, 2, 2}. and now, lets display all subsets of B so that we can see how many ways there exist for each active(in) and passive(out) equivalents. (IMAGE 1)
Let's look at a set B = {1, 2, 3, 4}. 
There is one subset with no elements { } or ø. 
There are 4 subsets with 1 element: {1}, {2}. {3}, {4} 
There are 6 subsets with 2 elements: {1, 2}, {2, 3}, {3, 4}, {1, 3} ,{2, 4}, {1, 4} 
There are 4 subsets with 3 elements: {1, 2, 3}, {1, 3, 4}, {2, 3, 4}, {1, 2, 4} 
There is one subset with 4 elements, B. 
There are 16 subsets in all. 
The rule is a set with n elements has 2^n subsets.
As you have seen above, whence from four elements, two active(displayed within range of K) and two passive(excluded from K bigger elements), there exist 6 different ways of display. and "6" is actual output of 2nd sample. but what if, of four elements, not two but one was active. then there would be 4 different ways of displaying K bigger elements. what if, three of four were active, then again, 4 different ways of exhibition of K bigger elements. if all or none were active, then only 1 way. 
lets look for sets with lesser elements: 
  (IMAGE 2)
or (IMAGE 3)
as you have seen from above images and examples, according to its total elements and activeness(inclusiveness) of them in K range, their exhibition alter. and the change in their exhibition(subset) has relevancy, in numbers. does that relevancy look familiar. i am hearing as if you confirm. yes, you are right, they pinpoint to pascal triangles: (IMAGE 4)
 1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5  10  10  5  1
1  6  15  20  15  6  1 
assume the triangle as an array. we have to output just that exact element(here 6) of total elements(4). put total elements as row, and active elements as columns. 2 active, 4 elements, then we need 3rd element of 5th row. and that number is "6", the exact output of 2nd sample. i tried hardly to program that in c++, but i couldnt, however, i realized that i can reach to the same answer with this: (IMAGE 5)
later i learned that through factorials, i can get to that element. how to do it? the image above explains everything ;)

**
IMAGE 1 :
alt text

IMAGE 2:

IMAGE 3:

IMAGE 4:

IMAGE 5:

my c++ sol: http://ideone.com/QpJR8X

sorry for posting this comment, but here is detailed explanation: http://garakchy.blogspot.com/2014/01/codechef-bestbats-top-batsmen-solution.html

and here is the original editorial - http://discuss.codechef.com/questions/3632/bestbats-editorial

1 Like