SRM 592 Round 1 500 points problem

Problem Statement
    
This problem statement contains superscripts and/or subscripts. These may not display properly outside the applet.

Little Elephant from the Zoo of Lviv likes permutations. A permutation of size N is a sequence (a1, …, aN) that contains each of the numbers from 1 to N exactly once. For example, (3,1,4,5,2) is a permutation of size 5.

Given two permutations A = (a1, …, aN) and B = (b1, …, bN), the value magic(A,B) is defined as follows: magic(A,B) = max(a1,b1) + max(a2,b2) + … + max(aN,bN).

You are given the int N. You are also given another int K. Return the number of pairs (A,B) such that both A and B are permutations of size N, and magic(A,B) is greater than or equal to K. (Note that A and B are not required to be distinct.)
Definition
    
Class:
LittleElephantAndPermutationDiv2
Method:
getNumber
Parameters:
int, int
Returns:
long long
Method signature:
long long getNumber(int N, int K)
(be sure your method is public)
    

Constraints
–
N will be between 1 and 10, inclusive.
–
K will be between 1 and 100, inclusive.
Examples
0)

    
1
1
Returns: 1
For N=1 the only pair of permutations is ( (1), (1) ). The magic of this pair of permutations is 1, so we count it.
1)

    
2
1
Returns: 4
Now there are four possible pairs of permutations. They are shown below, along with their magic value.
magic( (1,2), (1,2) ) = 1+2 = 3
magic( (1,2), (2,1) ) = 2+2 = 4
magic( (2,1), (1,2) ) = 2+2 = 4
magic( (2,1), (2,1) ) = 2+1 = 3
In all four cases the magic value is greater than or equal to K.
2)

    
3
8
Returns: 18
When A = (1,2,3), there are 3 possibilities for B: (2,3,1), (3,1,2) and (3,2,1). For each of the other 5 values of A, it can be shown that there are 3 possibilities for B as well. Therefore the answer is 3*6 = 18.
3)

    
10
47
Returns: 13168189440000

Solution :

  The 2nd test case explanation itself gives you a very good hint.

So all you need to do now is to generate permutation which can be done easily using 

next_permutation function in stl

[gist https://gist.github.com/vishnujayvel/6728791 ]

SRM 592 Round1 250 points problem LittleElephantAndBooks

Problem Statement
    
Little Elephant from the Zoo of Lviv has a bunch of books. You are given a vector <int> pages. Each element of pages is the number of pages in one of those books. There are no two books with the same number of pages.

You are also given a int number. As a homework from the teacher, Little Elephant must read exactly number of his books during the summer. (Little Elephant has strictly more than number books.)

All other elephants in the school also got the exact same homework. Little Elephant knows that the other elephants are lazy: they will simply pick the shortest number books, so that they have to read the smallest possible total number of pages. Little Elephant wants to be a good student and read a bit more than the other elephants. He wants to pick the subset of books with the second smallest number of pages. In other words, he wants to pick a subset of books with the following properties:
There are exactly number books in the chosen subset.
The total number of pages of those books is greater than the smallest possible total number of pages.
The total number of pages of those books is as small as possible (given the above conditions).

Return the total number of pages Little Elephant will have to read.
Definition
    
Class:
LittleElephantAndBooks
Method:
getNumber
Parameters:
vector <int>, int
Returns:
int
Method signature:
int getNumber(vector <int> pages, int number)
(be sure your method is public)
    

Constraints
–
pages will contain between 2 and 50 elements, inclusive.
–
Each element of pages will be between 1 and 100, inclusive.
–
There will be no two equal elements in pages.
–
number will be between 1 and N-1, inclusive, where N is the number of elements in pages.
Examples
0)

    
{1, 2}
1
Returns: 2
There are two books: one with 1 page, the other with 2 pages. As number=1, each of the elephants has to read one book. The lazy elephants will read the 1-page book, so our Little Elephant should read the 2-page one. Thus, the number of pages read by Little Elephant is 2.
1)

    
{74, 7, 4, 47, 44}
3
Returns: 58
The lazy elephants will read books 1, 2, and 4 (0-based indices). Their total number of pages is 7+4+44 = 55. Little Elephant should pick books 1, 2, and 3, for a total of 7+4+47 = 58 pages. (Note that Little Elephant is allowed to pick any subset, except for the minimal one. In particular, he may read some of the books read by the other elephants.)
2)

    
{3, 1, 9, 7, 2, 8, 6, 4, 5}
7
Returns: 29

3)

    
{74, 86, 32, 13, 100, 67, 77}
2
Returns: 80

 

solution :

    sort pages vector and select (number-1) minimum elements i.e first number-1 elements. 

  Then select (number+1)th element

  In a zero based array select (number)th element

This will give you 2nd minimum subset

[gist https://gist.github.com/vishnujayvel/6728628]