RAINBOWB - Editorial

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

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