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]

SRM 491 DIV 2

Problem Statement
    
We say that two integer numbers differ from each other by one digit, when in their decimal notation, possibly with leading zeros, they will differ in exactly one position. For example numbers 128 and 28 differ by one digit:
128
028
But numbers 2047 and 40 differ by two digits:
2047
0040
Given the number N, find and return the smallest possible non-negative number M, such that number N and M differ from each other by exactly one digit.
Definition
    
Class:
OneDigitDifference
Method:
getSmallest
Parameters:
int
Returns:
int
Method signature:
int getSmallest(int N)
(be sure your method is public)
    

Constraints
–
N will be between 0 and 2,000,000,000, inclusive.
Examples
0)

    
9
Returns: 0
0 is the smallest non-negative number and differs by only one digit.
1)

    
0
Returns: 1
The result number is not always smaller than N.
2)

    
900000123
Returns: 123
Leading zeros in the result are okay:
900000123
000000123
3)

    
30000
Returns: 0
Leading zeros are okay also with 0 as a result:
30000
00000
4)

    
47
Returns: 7

5)

    
1907654321
Returns: 907654321

This problem is very easy to solve if we convert the given int N  to string.

If the first digit is 0 make it as 1

else make it as 0

Then convert this string to integer !!

To convert int to string and then string to int one can use the c++ string stream

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

SRM 591 DIV 2 TheArithmeticProgression

Problem Statement
    
A triple (x, y, z) is called an arithmetic progression if the equality y – x = z – y holds. You are given three ints a, b and c. Your goal is to change the triple (a, b, c) into an arithmetic progression. You are only allowed to change one of the three numbers. The change must proceed as follows: First, you choose a non-negative real (not necessarily integer) number r. Then, you either add r to one of the three given numbers, or you subtract r from one of them. Return the minimum value of r which allows you to create an arithmetic progression.
Definition
    
Class:
TheArithmeticProgression
Method:
minimumChange
Parameters:
int, int, int
Returns:
double
Method signature:
double minimumChange(int a, int b, int c)
(be sure your method is public)
    

Constraints
–
a will be between 0 and 1000, inclusive.
–
b will be between 0 and 1000, inclusive.
–
c will be between 0 and 1000, inclusive.
Examples
0)

    
0
1
2
Returns: 0.0
The triple (0, 1, 2) is an arithmetic progression. Thus, you can choose r = 0.0 and add or subtract it from any of the given numbers without changing the triple.
1)

    
0
2
1
Returns: 1.5
Note that while (0, 1, 2) is an arithmetic progression, you cannot rearrange the numbers within the triple. You can choose r = 1.5 and subtract it from b, obtaining the triple (0, 0.5, 1).
2)

    
3
2
1
Returns: 0.0

3)

    
4
4
8
Returns: 2.0

Just use th A.P mid formula 

ie. if a,b,c is A.P

then mid=(a+c)/2

So b should be (a+c)/2

if b is not (a+c)/2 then add or subtract from b such that it is equal to (a+c)/2

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

SRM 518 DIV 2 TwiceString

Problem Statement
    
You are given a string s. Return the shortest string which contains s as a contiguous substring twice.
Note that two occurrences of s may overlap. For example, “ababa” contains “aba” twice.
Definition
    
Class:
TwiceString
Method:
getShortest
Parameters:
string
Returns:
string
Method signature:
string getShortest(string s)
(be sure your method is public)
    

Notes
–
The shortest string which contains s as a contiguous substring twice is always unique.
Constraints
–
s will contain between 1 and 50 characters, inclusive.
–
Each character in s will be a lowercase letter (‘a’-‘z’).
Examples
0)

    
“aba”
Returns: “ababa”
This is the example shown in the problem statement.
1)

    
“xxxxx”
Returns: “xxxxxx”

2)

    
“topcoder”
Returns: “topcodertopcoder”

3)

    
“abracadabra”
Returns: “abracadabracadabra”

 

Solution: 

   If you closly look into the examples you will know tat   you have to find the largest  common prefix and suffix.

i.e in this case “abracadabra”

     largest common prefix and suffix is abra (first 4 characters and last 4 characters)

So run a loop and use inbuilt string functions to find it. After finding it

 concatenate original string with string in which the common prefix is removed(“cadabra” in above example) thats it!!!

 

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