# RAINBOWB - Editorial

Difficulty : Simple

Pre-requisites : basic math

Solution :

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.

9 Likes

I solved it using a dynamic programming approach

Edit:
Explanation.

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:

7 Likes

Can you explain it?

I’ve tried my best to explain it.

Setter’s and tester’s solutions aren’t accessible.

3 Likes

Can someone explain how do we get this formula

a1+a2+a3+a4+a5+a6=M/2=K is C(K-1, 5).

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).

6 Likes

yeah got it thanks…i was missing the point that we need an integer solution (a(i) > 0)…so i was effectively considering 6 bars…

O(1) solution also exist for this problem.

1 Like

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)

2 Likes

what is “first 6 columns of the Pascal triangle” ? please explain.

The problem statement is unclear, ambiguous!

how to find combination formula using pascal? can u clear

1 Like

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.

import sys

f=sys.stdin

mod=1000000007

if n<13:

``````print 0
``````

else :

``````n+=1

n/=2

n-=1

ans=n*(n-1)*(n-2)*(n-3)*(n-4)*(n-5)

ans/=720

ans%=mod

print ans
``````

</a

here is my python code for this problem . hope you like this.

5 Likes

explanation to the solution is provided below

C(M,6) where M=(n-1)/2

C(M,6) where M=(n-1)/2

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)?

Could you explain your reasons for believing so?

Can anyone let me know why pascals triangle is required? PLease.

2 Likes