codechef BESTBATS - "top batsmen" solution and guidance

codechef BESTBATS - "top batsmen": http://www.codechef.com/problems/BESTBATS

codechef BESTBATS - "top batsmen" solution: http://ideone.com/QpJR8X

#include <iostream>

#include <cstdio>

#include <cstdlib>

using namespace std;

int fact(int a) {

return (a==1 || a==0) ? 1 : fact(a-1)*a;

}

int cmp(const void *a, const void *b) {

return (*(int*)b - *(int*)a);

}

int main() {

int t, p[12], k, k_th, in, out, tot;;

scanf("%d", &t);

while(t--) {

for(int i=0; i<11; i++) scanf("%d", &p[i]); scanf("%d", &k);

qsort(p, 11, sizeof(int), cmp); 

k_th=p[k-1]; in=out=tot=0;

for(int i=0; i<k; i++) if(k_th==p[i]) in++;

for(int i=k; i<11; i++) if(k_th==p[i]) out++;

tot=in+out;

printf("%d\n", fact(tot)/(fact(in)*fact(tot-in)));

}

return 0;

}

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.

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: 

  

or

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:

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:

later i learned that through factorials, i can get to that element. how to do it? the image above explains everything ;)