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 :
IMAGE 2:
IMAGE 3:
IMAGE 4:
IMAGE 5: