RAINBOWB - Editorial

Problem link : contest practice

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.

Setter’s solution: link

Tester’s solution: link

9 Likes

I solved it using a dynamic programming approach :slight_smile:

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

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

O(1) solution also exist for this problem.

1 Like

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

n=int(f.readline())

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

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

2 Likes

My approach might be similar to what others have suggested, but I will mention it nonetheless in case someone hasn’t understood any of the above methods -

if N < 13, then it is impossible to form a Rainbow Array.

Now, for N >= 13, let us first “distribute” the first 13 elements to each of a1 (2 times), a2 (2 times), a3 (2 times)…,a6 (2 times) and a7 (1 time). This constitutes a minimal rainbow array.

Now we have N-13 elements remaining.

If N is odd: // Implies N-13 is even
    In reality, now we only need to distribute (N-13)/2 elements since if we allot one element to a1 before a7 then the other will go to the other a1 (after a7).
    To distribute (N-13)/2 elements among 7 "containers" (a1, a2, a3, a4, a5, a6, a7) in zero or more ways (since we already filled them once before), we have the combinatorial formula C(n+r-1, r-1), where n = (N-13)/2 and r = 7.

If N is even: // Implies N-13 is odd
    Then the number of ways will remain the same as above case since the odd one left will always be sent to a7 and will not contribute to the number of ways.
4 Likes

Hi guys, Maybe I am not getting the solution correctly but where are we checking if the number of a1’s, a2’s etc. are equal in the left and the right of the array.

Please Somebody Explain my How the Number of Vectors equals C(K-1,5).

“…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)…”.

Seriously I don’t know how it came ? Can somebody Please explain me this… I was stuck in this position for a long time during the contest.

/*

  • To change this license header, choose License Headers in Project Properties.
  • To change this template file, choose Tools | Templates
  • and open the template in the editor.
    */
    package codechef;

import java.util.Scanner;
import java.io.*;

/**
*

  • @author admin
    */
    class Rainbow {
    public static void main(String args[])throws IOException

    {
    //Scanner in=new Scanner(System.in);
    BufferedReader br=new BufferedReader(new InputStreamReader (System.in));
    int n=Integer.parseInt(br.readLine());
    if(n>100 || n<1)
    {
    System.out.println(“no”);
    System.exit(0);
    }
    for(int k=1;k<=n;k++)
    {
    int l=Integer.parseInt(br.readLine());
    if(l<7 || l>100)
    {
    System.out.println(“no”);
    break;
    }
    int arr[]=new int[l];
    for(int i=0;i<l;i++)
    {
    arr[i]=Integer.parseInt(br.readLine());
    if(arr[i]>100 || arr[i]<1)
    {
    System.out.println(“no”);
    break;
    }
    }
    String r=IsRainbow(l,arr);
    System.out.println(r);
    }

    }

    static String IsRainbow(int l,int arr[])
    {
    int flag=0;
    int k=((l/2)+1);
    int j=k;
    if (l%2==0 || arr[k-1]!=7)
    flag=0;
    else
    {
    for(int i=k-2;i>=0;i–)
    {
    if(arr[i]!=arr[j])
    {
    flag=0;
    break;
    }
    else flag=1;
    j++;
    }
    }
    if(flag==0)
    return “no”;
    else
    return “yes”;

    }
    }

I know its not good method but I am amateur. I tried this even with scanner method but its coming runtime error. I have successfully compiled it in netbeans and got the result. But, the codechef compiler is constantly showing error. Can someone please tell me the error ?

Can you explain it?

I’ve tried my best to explain it.

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…

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

explanation to the solution is provided below