For checking whether there is a way to conduct all the songs of the singer, you can conduct the event in the following way.
- First singer will sing a song.
- Then during 10 minutes rest of the singer, the joker will crack 2 jokes(each of 5 minutes)
- Then singer will again sing a song, then joker, etc.
- After the singer has completes all his songs, the joker will keep on cracking jokes of 5 minutes each.
Hence minimum duration of the even needed such that sing could sing all his songs will be t1 + 10 + t2 + 10 + ... +tn = sum + (n - 1) * 10 where sum denote the total time of the songs of the singer.
So for checking feasibility of the solution, just check whether sum + (n - 1) * 10 ≤ duration or not?.
If it is feasible, then time remaining for joker will be the entire duration except the time when the singer is singing the song. Hence time available for the joker will be duration - sum. In that time joker will sing songs.
You can formulate the problem in following way. Given two arrays a and b. Find minimum cost of matching the elements of array a to b. For our problem the array a will be same as b. The array b will have content x, x — 1, , 1, 1. For a general version of this problem, we can use min cost max flow(min cost matching), but for this problem following simple greedy solution will work.
- Sort the array a in increasing and b in decreasing order (or vice versa).
- Now match ith element of the array a with ith element of array b.
It can be easily proved by exchange argument.
Let us first try to find the condition required to make sure the existence of the partitions.
Notice the following points.
If the parity of sum does not match with parity of number of odd partitions (k - p) , then we can't create the required partitions. eg. a = [1;2], k = 2, p = 0, Then you can not create two partitions of odd size, because then sum of the elements of the partitions of the array will be even whereas the sum of elements of the array is odd.
If number of odd elements in a are less than k - p (number of required partitions with odd sum), then we can not do a valid partitioning.
If number of even elements are less than p, then we can not create even partitions simply by using even numbers, we have to use odd numbers too. Notice the simple fact that sum of two odd numbers is even. Hence we will try to include 2 odd elements in our partitions too. So if we can create oddsRemaining / 2 partitions in which every partition contains 2 odd elements, then we can do a valid partitioning otherwise we can't. Here oddsRemaining denotes the number of odd elements which are not used in any of the partitions made up to now.
Let oddElements denotes the number of odd elements in array a. Similarly evenElements denotes the number of even elements.
So the answer exists if
- Number of possible odd partitions are ≥ k - p i.e. oddElements ≥ k - p.
- Number of possible even partitions are ≥ p i.e. evenElements + (oddRemaining) / 2 ≥ p. where oddRemaining is oddElements - (k - p).
For generating the actual partitions, you can follow the same strategy used in detecting the existence of the partitions. We will first generate any valid p partitions (forget about the condition of using the entire array), then we can simply include the remaining elements of the array in the last partition and we are done.
You can solve the problem in two ways.
- By using ternary search
Let us define a function f. Function f(k) = cost needed to make array a elements ≥ k + cost needed to make array b elements ≤ k
Instead of proving it formally, try checking the property on many random test cases. You will realize that f is convex.
Claim: f is convex:
It is fairly easy to prove. See the derivative of f.
= — (# of elements of b > k) + (# of elements of a < k)
The first term (without sign) can only decrease as k increases whereas second term can only increase as k increases.
- By using the fact that optimal values are attainable at the array values:
All the extremum points will lie in the elements from the any of the arrays because f is convex and at the event points (or the points of array a and b).
For learning more about ternary search, you can see following topcoder discussion
Another smart solution
- ternary search solution
- my solution using 2nd fact
- [user:Gerald] solution
- [user:triveni] solution using smart solution
There are two possible solutions.
Let P(n, f) be total number of ways of partitioning n into f segments such that each a i is positive. With some manipulations of the generating function, you can find that this is equal to .
Let F(n, f, g) denotes partitions of n into f parts such that gcd of all the ai's is g.
Note that F(n, f, 1) = P(n, f) — sum of F(n, f, g) over all possible gcd g's. So g will be a divisor of n.
In other words,
You can implement this solution by a simple dp.
You can pre-calculate factorials which will help you to calculate .
Complexity of this solution will be nlogn over all the test cases.
Please note that this solution might get time limit exceeded in Java. Please read the comment.
Note that F(n, f, 1) = P(n, f) — sum of F(n, f, g) over all possible gcd g's (g > 1 such that g is a divisor of n.
In other words,
As F(n, f, g) = .
Now you have to use Möbius inversion formula.
If f and g are two arithmetic functions satisfying
So In our case: g(n) is P(n, f) and f(n) is F(n, f, 1).
For proving complexity: Use the fact that total number of divisors of a number from 1 to n is