If we reformulate the problem, we’ll get the following one: given an integer N, calculate the number of integer vectors (a1, a2, a3, a4, a5, a6, a7) such that:
ai > 0, for each i, 1 <= i <= 7;
2(a1+a2+a3+a4+a5+a6)+a7=N.
Let’s brute-force a7. Then, we’ll have to calculate the number of integer vectors (a1, a2, a3, a4, a5, a6) such that 2(a1+a2+a3+a4+a5+a6)=N-a7=M. Of course, M should be even, otherwise there won’t be any solution.
And now, we use the well-known fact that the number of integer vectors (a1, a2, a3, a4, a5, a6) such that a1+a2+a3+a4+a5+a6=M/2=K is C(K-1, 5). These numbers can be obtained by the calculation of the first 6 columns of the Pascal triangle.
First of all we need to figure out how many “extra” numbers can we add so given the value of N we add one an then divide by 2.
N++; N /= 2
Then we check if N - 7 is negative, if it is we cannot form any rainbow array so the answer is 0.
If it is positive or 0, we follow the next procedure:
In the code I use an array int R[] = {1,2,3,4,5,6,7}; ¡even though there is no need to! (sorry)
Our DP function will receive two parameters int i for the value we’re placing in our rainbow arrray and int rest to keep track of how many extra numbers can we still add.
Inside the DP function we check for the value of i it is 7 (means we have placed all 7 numbers) so we check if we have placed all our “extra” numbers, if we have then that is one posibility. If we have not, that is not a posibility.
If the value of i is less tan 7, we have to make a decisión (to use an “extra” number or not), we can still add “extra” numbers if the value of res is other tan 0. If we add extra value our i stays the same but res decreases by one, in the other hand i increases by 1 and res stays the same.
If we use a recursive implementation it might give RTE, but with an iterative one I’ve got AC.
English is not my native language so please ask me or check my working code C++ or C# if you still have doubts:
We have to distribute K objects among 6 people. Suppose, all the K objects are lying in a row on the floor equally spaced. Now, if you put 5 bars, beetween any of the objects (gap b/w the objects), it will divide K objects into 6 parts and will be one possible solution of the equation above. So, all possible combinations can be given by (k-1)c(5) ( i.e. selecting 5 gaps among k-1 gaps).
yeah…thats what i did during contest…basically we need to find the total integer solutions to equation. a1 + a2 + … + a6 <= K…
it comes to combination(K,6)
Although i got your solution that you have brute force the value of a7. But, does it really required here is my solution to this problem .
I thought
if n is even then first n/2 will be exactly same as next n/2 integers but in opposite order.
else first (n)/2 will be same as next n/2 but n/2+1 being equal to 7.
so , what do we need to find is how many ways are there such that we can distribute (n+1)/2 elements in 7 boxes such that each box contains at least one element.
consider M=n/2+1
and the formulla M-7+6 C 6.
M-1 C 6.
A much simpler solution in terms of big notation. This way this problem can be solved for the higher constraints too.
Hope all of you get the idea. if anything is not understandable do comment here.
Can you tell me where my reasoning is wrong? For K=7, there is 1 solution: 1…7. for K=8, you can choose any one of [1,7] to clone, so ans=7. *For K=9, you can again choose any one of [1,7] to clone, including one chosen before (for. eg. 1,2,2,2,3,4…), so ans = 7**7. Continuing this way, shouldn’t it be 7^(K-7)?
