RAINBOWB - Editorial

editorial
, , , ,
21

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.
3 Likes
22

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.

23

Can anybody tell if the formula (k-1)C(5) is applicable for k<7 ,because in all these cases answer will come out to be 1.
for example: a1+a2+a3+a4+a5+a6=2 ,here k=2,by using above formula answer will be 1.but in actual it should be 21…please help,any kind of help will be appreciated

24

for nCr to work n must be greater than equal to r. In your case k-1=1 is less than 5 therefore answer is 0.

1 Like
25

Dude Awesome !!

26

why C(K-1,5) ?

It should be 6, right?

27

@amit001 i think you perhaps misunderstood the solution given in the editorial. As we are brute forcing all the values for 7 so we need to distribute the rest of the values in six containers. agree ??

28

@kodoos my bad. i was reading solutions in comments so thought 6 should be used but solution above brute force a7. now got it

29

python nails it.

30

Why is it not C(k+5,5)?


The link is just for a reference to such kind of equations.

31

Why is it not C(k+5,5)? http://cseweb.ucsd.edu/classes/wi10/cse20/CSE20%20Lecture%2015.pdf The link is just for a reference to such kind of equations.

32

awesome!!!

33

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.

34

/*

  • 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®;
    }

    }

    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 ?

35

if you are facing problems in implementing the aforesaid algorithm, using C++, you can have a look at my solution:

https://www.codechef.com/viewsolution/16738557

Note: 1. I was completely blown off by this idea (still can’t figure out why) @ma5termind
2. I just figured out that ‘int’ in python has a larger range than ‘long long int’ in C++